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

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

2013-09-26

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

LaTeXの数学記号とかをUnicodeの文字としてIMEで出す辞書を作った。例えば"Exists"とうつと∃が出る。1文字目大文字・その他小文字で統一している。なぜ1文字目大文字かというと、(自分の使っている)Google日本語入力の場合、大文字を打つとローマ字変換され…

2013-09-22

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つの…

2013-09-21

directなRMQ

Cartesian TreeとCatalan Numberとか。実装は超手抜きで簡潔さとか考えてない。 Fischer J., Heun V.: "Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE" Fischer J., Heun V.: "A New Succinct Representati…

2013-09-19

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

空間消費もそんなに気にしないし、論文書いた人のコードが本人も主張するad-hocさ加減でよくわからないし。 KLAAP algorithmはシンプルなのに驚いた。こんなシンプルなのに結構発見されたの最近なんだな、と。とりあえずA New Succinct Representation of R…

2013-09-18

(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上の階差・累…

2013-09-17

次はLCP-arrayをやりたい

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

2013-09-16

SA-ISの論文はCコードがあってそれを写せばよい(実装した)

結構写した感じになってしまった。理解としては、メインのinduced sortingが理解できていないのでなんとも。追記：番兵文字を予約しなくてもいいようにしてみた 1つ目のSA-ISの実装

2013-09-15

明日SA-ISを実装したい

SA-ISは常識っぽいので実装しなければならない。結構ブログも見つかるので。

2013-09-14

明日からはsuffix arrayやろう

suffix treeの線形時間構築アルゴリズムをちらっと見た。これ、suffix arrayの線形時間構築アルゴリズムの元となっているのかな、と思った。とりあえずsuffix array線形時間構築は必ず実装する。

2013-09-14

Manacher's algorithm

my wikiに書いたものを貼り付けてみるテスト。htmlそのまま貼り付けられるけれど、互換性無いから手直ししないとだめだね。アルゴリズム「回文の中心」を考えるために、奇回文のみを考える。偶回文に対応するために、文字列の間になんでもいいダミーの文…

2013-09-13

range treeとか(segment treeとかにΘ(その区間サイズ)の構造全部乗っけちゃうやつ)

警告：全く実装してないので信頼性低低。結構間違っていそう！そのうち実装してみてその時また書く。なんかマイナー？。実際自分も覚えてなかった。 d次元ならsegment treeのsegment treeのsegment treeの…っていうふうにすればよい。(実際には～3次元くら…

2013-09-11

mywikiは大変

書こうと思っても全然時間がかかって。それくらいしかできなかった。明日はSuffix TreeにLowest Common Ancestor(Euler Tourでの±RMQへの還元)を適用してApproximate Matchingとかやりたい。

2013-09-10

LCAのとかmy wikiとか

LCAのやつ、なんとなくはわかったけれども、文章に説明することはまだできないほどにまとまっていなかった。自分で理解したことをまとめて実感しようかと、少し前にローカルにmediawikiを立ててみてた。 wiki編集難しい。時間もかかってしまう。個人でやっ…

2013-09-08

LCA (Lowest Common Ancestor) / NCA (Nearest Common Ancestor) の訳語

※誤解していた。追記した。 "最小共通祖先"って不自然だと思う。Lowest = 最小？ってよくわからない。このLowestは"高さが低い"っていう意味で使われていると思うが、"小"に"低"の意味はそのままでは含まれていないだろう。「(高さの値が)最小」とか言えな…

2013-08-29

Suffix Treeで遊んでた

構築の時はともかくDFSするとなるとスタックオーバーフローするよなーとか思った。木の深さは(replicate n 'a')でnを達成する。なんでも、メモリを定数倍でも削減しようと思うと、結構複雑になる気がする。現実的にはそれが必要な場面も多いだろうし。 Suffi…

2013-08-27

SRMをやった

全体的に頭が働いていなかったように思える。 Mediumは、3つを2つに分けるやり方(対称性で減らして2^(3-1)=4通り)のうち、1通りは無意味なので綺麗な3通り！ってのが面白いと思った。極大/極小なもの以外無意味、ということは結構多そうなので、それを使った…