Suffix Arrayは何が画期的だったのか?

以下は、計算機科学者でなくても直感的に理解できると思います。

1. ソートされていない通常のデータの中にあるサブデータ(キー)を検索しようとすると、データの大きさに比例した時間(O(n))がかかる。
2. ソート済みのデータであれば、二分探索でデータの大きさの対数時間(O(logn))でキーを検索できる。
   1. さらにキーからIDを定数時間で作成できれば(これをやるのがハッシュ関数)、そのIDを添字にした配列アクセスによりデータの検索は定数時間(O(1))でできる(ハッシュテーブルの原理)。

だとしたら、何らかの形で全文字の出現位置をソートしておけばO(log(n))やO(1)で全文検索できるんじゃね?

その「何らかの形」が、Suffix Arrayというわけです。

論より証拠

というわけで実際にSuffix Arrayを作ってみましょう。やるべきことは二つだけ

• 全文字の出現位置の入った配列を作って
• それを辞書順にソートする

この配列は全文字の出現位置から最終文字までの文字列、つまり全接尾辞(suffix)の配列をソートしたことに相当します。よってSuffix Arrayというわけです。

SuffixArray = function(str, endch) {
    if (typeof(str) !== 'string') throw TypeError();
    if (endch) str += endch;    /* for BWT */
    /* always new */
    if (!(this instanceof SuffixArray)) return new SuffixArray(str);
    var sa = [],
        i, l;
    /* make an index that holds the location of every single character */
    for (i = 0, l = str.length; i < l; i++) sa.push(i);
    /* and sort it lexicographically */
    sa.sort(function(a, b) {
        /* there is no === case for suffix arrays! */
        return str.substr(a) < str.substr(b) ? -1 : 1;
    });
    this.str = str;
    this.sa  = sa;
};

「こんなんでいいの?」ってぐらい簡単な考えに感嘆せざるを得ません。

で、たいていのSuffix Arrayの説明はここで終わってしまっているのですが、肝心の検索が「あまりに自明」なのか端折られています。きちんとやることにしましょう。

幸いにして一般化した二分探索を以前実装したので、それをそのまま使うことにしましょう。

SuffixArray.prototype.prefixSearch = function(key, nosort) {
    if (typeof(key) !== 'string') throw TypeError('give me a string!');
    var str = this.str;
    var bs = bsearch(this.sa, key, function(a, b) {
        var as = str.substr(a, b.length);
        return as === b ? 0 : as < b ? -1 : 1;
    });
    var ret = bs.found ? this.sa.slice(bs.head, bs.tail + 1) : []
    return nosort ? ret : ret.sort(function(a, b){return a - b});
};

ここでnosortを指定しない場合最後に検索結果をさらにソートしているのは、Suffix Arrayにあるのはあくまで接尾辞を辞書順にソートしたものなので、出現位置順になっていないからです。別のいい方をすると、線形探索した場合と同じ結果を返すようにするということです。

linearPrefixSearch = function(str, key) {
    if (typeof(key) !== 'string') throw TypeError('arguments[0]');
    if (typeof(key) !== 'string') throw TypeError('arguments[1]');
    if (!str || !key) return [];
    var ret = [],
        idx = 0;
    while(true) {
        idx = str.indexOf(key, idx);
        if (idx < 0) return ret;
        ret.push(idx);
        idx += key.length;
    }
};

ついでにBWTの相互変換もサポートすることにしておきますか。コードは基本的にWeb+DB PRESS Vol. 42の岡野原さんの記事をJavaScriptに移植しただけのものです。Perl版はすでにだいぶ前に某社の元CTOが書いてます。総集編をHDDに入れておけばこれまたいつでも全文検索できるので超便利。

SuffixArray.prototype.bwt = function() {
    var str = this.str;
    return this.sa.map(function(v) {
        return str[v - 1] || str[str.length - 1];
    }).join('');
};

var NCHAR = 0x10000; /* NOT 256 in JavaScript! */

SuffixArray.ibwt = function(bwt, endch) {
    if (!endch) endch = '\u0000';
    var counts = [], LF = [], ibwt = [],
        i, l, cc, next = -1;
    for (i = 0, l = NCHAR; i < l; i++) counts[i] = 0;
    for (i = 0, l = bwt.length; i < l; i++) {
        if (bwt[i] === endch) next = i;
        counts[bwt.charCodeAt(i)]++;
    }
    for (i = 1, l = NCHAR; i < l; i++) counts[i] += counts[i - 1];
    for (i = bwt.length - 1; i >= 0; i--) {
        LF[--counts[bwt.charCodeAt(i)]] = i;
    }
    for (i = 0, l = bwt.length; i < l; i++) {
        next = LF[next];
        ibwt.push(bwt[next]);
    }
    return ibwt.join('');
};

Test

では、テストしてみましょう。

var s  = 'The quick brown fox jumps over the black lazy dog',
    sa = SuffixArray(s);
