Rest Term

ActionScriptでSuffix Array

Pocket

今回は画像処理ではなく文字列処理について。Suffix Arrayというデータ構造を扱います。

Suffix Array (接尾辞配列)は、もともと生物情報学の分野でゲノムデータベースの解析などに用いられてきたらしいのですが、そこからテキスト圧縮/検索などの自然言語文書を索引対象とした応用が広がり、全文検索エンジンの文字列索引(インデックス)としても利用されているデータ構造です。

Suffix(接尾辞)とは、索引対象となる文字列T内の任意の位置からTの末尾までの範囲の文字列のことで、Tの長さがNであればN個のSuffixが定義されインデックスが付与されます。Tの各Suffixは辞書順にソートされ、そのインデックスを配列にしたのがSuffix Arrayです。Suffixは辞書順にソートされているため、検索対象文字列をSuffix Array内で二分探索することにより、大規模テキストに対する高速な検索を可能にします。

Suffix ArrayのActionScriptでのコード例を示します。
1: "abracadabra" という文字列データが入ったファイルを読み込み、そのデータでSuffix Arrayを構築(クイックソート使用)
2: Suffix Array構築完了後、"ac" という部分文字列を探索(二分探索)して出現位置を返却

* 実行結果

ここで、テキスト圧縮技術の評価によく用いられるCalgary/Canterburyコーパス(書籍、ニュース、プログラムソースコード、ゲノム列(E.coli)などが含まれる)を用いてSuffix Arrayの構築時間を測ってみました。組み込みソート(Vector.sort())、クイックソート、マルチキークイックソート(Ternary Search Tree)での処理時間は以下の通りです(5回の計測時間の平均)。

* 環境:
Mac OSX 10.6.2: 2.26GHz / 2GB RAM
Flash Player: 10.0.45 (Debug)
Flex SDK: 4.0.0.14159

sorting time on texts (sec)
data size(byte) Vector.sort() QuickSort Multikey QuickSort
progc 39611 0.407 0.341 0.100
news 377109 5.022 4.285 1.323
book1 768771 10.819 9.958 3.144
world192 2473400 39.781 35.322 15.366
E.coli 4638690 Error #1502 Error #1502 29.258

4MB程度のデータ(E.coli)でも効率の悪いソート法だとFlash Playerがギブアップしてしまいます。。Suffix Arrayの欠点は構築に多くの時間がかかる点です。この問題を解決するためにマルチキークイックソートやMSD radix sort (基数ソート法, O(nlogn))、Two-Stage sort (二段階ソート法, O(n)) など数々の手法が提案されています。機会があればTwo-Stage sortあたりは一度書いてみたいなと思います。まぁでもFlashで大規模データは扱わないですよね。

Suffix Arrayは、整列(ソート)や探索、データ構造などをまとめて勉強できる教材として新人のC言語研修などに利用できるという話を聞きました。文字列配列を扱うのでポインタの勉強にも効果的かと。僕の所属部署では課題としては出ませんでしたが、検索事業などを持ってる部署ではN-gramと併せて課題の一つになってるみたいです。

あと、Suffix Arrayの構造を理解する為の小さなコードをwonderflに投稿しておきましたのでもし興味があれば。
Suffix Array | wonderfl build flash online

* 参考
CiNii 論文 - Suffix arrayの効率的な構築法
Sorting and Searching Strings

あわせて読む:

 

Tags: ,

Comments

No comments so far.

  • Leave a Reply
     
    Your gravatar
    Your Name