ファイル内のキーへの高速アクセス（ファイル全体をメモリにロードせずに）

Question

背景：ファイルシステムの辞書から定義（科学）を検索するWindows Mobile用のC＃アプリケーションを作成しています。ユーザーが単語を入力して、できるだけ速く意味を得ることができる必要があり

Word1:Meanings(2) 
-meaning 1 bla bla bla 
-meading 2 bla bla bla 
[...] 

： ファイルは、この（ファイルが100K +のエントリを持っている）のように見えます。ユーザーは1語または2語のみを検索します。これを行うには、私はソートされたリストで実際の単語とバイトオフセットの辞書ファイルで2番目のファイルを作成しました。 例：

word1:12344 
word2:32241 
word3:298 

私は（すべてのラインを介して単純なループと等しい場合の比較）私の「インデックス」に目を通した後、「ランダム・アクセス」のバイト・オフセットを使用して辞書ファイル。 問題は、これはまだ遅いです。 インデックスを配列/リスト/ハッシュテーブルにロードしようとしましたが、遅いioのために、これは時間がかかりすぎて（インデックスのロードに約20秒かかる）。これは、ユーザーが一般的に1語だけを検索するため、悪いことです。 したがって、（インデックス全体を走査することなく）ファイル上で直接動作できるいくつかのタイプのn-tree実装を探しています。 誰かがこれを行う方法をアドバイスしていますか？ 新しいインデックスはこの形式になっています：

a:FileOffsetInDictionary:FileOffsetOf"ab" //the first 2 character starting with a 
b:FileOffsetInDictionary:FileOffsetOf"ba" 
c:FileOffsetInDictionary:0 //"0" means that their are no words starting with "c" (just for example) 
[...] 
ab:FileOffsetInDictionary:FileOffsetOf"aba" 
ac:FileOffsetInDictionary:878878 //(just some random values for illustration) 
[...] 
ba:FileOffsetInDictionary:456 
[...] 
aba:FileOffsetInDictionary:2342 
[...] 

と検索このように行われる：

Users enter the word "Tree" 
Look for "t" in index by looping through the index 
if "t" found then goto FileOffsetOf2Digit 
if "tr" found then goto FileOffsetOf3Digit 
[...] 
[actually recursively coded] 

Answer 1

を正しい答えは、おそらくになり 私の現在のソリューションは、この（ただし、バギーや汚れが）のように見えますこの性質のディスクベースのインデックスには理想的なb-treeインデックスを使用するように指示するか、モバイル6.5以前についてはSQL CEデータベースを使用する方がよいでしょう。そして、あなたはいくつかの実装を見つけることができますが、次のことができない場合は失敗します。

現在のインデックスファイルのアイデアの行に沿って何かを使用して、各インデックスレコードを固定サイズにします。したがって、単語が50文字以上にならず、オフセットが4バイトの整数に収まることがわかっている場合は、インデックスファイルに54バイトのレコードエントリを作成することができます。その後、ファイル全体をスキャンして各レコードにアクセスするのではなく、インデックスファイルに対してbinary searchを実行することができます。

Answer 2

これを自分で実装する必要がある場合は、コーパス全体のtrieを作成する必要があります。これは、既知のデータのBツリー、Red-Blackツリー、またはハッシュテーブルよりも高速で、部分一致を保存できます。私。それを "T"と呼ぶと、あなたのコーパスの文字 "T"の最初のインスタンスを返します。それを "r"で呼び出して "T"の最初のインスタンスを指定すると、最初に "T"を検索することなくコーパス内の "Tr"の最初のインスタンスを返します。