namazu-ml(avocado)


[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Phrase search (Re: [Q] OpenText Style?)



古川です。

>> On Wed, 20 May 1998 18:34:19 +0900, Satoru Takabayashi <ccsatoru@xxxxxxxxxxxxxxxxxx> said:
  > えっと v1.1.2.3 は基本的にバグ修正版なので
  >> というのも、今度のは NMZ.f のフォーマットが変わるということで、pnamazu
  >> では、そのままではちょっと不都合なのです。
  > という心配はないです。基本的に以前と同じ仕様です。

早合点でした。失礼しました。



話はかわって…

>> On Fri, 22 May 1998 14:22:55 +0900, Satoru Takabayashi <ccsatoru@xxxxxxxxxxxxxxxxxx> said:
  > フレーズ検索の実装に関して何かアイディアがあったら教えてください。


おおもとのメールで紹介されていた、

>> On Thu, 21 May 1998 16:19:30 +0900, chida@xxxxxxxxxxxxx (CHIDA Makoto) said:
  >   最近、学術情報センター(http://wwwsoc.nacsis.ac.jp/)の	
  > 検索エンジン NACSIS SITE SEARCH
  >      http://www.rd.nacsis.ac.jp/webindex/soc.html

  > 1.http://wwwsoc.nacsis.ac.jp/jssst/okamura-thesis.html (Size: 3713)
  >       Dr. Hideaki Okamura // 日本ソフトウェア科学会ニューズレター / 博士論文紹


が、どのようになっているかを想像しながら、考えてみます。おおざっぱですが、
御容赦下さい。

例として、[namazu:00681] (2.6Kb) を使ってみます。

(1) たぶん、ファイル単位で、単語の列を持っているのではないかと思われます。
    これを、namazu でやるとして、kakasi -w の結果をそのまま持つと、

        chida@xxxxxxxxxxxxx (CHIDA Makoto) wrote: なぜ 、 " 一致 行の
        表示 " があると 便利 かなということを 補足 しますと 、 例えば
        、 paper の 検索 などで 、 "yamakawa taro" さんを 探し たいとき
        yamakawa & taro で 検索 すると "yamakawa ***" さんと "*** taro"

            (以下略)

    となります。


(2) このままだと、ファイルをそのまま持っているのと変わらないので、ここで、
    「必要なさそうなものは削る」という割り切りが必要になるでしょう。
    例えば、「記号は削る」とか「ひらがなだけの語は削る」。すると、

        chida ywt tdk co jp chida makoto wrote 一致 行の 表示 便利 補足
        例えば paper 検索 yamakawa taro 探し yamakawa taro 検索 yamakawa
        taro 含ん ファイル 全部 yamakawa taro 時 一致 行の 表示 便利
        思った 次第 yamakawa taro フレーズ 検索 実装 方法 今 インデックス

            (以下略)

    これでだいたい 250 語/1Kb くらいになります。

    もっと削りたければ、検索クライアントでも実現できるルールならば追加
    できます。

    例えば「数字だけの語は削る」「1 byte 1 文字だけの語は削る」「ひら
    がなを含む語は削る」など、いろいろなルールをつけていくと、

        chida ywt tdk co jp chida makoto wrote 一致 表示 便利 補足 paper
        検索 yamakawa taro yamakawa taro 検索 yamakawa taro ファイル 全部
        yamakawa taro 時 一致 表示 便利 次第 yamakawa taro フレーズ 検索
        実装 方法 今 インデックス 必要 インデックスファイル サイズ 分

            (以下略)

    これだと 200 語/0.9Kb くらいになります。


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


(4) 番号をコード順につけるとすると、辞書に載っている語はともかく、1 バイト
    文字列やカタカナ語は、あらかじめどんな語があるか分からない、という問題
    があります。つまり、コード順にしようとすると、インデクスを作成した後で、
    単語に番号をつけてから、もういちどファイルを調べなければならなくなりま
    す。


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

    そうすると、単語と番号の対応表が必要になります。とくに、検索時のことを
    考えると、「単語 -> 番号」のテーブルが欲しくなります。
    (これは NMZ.i に埋めこむようなかたちになるかな)


(6) そして、語数ですが、short に収まるとは限りませんから、long にすると、
    この例では 200 * 4 = 800 バイトになります。


(7) ここまでの話をまとめると、必要な容量は、
        「単語->番号」テーブル      語数 * 4
        フレーズ用インデクス        2.6Kb に対して 800 バイトだから、
                                    約 3 割くらいか


(8) 十分な資源があるところならば、これでも実現可能でしょうが、
    さらに節約するには…

    フレーズ検索しようとするとき、侯補となるファイルは、既に and 検索
    などで、その単語が存在することは分かっていて、並びが合うかどうか
    調べるだけなのだから、それほど厳密にやらなくても、よいのではないか、
    単語と番号が 1 対 1 に対応しなくても、単語から、8 bit くらいの
    ハッシュを計算してやって、フレーズ用インデクスにもそれを記録して
    やればよいのではないか、と思います。(一致行表示はできなくなりますが)

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

    この場合

        「単語->番号」テーブル      不要
        フレーズ用インデクス        2.6Kb に対して 200 バイト

    となります。



さらに話がかわって & 細かい & 古い話で恐縮ですが…

>> On Mon, 11 May 1998 19:46:32 +0900, Satoru Takabayashi <ccsatoru@xxxxxxxxxxxxxxxxxx> said:

  >> または、「先頭文字は 'M' しか認めない」とか。
  > これはお手軽で良いですね :-)。

ということで、

                    $uuin = $uuord, next if $line =~ /^M[\x21-\x60]+$/;

としましょう。

-- 

                                        ヤマハ(株)ピアノプレーヤ設計課
                                                              古川 令
                                             furukawa@xxxxxxxxxxxxxxxx