マイナス×マイナス

メンヘラ人工知能エンジニアのブログ/ 博士(工学)

眠れないので今更 Suffix Array の話でもかくか

 いま、Suffix Arrayを使って新しい手法を作ろうと画策している。基本的には、Katsuradaらの手法 (PDF)の応用である。しばらくは、既存の知識の応用で成果を出していく。もちろん、何に応用するかは言えない。

 この手法はSuffix Arrayをつかって、音声検索語検出を高速に行うものである。Suffix Arrayについては検索すればいくらでも詳しい情報が得られるため、詳説しない。大雑把にいうなら、巨大なドキュメントに対してインデックを貼りまくって、二分探索する感じである。メモリ効率を犠牲にして高速化を行う、現代的なアルゴリズムだ。

 Suffix Array自体の構築方法としては、Induction Sort(IS)と呼ばれる手法が高速である。詳細は以下の文献を参考にしてほしい。

Nong, G., Nong, G., Zhang, S., Zhang, S., Chan, W. H., & Chan, W. H. (2008). Two Efficient Algorithms for Linear Suffix Array Construction. Draft, 60(October), 25

実装については,sais が良いとのことである。

 この後、ごにょごにょして性能が上がると予測している。