jumbled pattern matchingというのを知った

Binary Jumbled Pattern Matching via All-Pairs Shortest Paths(http://arxiv.org/pdf/1401.2065v1.pdf)という論文がLOUDS論文をreferしていて興味があったので読んでいた。jumbled pattern matchingという問題の時間計算量を改善したよ、という話だった。
不勉強ながらjumbled pattern matchingという言葉を知らなかった(もしくは忘れていた)。幸い、この論文にどういう問題であるか解説があったので容易に理解することが出来た。
なので忘れないうちにメモしておく。


jumbled pattern matchingというのはマッチさせる単語の文字の順番が入れ替わっていてもマッチさせるパターンマッチ。つまりabracadabraに対してabraだけでなくbaraもマッチする。
この論文では文字を二値にして単純化したbinary jumbled pattern matchingというのを扱っている。これはビット列Bに対して(i,j)というクエリを投げた場合、長さiの部分ビット列でj個だけ1が立っているものは存在するか?というのを返す問題。例えば10001101に対して(4,0)=0, (4,1)=1, (4,2)=1, (4,3) = 1, (4, 4) = 0という感じ。


この問題は単純に数え上げるとO(n)の時間計算量がかかる。しかし、各iに対して(i, j)=1となる最小のjと最大のjを持たせておけばこのクエリはO(1)となる(空間計算量は余分にO(n)必要となる)。
これは(i,j)というクエリが投げられた時に、jが最小値と最大値の間にあれば常に(i,j)=1となるから。例えばi=4に対してjの最小値は1で最大値は3なので(↑の例を参照)、(4,2)=1となる。


何故これが成り立つかというと、例えば、ビット列B(10001101)上の長さ4の部分ビット列b1とb2があって、b1は0ビット目からはじまるビット列(1000), b2は4ビット目からはじまるビット列(1101)だったとする。
このときb1からb2へと移動する場合「1ビット隣に移動する」という操作を繰り返すことになる。つまり(1000)→(0001)→(0011)→(0110)→(1101)というふうに長さ4の部分ビット列を移動させていく。この毎回の移動によって部分ビット列内の立っているビット数は(1減る、変わらない、1増える)のいずれかになる。


つまり最小の1を含む部分ビット列から、最大の1を含む部分ビット列への移動も「1ビット隣に移動する」の繰り返しなので、言い換えると「立っているビット数が(1減るor変わらないor1増える)」の繰り返しになる。
部分ビット列の位置の移動は「立っているビット数の1ずつの増減」の繰り返しで行われるので、j1個の1が立っている長さiの部分ビット列からj2個の1が立っている長さiの部分ビット列への移動の過程でj1<= j <=j2となるjについて、j個の1が立っている部分ビット列が登場しているということ。


具体的に見ていくと、ビット列B(10001101)に対してi=4に対するjの最小値は1で、これは例えば0ビット目からはじまる部分ビット列(1000)が該当する。またjの最大値は3で、これは例えば4ビット目からはじまる部分ビット列(1101)が該当する。
このビット列間の移動は既に一回説明したように(1000)→(0001)→(0011)→(0110)→(1101)となっている。立っているビット数の変更を書き加えると

(1000)→(変わらない)→(0001)→(1増える)→
(0011)→(変わらない)→(0110)→(1増える)→(1101)

というわけで1ビットの増減によって移動が行われている。この移動の途中で(0011),(0110)という(4,2)=1に該当する部分ビット列が登場していることがわかる。


というわけで説明は以上。
ちなみに各クエリに対して定数時間で計算できるのでこれで充分じゃね、と思ったら全i,jの組み合わせに対して計算するとO(n^2)なのでこれを改善するよ、という話の論文だった。


思いつきメモ
binaryじゃないjumbled pattern matchingも、それぞれの文字について最小値、最大値をもたせれば同じことが出来そう。その場合O(Σn)の予備領域が必要だけど、最小値、最大値はそれぞれ非減少列、非増加列なのでvertical codeのような差分圧縮な簡潔構造を使えばデータサイズが小さくて済みそう。