2008年07月10日

Suffix Arrayを用いた一致領域取得スクリプト

このエントリーをはてなブックマークに追加
follow us in feedly
javascriptだけで動きます。
以前作ったやつをもう一回見直しました。






diffコマンドみたいに、行レベルで差分を調べるわけではありません。
文字レベルで一致をみます 順序前後なんかは全く関係ありません。


コードはおそらく最適なものではありません。
また、計算量を減らすための前処理もしています。





これはsuffix arrayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
れはsuffix arrayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
はsuffix arrayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
suffix arrayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
uffix arrayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
ffix arrayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
fix arrayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
ix arrayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
x arrayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
arrayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
rrayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
rayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
ayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
yというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
というデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
いうデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
うデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
データ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
ータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
タ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
構造で実現できます。suffixつまり接頭辞とは、こういうことです。
造で実現できます。suffixつまり接頭辞とは、こういうことです。
で実現できます。suffixつまり接頭辞とは、こういうことです。
実現できます。suffixつまり接頭辞とは、こういうことです。
現できます。suffixつまり接頭辞とは、こういうことです。
できます。suffixつまり接頭辞とは、こういうことです。
きます。suffixつまり接頭辞とは、こういうことです。
ます。suffixつまり接頭辞とは、こういうことです。
す。suffixつまり接頭辞とは、こういうことです。
。suffixつまり接頭辞とは、こういうことです。
suffixつまり接頭辞とは、こういうことです。
uffixつまり接頭辞とは、こういうことです。
ffixつまり接頭辞とは、こういうことです。
fixつまり接頭辞とは、こういうことです。
ixつまり接頭辞とは、こういうことです。
xつまり接頭辞とは、こういうことです。
つまり接頭辞とは、こういうことです。
まり接頭辞とは、こういうことです。
り接頭辞とは、こういうことです。
接頭辞とは、こういうことです。
頭辞とは、こういうことです。
辞とは、こういうことです。
とは、こういうことです。
は、こういうことです。
、こういうことです。
こういうことです。
ういうことです。
いうことです。
うことです。
ことです。
とです。
です。
す。





次に、このようにして得られたSuffix を辞書順に並べ替えます。




arrayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
ayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
ffix arrayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
ffixつまり接頭辞とは、こういうことです。
fix arrayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
fixつまり接頭辞とは、こういうことです。
ix arrayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
ixつまり接頭辞とは、こういうことです。
rayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
rrayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
suffix arrayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
suffixつまり接頭辞とは、こういうことです。
uffix arrayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
uffixつまり接頭辞とは、こういうことです。
x arrayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
xつまり接頭辞とは、こういうことです。
yというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
いうことです。
いうデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
ういうことです。
うことです。
うデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
きます。suffixつまり接頭辞とは、こういうことです。
こういうことです。
ことです。
これはsuffix arrayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
す。
す。suffixつまり接頭辞とは、こういうことです。
つまり接頭辞とは、こういうことです。
できます。suffixつまり接頭辞とは、こういうことです。
です。
で実現できます。suffixつまり接頭辞とは、こういうことです。
というデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
とです。
とは、こういうことです。
はSuffix arrayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
は、こういうことです。
ます。suffixつまり接頭辞とは、こういうことです。
まり接頭辞とは、こういうことです。
り接頭辞とは、こういうことです。
れはsuffix arrayというデータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
タ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
データ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
ータ構造で実現できます。suffixつまり接頭辞とは、こういうことです。
現できます。suffixつまり接頭辞とは、こういうことです。
構造で実現できます。suffixつまり接頭辞とは、こういうことです。
辞とは、こういうことです。
実現できます。suffixつまり接頭辞とは、こういうことです。
接頭辞とは、こういうことです。
造で実現できます。suffixつまり接頭辞とは、こういうことです。
頭辞とは、こういうことです。
、こういうことです。

。suffixつまり接頭辞とは、こういうことです。



普通は↑この配列のことを、Suffix Arrayと言います。
実質的には、部分文字列へのポインタがこのような順序に並んでいればいいのです。
コーパスの規模が N であれば、 ポインタN個分の記憶領域があればできます。

アルファベットが先か後か、漢字、平仮名、片仮名、記号の順番など、辞書順の定義は、本質的にはどうでもいいのです。


こうすることで、任意の部分文字列を列挙できます。
任意の文字列検索、全文検索が可能になります。


suffix arrayのアルゴリズムは実装しやすいので、さまざまなライブラリなどがあります。



長さX以上の文字列 C が、総異なり数 G で、延べ T回 出現しているか、などを計算できます。

念のため、もう一度説明すると、
「ある文字列 S が、コーパス中に何回出現しているか、 を検出する。」のではないです。
「その、文字列S(集合)は、何であるか?」を検出するのです。


suffix arrayの構築コストの計算量は、コーパスの規模が N であれば、 O(N log N)です。
検索も高速化できます。辞書順にソートされてるので、二分探索で、 O( log N )のコストで検索できます。


岡野原さんが、多分日本一か、世界一ぐらい詳しいと思います。
岡野原さんは、テラバイト以上の、超巨大テキストなどの超高速検索とかをやっていたと思います。


トラックバックURL

コメントする

名前:
URL:
  情報を記憶: 評価:  顔   星
 
 
 
サイト内検索
にほんブログ村 科学ブログへ
にほんブログ村
adsense
Archives
amazon
blogchart
QRコード
QRコード
Recent Comments