Hatena::Grouptopcoder

(iwi) { 反省します

TopCoder: [[iwi]] / Twitter: @iwiwi

 | 

2011-07-20

SA-IS

22:22 | SA-IS - (iwi) { 反省します を含むブックマーク はてなブックマーク - SA-IS - (iwi) { 反省します SA-IS - (iwi) { 反省します のブックマークコメント

はじめに

Suffix Array の現状最強アルゴリズムっぽい SA-IS を理解したつもりになったので、備忘録を殴り書く。論文は:

これは 2009 年のアルゴリズムで、他のそれまでのアルゴリズムに比べて、速くて、メモリ使用量も少なく、しかも実装量も少ないと、ぱないアルゴリズムです。 どっかに比較のプロットがある論文があったはず。

先生へ:僕のレポートはここのコピペ編集ではなくここを書いたのも僕ですのでカンニング扱いにしないようお願いします

概要

  1. 与えられた列を LMS-Substring の列として分け、それらを全てソートし小さい順に番号つけて、新たな列を作る
  2. その列の Suffix Array再帰的に求める
  3. その Suffix Array から全体の Suffix Array を求める

という感じ。 2 の再帰時にサイズが必ず半分以下になっているので、線形時間!!! 1 と 3 の両方で Induced-Sorting というテクが使われる (同じコードが使いまわせるぐらい同じことする) のが特徴。

LMS-Substring

与えられる文字列を A としましょう。各場所 i について、

  • 場所 i が S-type <-> A[i..] < A[i+1..]
  • 場所 i が L-type <-> A[i..] > A[i+1..]

とします。 (A[i...] は場所 i からのサフィックス)

各場所 S か L になって、要は折れ線で登ってるところが S で下ってるところが L で、文字列に対して LLLSSSLLSSLLLSSSLLL みたいなのが対応する、感じ。

LMS とは Left-most-S という意味で、左を極めた S。 そこが S かつすぐ左が L の場所のこと。

LMS-Substring とは、ある LMS から次の LMS までの部分文字列たちのこと。 SSSSLLLLL(S)

Induced-Sorting

先に、LMS-Substring 達の Suffix Array から元の Suffix Array を作る方法を話す。 (概要の 3)

ここも 3 つのステップからなって、

  1. 「LMS の位置」だけに関する SAをつくる
    • これは、部分問題の SA を、元の SA にインデックスに貼り直せばよい
  2. さっきの SA の情報を元に、「LMS の位置&L-type の位置」 に関する SA を作る (L-type の位置について計算する)
  3. さらにその SA の情報を元に、完全な SA を作る (S-type の位置について計算する)

ここが難しいところだけど、やってることはすごいシンプル。

2 と 3 は、向きこそ違うが、似たようなことをやる。 ので、2 だけ説明する。

まず、Suffix Array において、L-type と S-type はどういう雰囲気になるかというと、

  • 'a' から始まる L-type
  • 'a' から始まる S-type
  • 'b' から始まる L-type
  • 'b' から始まる S-type

という風な順にならんでいるということがわかる。 (これは 2 段階法とか系列の SA のアルゴリズム達で核となってきたアイディア)

まず、バケツソート的な計数を行うことにより、'a' から始まる suffix、'b' から始まる suffix、… とかの数がわかる。

最初の文字でバケツソート数えた各バケツに放り込むと考えると、'a' から始まり L-type の文字列たちのランク付けっていうのは、'a' を除いた 1 文字短い suffix たちのランク付けが分かれば、OK。

で、その情報は、Suffix Array が分かってればすぐにわかるんですが、今まさに Suffix Array 計算しようとしてるのに Suffix Array の情報使いたいとか、意味わからない。 んですが、実は、順序を工夫して計算してゆくと、必要なところから順に計算されていって、どんどんと情報を伝搬みたいなことができるようになります。

具体的には、i を小さい順に見ていく

  • SA[i] がもう分かってて、場所 SA[i]-1 が L-type なら、
    • 場所 SA[i]-1 を文字 A[SA[i]-1] のバケットの最後尾に放り込む
    • (放り込む、とは、SA[i]-1 の SA 内での場所をそこに確定するということ。 Suffix Array の適切なインデックスに場所 SA[i]-1 が追加される)

配列 SA を頭から見てゆくと、小さい suffix から見てゆくことになります。 L-type ってことは、 1 文字短くした suffix ってのは、自分より小さい suffix になっているはずで、しかもそれは L-type か LMS のどちらかなので、もう計算されてるわけですね。

天才すぎる。 計算してった情報がどんどん伝搬してゆく感じ。

ステップ 3 の S-type に関しては、逆に大きい i から見てゆきます。 S-type ってことは 1 文字短くした suffix は自分より大きいわけですからね。

あと、概要ステップ 1 の、LMS-substring のソートは、LMS の文字たちをバケツソートして、あとは全く同じことをします。すると、LMS の文字たちから、「L-type の各文字〜次のLMS」っていう文字列たちのソートができて、で、「各文字から次のLMS」っていう文字列のソートができる。

おわりに

まあこんなのじゃわからないかもしれませんが、きほん他人向けじゃないつもりな割にいっぱい書いたけどやっぱわからないと思うのでごめんなさい。 わかったらすごい。

ちなみに、"Two Efficient Algorithms for Linear Suffix Array Construction" という論文の方に SA-IS の C のコードが載っています。 100 行以内で書ける!! とか言っておきながら、96 行あるけど、まあコメント行結構ある、けど、1 行に複数ステートメントある行も結構ある…

コピペすれば普通に使えます。

日常で使いたいときは Yuta Mori さんの実装が良さそう。 元論文でもチラりと言及されている。

検証は https://www.spoj.pl/problems/SARRAY/ とか。

highjellieshighjellies2011/07/27 14:33全然理解してないけど赤字のところが面白かったです.

iwiwiiwiwi2011/08/13 17:24世の中こわいので…

AmbriorixAmbriorix2012/08/30 12:14Peefrct shot! Thanks for your post!

nqirfrdimwnqirfrdimw2012/09/01 03:08IkIM8n , [url=http://gddvyeazmity.com/]gddvyeazmity[/url], [link=http://nvjwvdodlwxu.com/]nvjwvdodlwxu[/link], http://mrbyxinpejrr.com/

gfkldagfklda2012/09/01 18:247ZkF4W <a href="http://ldlqtuhpfhtl.com/">ldlqtuhpfhtl</a>

 |