p('fox', sa.prefixSearch('fox'));
p('dog', sa.prefixSearch('dog'));
p('dan', sa.prefixSearch('dan'));
p('linearPrefixSearch(s, "o")', linearPrefixSearch(s, 'o'));
p('      sa.PrefixSearch("o")', sa.prefixSearch('o'));
p('sa.PrefixSearch("o", true)', sa.prefixSearch('o', true));
'abcdefghijklmnopqrstuvwxyz'.split('').forEach(function(k){
    p(k + ':');
    sa.prefixSearch(k).forEach(function(at){
        p('  ' + at, JSON.stringify(sa.str.substr(at)));
    });
});
sa = SuffixArray(s, '$');
p(sa.bwt());
p(SuffixArray.ibwt(sa.bwt(), '$'));

確かに期待通り動いているようです。

Demo - 実際に全文検索してみる

やはりプログラムというのは使ってなんぼ。ということで実際に全文検索してみることにしましょう。

JavaScript

demosa = undefined; /* intentionally global */
incrementalSearch = function(keyelem, dstelem) {
    if (!demosa) return;
    var key = keyelem.value,
        str = demosa.str,
        prefixes =  demosa.prefixSearch(key);
        /* prefixes = linearPrefixSearch(str, key); // works ok, too */
    if (key && prefixes.length) {
        var d = document,
            frag = d.createDocumentFragment(),
            prev = 0;
        prefixes.forEach(function(at) {
            if (prev < at) frag.appendChild(d.createTextNode(
                str.substr(prev, at - prev)
            ));
            var span = d.createElement('span');
            span.appendChild(d.createTextNode(
                str.substr(at, key.length)
            ));
            span.style.backgroundColor = '#ffcccc';
            frag.appendChild(span);
            prev = at + key.length;
        });
        frag.appendChild(d.createTextNode(
            str.substr(prefixes[prefixes.length - 1] + key.length)
        ));
        dstelem.innerHTML = '';
        dstelem.appendChild(frag);
    }else {
        dstelem['textContent' in dst ? 'textContent' : 'innerText'] = str;
    }
};

DHTML

以下のtextareaに全文検索したいテキストをペーストして、Make SAしてから全文検索したい語句をタイプしてみてください。なかなか楽しいです。

Benchmark

しかし速度はどうでしょうか?

結論から言うと

• 一旦Suffix Arrayを構築してしまえば、JavaScriptでも検索は確かに高速になる
  • しかし線形探索版と結果を一致させようとすると、二分探索した結果をさらにソートせねばならず、一致件数が多いとそのコストが重くのしかかる。
• ビルトインの比較ソートを使った現在の実装では、Suffix Arrayの構築コストが高すぎる
  • どんなアルゴリズムを使ってもSuffix Arrayの構築コストがO(n)以上なので、一回線形探索をするコスト以上のコストが必ずかかる。よって複数回検索しないと元を取ることができない

ということになるでしょうか。データの変更回数＜＜検索回数というのがSuffix Array(さらにはそれを Succinct Data Structure(簡潔データ構造)を使って表現したSuffix Treeなど)を用いた全文検索が生きるところ。辞書などにはうってつけです。

実はSuffix Arrayの一番のベネフィットは、基本的なアルゴリズムとデータ構造の理解を体得するのにこれ以上向いた題材は滅多にないということかも知れません。手でプログラムを書いてみれば探索とソートという二大問題が文字通り手に取るようにわかるようになります。そしてなぜプロ^2プログラマーたちがその高速化にやっきになっているかも。

というわけで、あなたもSuffix Arrayを再発明してみませんか?

Dan the Man with Too Many Things to Search

Auxiliary codes

bsearch = function(ary, val, cmp) {
    cmp = cmp || function(a, b) { return a === b ? 0 : a < b ? -1 : 1 };
    var head = 0,
        tail = ary.length - 1,
        here, that, h, m, t;
    while (head <= tail) {
        here = head + ((tail - head) >> 1);
        that = cmp(ary[here], val);
        if (0 === that) {   /* if found, binary-search the boundary */
            h = 0, t = here;
            while (h <= t) {
                m = h + ((t - h) >> 1);
                if (0 === cmp(ary[m], val)) t = m - 1;
                else                        h = m + 1;
            }
            head = h;
            h = here, t = ary.length;
            while (h <= t) {
                m = h + ((t - h) >> 1);
                if (0 === cmp(ary[m], val)) h = m + 1;
                else                        t = m - 1;
            }
            tail = t;
            return { found: true, head: head, tail: tail };
        }
        if (0 < that) tail = here - 1;
        else          head = here + 1;
    }
    return { found: false, head: tail, tail: head };
};

repeatString = function(str, n){
    return (new Array(n+1)).join(str);
};

timeit = function(l, f) {
    var i, started = Date.now();
    for (i = 0; i < l; i++) f();
    return Date.now() - started + 'ms';
}