ActionScriptでSuffix Array

今回は画像処理ではなく文字列処理について。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” という部分文字列を探索(二分探索)して出現位置を返却

[as]
package {
import flash.display.Sprite;
import flash.events.*;
import flash.net.URLLoader;
import flash.net.URLRequest;

public class Test extends Sprite {
private var sa:SuffixArray;
private var urlLoader:URLLoader;

public function Test() {
urlLoader = new URLLoader();
urlLoader.addEventListener(Event.COMPLETE, completeHandler, false, 0, true);
urlLoader.addEventListener(IOErrorEvent.IO_ERROR, errorHandler, false, 0, true);
urlLoader.load(new URLRequest(“data.txt”)); // abracadabra
}
private function completeHandler(e:Event):void {
sa = new SuffixArray();
var substring:String = “ac”;
sa.addEventListener(SuffixArray.BUILD_COMPLETE, function():void {
trace(sa);
trace(“\nindex: ” + sa.search(substring));
}, false, 0, true);
sa.build(e.target.data, SuffixArray.QUICK_SORT);
}
private function errorHandler(e:IOErrorEvent):void {
trace(e);
}
}
}

import __AS3__.vec.Vector;
import flash.events.Event;
import flash.events.EventDispatcher;
import flash.utils.getTimer;

class SuffixArray extends EventDispatcher {
public static const BUILD_COMPLETE:String = “build_complete”;
public static const QUICK_SORT:String = “quicksort”;
private var suffixes:Vector.;
private var len:int;
private var _time:Number;

public override function toString():String {
return suffixes.join(“\n”);
}
/**
* search substring, using binary search O(mlogn)
*/
public function search(substring:String):int {
if(len == 0) return substring.length == 0 ? 0 : -1;
var low:int = 0, high:int = suffixes.length – 1;
while(low < high) { var middle:int = low + (high - low)/2; if(suffixes[middle] >= substring) high = middle;
else low = middle + 1;
}
if(suffixes[high].indexOf(substring, 0) == 0) {
return len – suffixes[high].length;
}
return -1;
}
/**
* build Suffix Array, O(n^2logn)
*/
public function build(str:String, sortFunc:String = null):void {
try {
_time = getTimer();
len = str.length;
suffixes = new Vector.(len, true);
for(var i:int = 0; i < len; i++) { suffixes[i] = str.substring(i); } this[sortFunc](); _time = getTimer() - _time; dispatchEvent(new Event(BUILD_COMPLETE)); }catch(e:ReferenceError) { suffixes.sort( function(x:String, y:String):int { return x > y ? 1 : x < y ? -1 : 0; } ); _time = getTimer() - _time; dispatchEvent(new Event(BUILD_COMPLETE)); } } public function get time():Number { return _time; } /** * apply Quick Sort */ private function quicksort():void { _quicksort(suffixes, 0, suffixes.length - 1); } private function _quicksort(data:Vector., low:int, high:int):void {
if(low > high) return;
var i:int = low + 1, p:int = low, c:int = int((low + high)/2), pivot:String = data[c];
data[c] = data[low];
while(i <= high) { if(data[i] < pivot) { var tmp:String = data[++p]; data[p] = data[i]; data[i] = tmp; } i++; } data[low] = data[p]; data[p] = pivot; _quicksort(data, low, p - 1); _quicksort(data, p + 1, high); } } [/as] * 実行結果

a
abra
abracadabra
acadabra
adabra
bra
bracadabra
cadabra
dabra
ra
racadabra

index: 3

ここで、テキスト圧縮技術の評価によく用いられる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

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

あわせて読む:

• ByteArrayキャッシュ
• Consistent Hashing in AS3
• AS3で関数のカリー化
• ハイパス/ローパスフィルタ
• WebカメラでVTR調フィルタ