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" という部分文字列を探索(二分探索)して出現位置を返却

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.<String>;
  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.<String>(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.<String>, 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);
  }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

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.<String>;

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.<String>(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.<String>, 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);

}

* 実行結果

a
abra
abracadabra
acadabra
adabra
bra
bracadabra
cadabra
dabra
ra
racadabra

index: 3

abra

abracadabra

acadabra

adabra

bra

bracadabra

cadabra

dabra

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

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: actionscript, algorithm

Rest Term

ActionScriptでSuffix Array

あわせて読む:

Comments