c# - トライをディスクに保存する

Question

これは簡単な質問のように聞こえますが、その答えを検索する方法がわかりません。

辞書ファイルから約80Kの単語を保存するC＃のトライ実装があります。これらすべての単語をロードするにはかなりの時間がかかります（5分以上）。アプリケーションを起動するたびにすべての単語をリロードする必要がないように、これらのデータを「永続化」するための最良の方法は何でしょうか。

ありがとう。

Answer 1

他のすべてのパフォーマンスの問題と同様に、理想的なソリューションは、現在のソリューションと思いついた他の候補ソリューションのプロファイリングから得られます。ボトルネックはどこにありますか？I / O？テキストを字句解析しますか？トライでリンクを形成しますか？パフォーマンスの目標、トライの性質、現在のボトルネックを知らずに具体的な提案をするのは難しいでしょう。

考慮すべき問題：

1. ストレージ形式：テキスト？バイナリ？
2. 永続化されたデータ：トライの構造全体（XMLなど）または単語のリストのみで、実行時コードに依存してデータ構造内の適切な場所にプッシュしますか？データに対するマークアップの比率はどれくらいですか？解析するのはどれくらい重いですか？
3. 保存場所：DB/フラットファイル/...？
4. インクリメンタルローディング：可能ですか？

考えられる戦略の1つ：最も頻繁に使用される1,000個（またはそれ以上）の単語を使用して、「最も一般的な単語」辞書を作成して永続化します。起動時にこれらの単語をトライにロードし、別のスレッドに完全な辞書のロードを生成します。新しい単語が読み取られると、作成されたトライに段階的に追加されます。

• 長所：ユーザーは起動時間が速くなります。
• 短所：クロススレッド同期が必要な場合があります。ロードが完全に完了するまで、ユーザーには不完全なトライが表示されます。これは、トライが何に使用されているかによって、ショートッパーになる場合とそうでない場合があります。

Answer 2

最近、パフォーマンスが遅く、シリアル化/逆シリアル化の時間が遅いため、同様のデータ構造をリファクタリングしました。

私の解決策は、トライを完全に破棄し、ネイティブの.NETコレクション（辞書とルックアップ）を使用することでした。

私は約40万語を扱っています。メモリからデータ構造を構築するのに約5秒かかります。データ構造は、多数の辞書とルックアップによってインデックス付けされたオブジェクトのリストです。

• 構造の最上位は Dictionary<int, var>、キーがn（検索語の文字数）であるaです。
• 辞書の各値はLookup<string, string>、キーがn文字の文字列であり、値はその文字列で始まるすべての文字列です。たとえば、キーの「st」値は「start」、「stop」、「string」の場合があります。

データ構造を作成するには、i = 1からmaxlengthまでの単語のリスト全体を繰り返し処理して、各iの'文字列で始まるすべての個別のルックアップを作成します。それらをトップレベルの辞書に接続すれば完了です。

これにより、カスタムビルドのトライが不要になります。パフォーマンスの違い（検索時間）はごくわずかでしたが、ロードの速度は私の設計に非常に有利でした（単純な.NETタイプを使用することの単純さと保守性は言うまでもありません）。

Answer 3

古いMFCバイナリ方式でシリアル化するだけです。基本的に、読み取り/書き込みは可能な限り高速である必要があります。残っているのは、入力時に構造を割り当てて初期化することだけです。これはとにかく行う必要があります。

つまり、トライのノードをシリアル化するには、次のようにします。

Read/Write number N of subnodes
For each subnode
  If reading, allocate a subnode in this node
  Read/Write the character for the subnode
  Serialize the subnode
End

編集：質問を読み直して、単語リストからトライを最初から作成したいですか？他の人が言ったように、プロファイリングしますが、古いプロファイラーだけではありません。彼ら全員があなたの問題を見つけるわけではありません。これが私がすることです。かかる時間は、ファイルの読み取りにかかる時間に加えて、構造の作成にかかる時間よりもはるかに長くすることはできません。