Sphinx  Suffix Arrayのローカライズへの応用

最近、『ソフトウェアの匠』(日経BP社)という本で Suffix Array という全文検索技術を知りました
(http://0xcc.net/pub/nb-2004-01/)。

形態素解析型やn-gram方式ともまったく違う、検索漏れが一切発生しないという
興味深い技術で、ゲノム情報の検索・抽出のための文書解析技術としても応用されているそうです。
「検索漏れのない全文検索システム」であるならば、翻訳者が辞書や用語集を検索する作業に応用することもできるのでは
と考え、詳しく調査することにしました。Sphinxは、この本の著者が作成したsaryという、unix上で動作する
プログラムに強い影響を受けて開発したものです。SphinxはWindows用のソフトでGUIインターフェイスです。

ソースコードを見比べながらの移植ではなく、上記文献を基に独自の解釈で実装したものなので、
仕様が一部異なることを含め、sary に比べると、まだまだ改良の余地はあります。
特に、索引構築時には、膨大な量のデータ（100万行のテキストファイルだと、
数千万件規模になる）をソートするプロセスが伴いますが、そのプロセスに歴然とした差があります。

sary が、「分割ソート」と「マルチスレッド」を組み合わせ、比較的低スペックのマシンでも索引を構築できるのに対し、
sphinxはシングルスレッドで、単にクイックソートを使ったものなので、低スペックのマシンで大きなテキストファイル
を索引化しようとすると、OutOfMemoryエラーになります。

【参考】 http://homepage3.nifty.com/DO/suffix_array.htm

●Suffix Arrayとは
ゲノム情報の検索・抽出のための文書解析技術としても応用されている

●特長
・サイズの大きなテキストファイルから目的のキーワードを高速に検索できる
・検索は二分探索で行うため高速
・検索漏れがない、基本的にどの文字位置からでも検索できる  
・検索ヒット位置を基準に前後の文脈を簡単に取得できる

●欠点
・インデックスの作成コスト（メモリ使用量と時間）が大きい
・１つのテキストファイルに対してしか検索できない
・エントリの追加/削除ができない。テキストデータに変更が生じた場合は、
最初から索引を構築しなおす必要がある。

●ローカライズに応用することによって何が得られるか
・前後文脈を得ることができる
・検索が極めて高速であるため、PDICのようなインクリメンタル検索が可能
（つまり、[検索]ボタンをいちいち押さなくてよい）  

●具体的には？
たとえば、「いろはにほへとちりぬるを 」というテキストがあったら、
文字列の末尾に到達するまで１文字ずつずらしながら接尾辞を作成する

 いろはにほへとちりぬるを
ろはにほへとちりぬるを
はにほへとちりぬるを
にほへとちりぬるを
ほへとちりぬるを
へとちりぬるを
とちりぬるを
ちりぬるを
りぬるを
ぬるを
るを
を

●これをソートすると

いろはにほへとちりぬるを
ちりぬるを
とちりぬるを
にほへとちりぬるを
ぬるを
はにほへとちりぬるを
へとちりぬるを
ほへとちりぬるを
りぬるを
るを
ろはにほへとちりぬるを
を

●これで二分探索を使って高速検索できる

======以下Sphinxのソースコードより抜粋======

Public Sub BuildNewSphinxIndex() Implements ISphinx.BuildNewSphinxIndex
'テキストファイルを受け取り、そのソート済みサフィックス配列を返す
'サフィックス配列の生成後に再起動が必要(SA作成時点では、テキストファイル全体を小文字にするため)
Dim enc As System.Text.Encoding
enc = System.Text.Encoding.GetEncoding(SphinxEncoding)
Dim sr As New StreamReader(fn, enc)
sbText = New StringBuilder()
sr.BaseStream.Seek(0, SeekOrigin.Begin)
While (sr.Peek() > -1)
'SA作成時点では、すべて小文字にする
sbText.Append(LCase(sr.ReadLine()) & vbCrLf)
End While
sr.Close()
ReDim sa(sbText.Length - 1)
Dim ip As Integer 'インデックスポイント
For ip = 0 To sbText.Length - 1
sa(ip) = ip 'クラスモジュールレベルの変数に格納
Next
Dim cmp As New SuffixArrayComparer(sbText)
Array.Sort(sa, cmp)
SaveSuffix(indexfile)
End Sub

==========================================
*抜粋コードなので、これだけでは動作しません。

比較は、１文字単位で制御文字（改行など）に到達するまで行う。 
したがって、検索時には、制御文字をまたいで検索することはできない。
たとえば、複数行をキーワードとして検索することも不可。

*なお、この制限は文字列の最後まで比較すれば回避できる。saryもそのように
しているかもしれない。当初は、Sphinxもそのようにしていたが、ソートにあまりに
時間がかかりすぎること、また、翻訳者が用語集を検索する際、
制御文字をまたいで検索することは希であると考え、制御文字で比較が終了する仕様を採用した。

 SuffixArrayは実装が簡単であるという特長があるが、
インデックスの作成コストを抑えるためには工夫が必要。
現在では、ソート方法を色々工夫することによって高速化する手法が研究されている。

【Sphinx のインストール/アンインストール】 

インストーラはありません。任意のディレクトリにsphinx.exeを格納してください。
また、レジストリも使っていないので、アンインストールする場合はディレクトリごと削除するだけでOK。

【要件】

CPU:  Pentium4 3.0GHz 
Memory: 1GB 以上を推奨。

上記のスペックで最大150MBのテキストファイルまでは索引作成可能と思われる。
たとえば、約80Mの英辞郎(v81)をインデックス化すると、
Pentium4 3.0GHz + メモリ１G のマシンで30分ぐらい

【Sphinx の使い方】

対象のテキストファイル、およびインデックスの作成ディレクトリを指定し、
[索引読み込み] をクリックすると、既存のインデックスが読み込まれる。

*既存のインデックスが存在しない場合は、インデックスが新規作成される。
完了したら再起動して [索引読み込み] をクリックする。