antaのWeb日記

あくまで日記として

Suffix arrayでのbottom-up traversalがうまくいかない

"Replacing suffix trees with

enhanced suffix arrays"に書かれているのを書きたいのだけれどうまくいかない。Lempel Ziv decompositionの場合子のリストを持ってさらにそれに値も持たせないといけないっぽいのだけれど、一時領域だけで最悪24n bytesとかかかってしまう。

まずノードが(l,r)の組で表わされるのが扱いづらい。それをインデックスとした配列を直接操作できない。子を列挙できてもそれに対応する値を保存・取得する方法がわからない。そのためスタックに載せないといけなくて、そのため子のリストを陽に持たないといけなくなってしまう。

あとchild-tableとかlcp-arrayとかが現実的には小さい値ばかりだからたいていは2n bytesとかで～みたいなことをいってるのだけどどうしても最悪を考えてしまう。

lcp-arrayに関しては別に簡潔な保存の方法もあるらしいのだが…読めてない。

なにかうまい方法があるのか…ジェネリックなtraversalルーチンはただの理論的な興味深さでしかなく、問題には問題ごとに対応しなければならないのか…

LaTeXの数学記号とかをUnicodeの文字としてIMEで出す辞書を作った

LaTeXの数学記号とかをUnicodeの文字としてIMEで出す辞書を作った。

例えば"Exists"とうつと∃が出る。1文字目大文字・その他小文字で統一している。なぜ1文字目大文字かというと、(自分の使っている)Google日本語入力の場合、大文字を打つとローマ字変換されないモードみたいになるから。そうじゃないと"えぃｓｔｓ"みたいになってしまって、これで登録するのは少し面倒。

リストはLaTeX/Mathematics - Wikibooksから得た。対応するUnicodeの文字はMathJaxで変換して一部自分で修正・追加・削除。

著作権があるかわからないけれど、もしあったらライセンスはCC0で。

辞書ファイル

Range Maximum-Sum Segment Query Problem

楽しみのために論文を読むことは面白い！

参照： Chen, K.Y., Chao, K.M.: "On the Range Maximum-Sum Segment Query Problem"

 

問題

the Range Maximum-Sum Segment Query Problem (RMSQ)

入力: 空でないnつの実数の列A = [a_1,a_2,...,a_n]。

クエリ: 2つの区間[i, j]と[k, l] (1≦i≦j≦n, 1≦k≦l≦n, i≦l)が入力される。全てのインデックスの組(x, y) (i≦x≦j, k≦y≦l) に対してS(x,y)が最大であるものを返す。答えをRMSQ(i,j,k,l)と呼ぶ。

ここで、S(x,y)は配列Aの部分和 \Sigma_{k=x}^y A[k]。

 

この問題が前処理O(n),クエリO(1)で解けることを示した論文である。

まず、特殊な場合を考える：

 A Special Case of the RMSQ problem (SRMSQ)

入力: 空でないnつの実数の列A = [a_1,a_2,...,a_n]。

クエリ: 区間[i, j](1≦i≦j≦n)が入力される。全てのインデックスの組(x, y) (i≦x≦y≦j) に対してS(x, y)が最大であるものを返す。答えをSRMSQ(i, j)と呼ぶ。

ここで、A(x,y)は配列Aの部分列 A(x,y) = A[x..y] = [a_x, a_{x+1}, ..., a_y]。

SRMSQ(i,j)をA(i,j)の"maximum-sum segment"と呼び、SRMSQ(1,n)をAのmaximum-sum segmentと呼ぶ。

SRMSQ(i,j) = RMSQ(i,j,i,j)であることは明らかである。

SRMSQを解くアルゴリズム

基本的な戦略として、配列Aの累積和c[･]を考える。c[0] = 0、c[i+1] = c[i] + A[i+1]と定義する。ここで、部分和A(l,r)はc[r]-c[l-1]と表されることに注意すると、c[r]を大きくしてc[l-1]を小さくするのが直感的に良さそうにみえる。

しかしこれを直接、たとえば「t[i] = l∈[1..i]でc[l-1]が最小のもの」として前処理してしまうと、クエリでt[i..j]のRMQで区間[t[r],r]を求めたとしてもt[r]＜iの場合にどうしようもない。

そこで"good partner"p[･]というものを考える(定義は省く)。各jに対してp[j]を求め、m[j] = S(1, p[j])という累積和のものをRangeMaximumQueryで前処理しておく。

Lemma 4. インデックス rが全ての 1 \le k \le nに対して m[r] \ge m[k]を満たすならば、 A(p[r], r)は Aのmaximum-sum segmentとなる。

上記の定理はgood partnerが確かにgoodなpartnerであるということを示している。

