namazu-ml(avocado)
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Phrase search (Re: [Q] OpenText Style?)
- From: Rei FURUKAWA <furukawa@xxxxxxxxxxxxxxxx>
- Date: Fri, 22 May 1998 18:26:18 +0900
- X-ml-name: namazu
- X-mail-count: 00687
古川です。
>> 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