読者です 読者をやめる 読者になる 読者になる

高速文字列解析の"別"世界

NLP

1月に「高速文字列解析の世界」を購入してから半年が経ちました。以下、文字列本と呼びます。

高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)

高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)

全文検索として、「CSA」や「FM-Index」が紹介されていますが、「全文検索システム」を作るには、これらだけでは不十分です。なぜなら、以下のような特徴があるからです。

  • 文書IDの識別が遅い。
  • 各文書IDに出現する頻度を求めるのが遅い。

ちなみに、転置インデックス(or N-gramインデックス)を使った場合、これらの処理は高速ですね。

インデックスを圧縮しているのだからしょうがないとも考えられますが、作りたいですよねぇ、「全文検索システム」。このあたりなんとかならんか~って思いますよねぇ。

ひとつは、「文字列本」の最終章でちょっと紹介されているように、ウェーブレット木を使う方法があります。詳細は、「文字列本」に譲りますが、文書IDを昇順、降順、頻度付きで返すことができます。また、頻度が多い順にTop-K件も返せます。ただし、これも万能ではありません。というのも、作ってみればわかりますが、「CSA」とか「FM-Index」に比べてサイズが大きすぎるんです。圧縮タイプのウェーブレット木でも問題は解決されません(Grammarベースなら解決できるか?)。その理由は、テキストは、BWTにより、同じ文字が並びやすくなりますが、文書IDは、同じ文書IDがあまり繰り返されたりしないからです。

このぐらいのことは、世界中でみんな考えているようで、いろんな研究があるようです。ただ、私は、途方に暮れました。いろんな研究があることはわかったんですが、何から読めばいいのやらって感じです。いろいろ乱読しましたが、鬼畜な論文も多く、具体例を重視する私には、理解不能なものもたくさんありました。

そんな中、良い論文を見つけました。神です。Navarro神です。

Spaces, Trees and Colors: The Algorithmic Landscape of Document Retrieval on Sequences
Gonzalo Navarro, arxiv, 2013.

http://arxiv.org/abs/1304.6023

文書IDをどうやって高速に求めるか、頻度付きで求めるにはどうするか、重要な順に求めるにはどうするか、ということがたくさんのアルゴリズムの例とともにまとまっています。現時点の最新の研究までカバーされています。Navarroのストーカーをしといて良かったです。

この論文は、「高速文字列解析の世界」の別世界にある隠しダンジョンみたいなものです。つまり、本編をきちんとクリアしていないと一瞬でやられます。ウェーブレット木とかCSAとかFM-Indexとかは知ってて当たり前レベルで話が進みます。攻略には苦労しますが、「全文検索アルゴリズム」から「全文検索システム」にかなり近づけます。

あと、半年は、世界を冒険できそうです。