Lemma 5. p[j]が A上のインデックス jのgood partnerであってp[j]＜jとするならば、全ての p[j] \le k \le j-1に対して c[p[j]-1] \lt c[k] \lt c[j]。

アルゴリズムではまずm[i..j]中の最大値の位置を求め、rとする。i≦p[r]の場合はLemma 4によりそれ[p[r],r]が答えである。

問題はp[r]＜iのときどうするか。しかしgood partnerにはうまい入れ子構造が存在して：

Lemma 6. 全てのインデックス i, j (1 \lt i \lt j \lt n)に対して、 p[i] \lt p[j] \le i \lt jということありえない。

この補題により、もしrを求めてp[r]＜iであったなら、[i,r]と[r+1,j]に区間を分割することができる。なぜなら、もしその2つの分割された区間を横断するようなものが存在したならば、それはあるuに対して[p[u],u]であって、それと[p[r],r]が交差してしまってLemma 6に反するからである。(ここ微妙にわかってない)

[i,r]の部分。c[i-1..r-1]中の最小値の位置を求め、r1とする。[r1,r]が候補となる。右端をrに固定したならば左端のc[r1-1]を最小化したものが答えとなるのは基本的な戦略として書いた通りである。なぜr以外の右端を考えなくて良いかというと、Lemma 5によりc[r]以上のc[k]は存在しないからである。

[r+1,j]の部分。さらにm[r+1..j]中の最大値の位置を求め、r2とする。ここで、Lemma 6によりr[r2]はr以下にならず、よってi以下にもならないためr[r2]を確実に左端とすることができ、Lemma 4により[r[r2],r2]を答えとすることができる。

分割した区間の両方(r==jの場合は後者は存在しない)を解き、そのうち最大値を取るものが答えとなる。

RMSQを解くアルゴリズム

さて、実際にはSRMSQが解けたならば、RMSQはそれに少しコードを足すだけで解けてしまう。最初に、一般性を失わずにi≦kかつj≦lと仮定しておく。

まずj≦kの場合は簡単である。基本的な戦略は分離した(点で接していてもいい)2つの区間のSRMSQに対しては完全によく働く。つまり、(RMQ_min(c, i − 1, j − 1) + 1, RMQ_max(c, k, l))を出力する。

次にk＜jの場合。アイデアはこれもまた区間(ペア)の分割である。3つの区間ペアに分割できる。

  1. ([k,j], [k,j])。つまり2つの区間の共通部分である。SRMSQを子呼び出しすればいい。
  2. ([i,k], [k,l])。分離しているので基本的な戦略通りでいい。
  3. ([k,j], [j, l])。これも分離しているので基本的な戦略を用いる。

上記の3つのもののうち最大値をとるものが答えとなる。なぜこの3つだけでよいかは絵を描けばわかる。どうやってもその3通り以外の正当な区間を取れないことがわかるだろう。

f:id:anta2:20130922002854p:plain

RMQは前処理O(n),クエリO(1)で解けるので、この問題も漸近的に最適に解ける。

 実装

0-originにしている。一応ランダムテストされている。RMQは別途必要。

Range Maximum-Sum Segment Query Problem

directなRMQ

Cartesian TreeとCatalan Numberとか。実装は超手抜きで簡潔さとか考えてない。

directなRMQ的な(手抜きなのでO(n)になってないきがする)

とりあえずinducing LCP-arrayは諦めた

空間消費もそんなに気にしないし、論文書いた人のコードが本人も主張するad-hocさ加減でよくわからないし。

KLAAP algorithmはシンプルなのに驚いた。こんなシンプルなのに結構発見されたの最近なんだな、と。

とりあえずA New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Arrayにあるような、Cartesian treeの番号付けに基づいた、Cartesian treeを陽に構築しなくても一般RMQができるやつを実装したい。

(n-ary) Gray code と累積和・階差

Prefix sum - Wikipedia, the free encyclopediaより。

なんでもGray codeの逆変換 = Z/2Z上の累積和で、つまりGray code変換 = 階差らしい。

Gray code - Wikipedia, the free encyclopediaにあるgeneralizeのn-ary Gray codeも同じようにZ/nZ上の階差・累積和となる(おそらくは)。

この考えの競プロ的使い方としては、累積和法させる時にGray codeを出して累積和法であることを「隠す」ことくらいかな。まあ既にあるかもしれないけど。

余談だが累積和(cumlative sum)ってprefix sum(接頭辞和という訳が少し見つかった)とも言うんだね。LCAといい、こういう複数の呼び方があるやつどうにかしてほしい…

次はLCP-arrayをやりたい

wikipediaから参照されていたInducing the LCP-Arrayを読んでる。なんだか怪しげなデータ構造とかを使うと線形時間！か書いたあとに、"これは欲しいものより一般化された問題を解いていた"ってなんだよ！！！！！全然読めてない…