[Namazu-devel-ja 742] Re: フレーズ検索って N-gram ですよね

[Tadamasa Teranishi]

寺西です。

# 別に N-gram じゃなくてもいいんですけどね。

NOKUBI Takatsugu wrote:
> 
> At Fri, 18 Nov 2005 02:53:11 +0900,
> Tadamasa Teranishi wrote:
> > ふと思ったんですが、フレーズ検索って N-gram ですよね。
> 
>   うーん、N文字単位で単語をオーバーラップしながら区切っていかないと
> N-gramベースとは呼べないような気がします。

グラムは別に文字でなくても、単語でも良いのです。
だから、N単語単位で文字列をオーバーラップしながら区切るので、大丈夫
じゃないですか?

> > Namazu のフレーズ検索だと、2つの単語からハッシュを算出しますから、
> > bi-gram ということになりますか。
> 
>   区切る単位が2文字づつなのがbi-gramなので、Namazuのフレーズ検索はそれ
> とはちょっと違います。

そこも、文字ではなく単語単位なら、2単語ずつ分けるので bi-gram に
なるはずです。

参考になる良い資料がないのですが、(というか見失ったのですが)
例えば

http://uluru.lang.osaka-u.ac.jp/~k-goto/ngrammer.html

とか。
たぶん単語N-gramと一般的に呼ばれるものになるのかと思います。

もっとも、N-gram モデルをベースに設計したわけじゃなくて、後づけ
にはなるのですが。
  
>   N-gramが関係ない文字列を含みやすいのは、ある単語中の部分文字列や、複
> 数の単語をまたがった部分文字列に検索式がマッチすることがあるためからで
> す(たとえば「Namazuはこの先生きのこることができるか」に「先生 & きのこ」
> がマッチする)。

これは "京都" で検索して "東京都" が見つかる問題ですよね? 
単語単位でグラム分けすると、これはなくなります。

>   対して、Namazuのフレーズ検索はhashを使っているので衝突が起きる可能性
> がある、ということなので「ごみが出やすい」という点では同じですが、起き
> る原因に違いがあります。

確かに。

また、こちらよりは

> > Namazu では文字(単語)の文書中の位置は記録していません。このため
> > N-gram での検索結果から位置による絞り込みはできませんから、やっぱり
> > ゴミが多すぎてダメですかね。

こっちの理由によるゴミの方が問題になるかとは思います。
"foo bar baz" で検索すると "foo bar" と "bar baz" を含む文書もヒット
してしまうというものです。

文字単位の N-gram ベースの検索エンジンだと、
"あいう" で検索して、"あい" と "いう" を含む文書はヒットしないで
しょうから。

> では、分かち書きをせずに文字単位の N-gram でインデックスを作れば、
> 転置インデックス型ではあるが巷の N-gram ベースの検索エンジンぽく
> なったりしませんかね?

こっちは意外と簡単にテストできました。それはまた別メールで。
-- 
=====================================================================
寺西 忠勝(TADAMASA TERANISHI)  yw3t-trns ＠ asahi-net.or.jp
http://www.asahi-net.or.jp/~yw3t-trns/index.htm
Key fingerprint =  474E 4D93 8E97 11F6 662D  8A42 17F5 52F4 10E7 D14E