namazu-ml(avocado)

[Satoru Takabayashi <ccsatoru@xxxxxxxxxxxxxxxxxx>]

Rei FURUKAWA <furukawa@xxxxxxxxxxxxxxxx> wrote:

>(1) たぶん、ファイル単位で、単語の列を持っているのではないかと思われます。

えっと、ファイル単位で単語の並びを記録しておくと数百KBくらいあるテ
キストファイルの場合はいくら節約しても全体を調べるには結構コストが
かかりますよね。私としては「一致行の表示」の機能はいらなくて、せい
ぜい 4〜5単語のフレーズが検索できれば十分なのでファイル単位で記録
する必要性は感じません。


>(3) これを、どのようにインデクスファイルに記録するか、ですが、やはり、
>    単語そのままではなく、番号をつけて記録したほうが効率はよいでしょう。
>    問題は、
>        単語の番号を、いつ、どのようにつけるか
>    ということです。

この問題をさっぱり忘れていました。


>(5) よって、番号はインデクスを作成しながらつける、ということにしたいです
>    から、「出現順」ということになるでしょうか。

「出現順」を記録するためには単語をキーとした巨大なハッシュが必要に
なりませんか? 10万語とかになるとかなりきつそうです。


>    フレーズ検索しようとするとき、侯補となるファイルは、既に and 検索
>    などで、その単語が存在することは分かっていて、並びが合うかどうか
>    調べるだけなのだから、それほど厳密にやらなくても、よいのではないか、

そうです。並びを確かめたいだけなのです。どうせ AND検索でそれぞれの
語がすべて含まれていることが分かっているのだから、精度を多少犠牲に
してフレーズ用インデックスのサイズを減らすことが可能なのですね。気
付きませんでした。

# 古川さんのご意見はいつも示唆に富んでいて感心してしまいます。


>    まずいケースとして、'yamamoto' と 'suzuki' のハッシュ値が同じだった
>    場合に、'suzuki taro' と 'yamamoto' が存在する文書もヒットしてしま
>    うことになりますが、ハッシュ値が一致する語の確率は 0.4% くらいです
>    し、ヒット数が増える方向のエラーなので、実際には問題にはならないの
>    ではないか、と思います。

語からハッシュを計算すれば「番号」をどうするかという問題がなくなり
ますね。素晴らしいです。あ、でも1/256 = 0.4% ではありますが「ハッ
シュ値が一致する語の確率は 0.4%」は違うような気がします。大きいファ
イルは衝突しやすいとか、語の頻度が関係してくると思います。たとえば 
"the" と "yamamoto" のハッシュ値が同じだったら? のように。

それはともかく 8bit * 8bit の表を作れば二つの単語によるフレーズが
ある程度の精度で調べられますよね (個々の単語のAND検索は済んでいる
ので)。で、それを重ねていけば 3, 4, 5...語のフレーズ検索もできそう
です。どの程度の精度が出るかは計算できません (私には無理)。

そんなわけでサイズを具体的に計算してみると、ファイルの数が 2,048, 
一ファイルあたりの隣接する 2単語のハッシュの組合わせが平均 512とし
て

   256 * 256 * 4 =   256 KB  # seek用のインデックス
+  256 * 256 * 4 =   256 KB  # fread & malloc用にIDの数を記録
+ 2048 * 512 * 4 = 4,096 KB  # ファイルのIDの記録する領域
----------------------------
                   4,608 KB

と 4.5MBになります。この程度なら及第点なのではないかと思います。こ
れは単純に計算しただけで、しかも私は混乱しているので間違っている可
能性が高いです。実現できるかも不明です。コメントを頂けると助かりま
す。

--
高林 哲 Satoru Takabayashi