今回は最近流行り（？）のストリーミングモデルにおける文字列処理について簡単に紹介しようと思います．テクニカルな内容を期待している方には申し訳ありませんが，今回はこういうことが研究されているよぐらい，かつ短い記事です．

ストリーミングモデルにおける文字列照合問題

説明を簡単にするために，文字列照合問題に絞ってお話します．
ストリーミングというからには，テキスト全体がわかっているということはありません．テキストは一文字ずつやってきて，その都度その位置を終了位置とするパターンの出現があるかないかを高速に計算しましょうというものです．もちろんパターンは事前に与えられているものとして，前処理をしておいてかまいません．
さてこの設定ではいわゆるオンラインアルゴリズム（15日目 @hdbn さんの記事でも取り上げられています）じゃないかと感じるでしょう．その通りです．では何を持ってしてストリーミングアルゴリズムと呼ばれるのでしょうか．それは領域の制約です．通常であれば，パターン長に線形な領域（以降パターン長を $m$ として $O(m)$ 領域）の前処理をしておけばこの問題を高速に解くことができますが，ストリーミングアルゴリズムは欲張りで，高速でありながらこの領域すら削減を目指します．

そんなことができるのでしょうか．次のようなことが知られています．

定理 1
オンライン文字列照合問題の決定性アルゴリズムは，$\Omega(m)$ 領域必要である．

R. Clifford et al., "A Black Box for Online Approximate Pattern Matching", CPM 2008

そう，決定性アルゴリズムではできないのです．というわけで，話は乱択アルゴリズムへと変わります．ここでは，高い確率で正しく出力するけどたまに間違えるかもねってことです．決定性は正しく答えないといけないので $O(m)$ 領域使わない，つまりパターンそのものすら保持できないことを考えるとこの結果にもうなずけますが，実は乱択にしてもこの $\Omega(m)$ 領域が必要なのではないかと長く信じられていたようです．

文字列照合問題におけるブレークスルー

ですが安心してください．2009年にこの問題に対して救世主が現れました．

定理 2
$O(\log m)$ 領域の前処理をしておけば，一文字あたり $O(\log m)$ 時間の処理でパターンの存在を判定できる．エラーの確率は $\frac{1}{n^2}$ である（$n$ はテキスト長）．

B. Porat and E. Porat, "Exact and Approximate Pattern Matching in the Streaming Model", FOCS 2009

見る人が見ればわかるトップカンファレンスに採択された論文です．ちなみに，一文字あたりの計算時間を平均的に解析するとなんと定数時間だそうです．
今回はテクニカルな内容は話さないのですが，どの部分を乱択にしているのかだけ簡単に説明すると，それは部分文字列の比較です．Finger print というものを使います．これは，文字列を適当な数値に変換するもので，同じ文字列であれば数値は必ず同じになりますが，ある程度低い確率で異なる文字列が同じ値になってしまいます．つまり，数値の比較という簡単な操作で高速に文字列の比較を高い確率でできるということです．

ブレークスルーのその後

上記の結果も非常にすごいのですが，この後さらに改善されていきなんとなんと...

定理 3
$O(\log m)$ 領域の前処理をしておけば，一文字あたり $O(1)$ 時間の処理でパターンの存在を判定できる．エラーの確率は $\frac{1}{n^{\alpha}}$ である（$\alpha > 0$ ）．

D. Breslauer and Z. Galil, "Real-time Streaming String-matching
", ACM Transactions on Algorithms, 2014

もういうことはありませんね．ここまでが（厳密一致）文字列照合問題の話でした．

様々な問題

上では簡単に厳密一致文字列照合問題について紹介しましたが，最後に他の問題についてどんなものが研究されているかいくつか挙げておわりにしたいと思います．

k-ミスマッチ文字列照合問題

この問題は，パターンと同じ長さのテキストの部分文字列と $k$ 文字まではマッチしてなくても出現したとみなす文字列照合問題です（例えば，aabab と abbaa は 2-ミスマッチや 3-ミスマッチ問題ではマッチします）．この問題に対しての結果は，実は上の定理 2 で紹介した論文で紹介されています．また最新の結果としては，R. Clifford らの以下の論文で発表されています．

R. Clifford et al., "The k-mismatch Problem Revisited", SODA 2016

その他の問題

文字列照合問題には様々なバリエーションがあり，上のミスマッチを許した照合以外にも，Wildcard を含んだ文字列照合問題，パラメタ化文字列照合問題や辞書照合問題などに対してストリーミングアルゴリズムが提案されています．
さらに文字列照合以外にも，文字列の最小周期，ハミング距離，回文構造などを計算する問題のストリーミングモデルでのアルゴリズムが研究されています．

さいごに

今回は短いですが，これで終わります．
ストリーミングモデルにおける文字列アルゴリズムの研究はまだまだやることがたくさんあると思います．しかもこれまでの成果の多くがトップカンファレンスに採択されているという業界の方には良いフィールドかもしれませんね．
大した内容ではありませんでしたが，読んでいただいてありがとうございました（また後日，追記などする可能性が大いにあります）．