テキストの分割アルゴリズム
今、WHAT[?]*1の為に検索アルゴリズムを考えている。そのために避けて通れないのが、テキストの分割アルゴリズムだ。要するに速く検索するためにテキストを適切に分割しインデックスを作製するのだが、この分割の方法で検索の精度、速度、データサイズなどが変わってくる。
代表的な全文検索システムであるNamazu*2では形態素解析によってテキストを分割する。例えば『お気に入りのセーターでぬくぬくと温まる』という文章を形態素解析すると次のようになる。
お気に入り・の・セーター・で・ぬくぬく・と・温まる』
もう１つの全文検索システムであるAkao*3ではN-Gramという手法でテキストを分割する。N-Gramとはテキストを単純にN文字毎に区切る手法だ。先ほどと同じ例でN-Gram（N=2とする）を実演すると次のようになる。
お気・気に・に入・入り・りの・のセ・セー・ータ・ター・ ーで・でぬ・ぬく・くぬ・ぬく・くと・と温・温ま・まる
この二つの手法がデータ変換研究所によって評価され、公開されているので*4、一部引用してみる。
テキストファイルのインデックス処理時間・インデックスサイズの比較（10000ファイル・計505MBに対する処理）。
『全文検索システムAkaoの検索手法と性能評価』より
system run time index size Akao 55分22秒 197MB Namazu 11時間8分22秒 145MB
まぁ、想像通りの結果だろう。形態素解析は辞書を見ながら"解析"する処理だが、N-Gramは機械的に分割しているだけだからダントツで速い。逆に最初の例文を見れば分かるようにデータサイズはN-Gramの方が大きい。個人的にはN-Gramのデータサイズが小さすぎる用に思える。やはりなんらかのフィルタリングをしてノイズを省いてるのか？
もう１つの特長として形態素解析では検索洩れが出るのに対して、N-Gramではでない。同時に、N-gramではノイズが多くなる（らしい）。最初の例文を見れば分かるように変なところで区切るから仕方がない。
で、思いついた事がある。まだ実験・検証をしてないのでただのアイディアなのだが…。
N-Gramの分割例を見た感じ、とても嫌な分割箇所がある。それは『りの』『のセ』『と温』などだ。これは形態素解析の例文を見ると分かるように形態素と形態素の間にあたる。ならば、これを排除すればデータ縮小・ノイズ軽減が出来そうだ。そのために分割を次のようなアルゴリズムで行なえば良い。
実際に最初の例文を試してみた。
お気・気に・に入・入り・セー・ータ ター・ぬく・くぬ・ぬく・温ま・まる
これにより単純なN-Gramでは18個に分割されるのに対して、12個ですんでいる。さらに、形態素解析・N-Gramと順番に行なうだけなので方法もシンプルだ。
こんな方法はどうだろうか？
[おまけ]
上記の方法で分割した後で（同一形態素内での）出現順序を元に重みづけを行なう。例：
# 括弧内が点数 お気（10）・気に（9）・に入（8）・入り（7）
これはまったくの思いつき。根拠もない。が、思いついて理由はある。『正規表現』『表現力』の二つの語を形態素解析するとそれぞれ『正規・表現』『表現・力』となる。このとき、『表現』を検索したときに
正規（10）・表現（9）：2語目にマッチしたので、9点 表現（10）・力（9）：1語目にマッチしたので、10点
となり、『表現力』の方が上に来る。『表現』に対する結果としてはおそらく直感的な結果だと思う。
都合の良いシチュエーションであることは理解している。こうならない場面も多いだろうが、頭にいれておく価値はあるかも。
*1:WHAT[?]プロジェクト：http://what.sourceforge.jp
*2:Namazu：http://www.namazu.org
*3:Akao：http://www.dehenken.co.jp/products/Akao.akao.html
*4:全文検索システムAkaoの検索手法と性能評価：http://lc.linux/or/jp/paper/lc2003/CP-03.pdf
