文字列処理 - haraduka's diary

インターンやら何やらで何もやる時間がなかったのですが、帰ってきたので少し書きます(また明後日から二週間何もできない)。

文字列検索には主にローリングハッシュというものと、SuffixArrayというものがあるそうです。へぇ。
あるn文字のstring Sからm文字のstring Tを発見することを考えます。

ローリングハッシュ
ハッシュで検索するとは、各開始位置に対してそこからの文字列が一致するかをO(m)かけて文字列比較(結局O(nm))するかわりに、ハッシュ値を使ってO(1)で求めよう！というものです。
が、そのときハッシュ値を作成するのにO(nm)かかってしまっては結局O(nm)になってしまうので、うまくO(n+m)で文字列検索をしようではないか！というのがローリングハッシュというアルゴリズムです。

互いに素な定数b,hを持ってきて、文字列Sのk文字目からm文字の部分文字列をS[k…k+m-1]と置き、ハッシュ値H(S[k…k+m-1])を
${\displaystyle H(S[k{\ldots}k+m-1]) = {C_k}{b}^{m-1}+{C_{k+1}{b}^{m-2}}+{\ldots}+{C_{k+m-1}{b}^{0}} }$
とすると、
${\displaystyle H(S[k+1{\ldots}k+m]) = {(H(S[k{\ldots}k+m-1]){b}-{S_k}{b}^{m}+{S}^{k+m}}) {mod } {h} }$
というように開始位置を一つずらしたハッシュ値が得られるので、これを最初から最後まで繰り返せば、結局O(n+m)で文字列比較ができることになります。

これは二次元にも拡張可能だし、とても便利ですね。

Suffix Array
これは接尾辞配列を用いた文字列検索方法です。つまり、開始位置を変えながらそこから文字列の終端までの部分文字列を全て列挙、ソートして保持しておき、そこから二分探索で文字列検索をかけます。
ローリングハッシュだとO(len(S)+len(T))ですが、SuffixArrayを用いればO(len(T)*log(len(S)))で検索が可能なため、Sが非常に大きい場合に有利になります。
問題はこの"ソートして保持"の部分で、これを速く計算しないといけないのですが、ナイーブにやるとO(n^2*log(n))でお話になりません、ということでダブリングという方法を使ってO(n*(log^2(n)))にすることができます。
これはまず、それぞれの開始位置から1文字を取ってきてソートし、次に2文字を取ってきて前回ソートしたところ以外をソートし、次に4文字を取ってきて…というように計算していく方式です。他にもSA-ISとかいうめっちゃ速いアルゴリズムがあるらしいですよ。

また、SuffixArrayには高さ配列(LCP)という情報を付加することでさらに便利になります。
それは、SuffixArrayの隣あった文字列が先頭から何文字一致するかを格納した配列のことです。
これはO(n)で計算できるのですが、これを使えば、2つの文字列に共通している部分文字列の最長や最小を求めたりすることが容易になります。