2013-01-01から1年間の記事一覧
"Replacing suffix trees with enhanced suffix arrays"に書かれているのを書きたいのだけれどうまくいかない。Lempel Ziv decompositionの場合子のリストを持ってさらにそれに値も持たせないといけないっぽいのだけれど、一時領域だけで最悪24n bytesとかかか…
LaTeXの数学記号とかをUnicodeの文字としてIMEで出す辞書を作った。 例えば"Exists"とうつと∃が出る。1文字目大文字・その他小文字で統一している。なぜ1文字目大文字かというと、(自分の使っている)Google日本語入力の場合、大文字を打つとローマ字変換され…
楽しみのために論文を読むことは面白い! 参照: 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つの…
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…
空間消費もそんなに気にしないし、論文書いた人のコードが本人も主張するad-hocさ加減でよくわからないし。 KLAAP algorithmはシンプルなのに驚いた。こんなシンプルなのに結構発見されたの最近なんだな、と。 とりあえずA New Succinct Representation of R…
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上の階差・累…
wikipediaから参照されていたInducing the LCP-Arrayを読んでる。なんだか怪しげなデータ構造とかを使うと線形時間!か書いたあとに、"これは欲しいものより一般化された問題を解いていた"ってなんだよ!!!!!全然読めてない…
結構写した感じになってしまった。理解としては、メインのinduced sortingが理解できていないのでなんとも。 追記:番兵文字を予約しなくてもいいようにしてみた 1つ目のSA-ISの実装
SA-ISは常識っぽいので実装しなければならない。 結構ブログも見つかるので。
suffix treeの線形時間構築アルゴリズムをちらっと見た。これ、suffix arrayの線形時間構築アルゴリズムの元となっているのかな、と思った。 とりあえずsuffix array線形時間構築は必ず実装する。
my wikiに書いたものを貼り付けてみるテスト。htmlそのまま貼り付けられるけれど、互換性無いから手直ししないとだめだね。 アルゴリズム 「回文の中心」を考えるために、奇回文のみを考える。 偶回文に対応するために、文字列の間になんでもいいダミーの文…
警告:全く実装してないので信頼性低低。結構間違っていそう!そのうち実装してみてその時また書く。 なんかマイナー?。実際自分も覚えてなかった。 d次元ならsegment treeのsegment treeのsegment treeの…っていうふうにすればよい。(実際には~3次元くら…
書こうと思っても全然時間がかかって。それくらいしかできなかった。 明日はSuffix TreeにLowest Common Ancestor(Euler Tourでの±RMQへの還元)を適用してApproximate Matchingとかやりたい。
LCAのやつ、なんとなくはわかったけれども、文章に説明することはまだできないほどにまとまっていなかった。 自分で理解したことをまとめて実感しようかと、少し前にローカルにmediawikiを立ててみてた。 wiki編集難しい。時間もかかってしまう。個人でやっ…
※誤解していた。追記した。 "最小共通祖先"って不自然だと思う。Lowest = 最小? ってよくわからない。このLowestは"高さが低い"っていう意味で使われていると思うが、"小"に"低"の意味はそのままでは含まれていないだろう。「(高さの値が)最小」とか言えな…
構築の時はともかくDFSするとなるとスタックオーバーフローするよなーとか思った。木の深さは(replicate n 'a')でnを達成する。なんでも、メモリを定数倍でも削減しようと思うと、結構複雑になる気がする。現実的にはそれが必要な場面も多いだろうし。 Suffi…
全体的に頭が働いていなかったように思える。 Mediumは、3つを2つに分けるやり方(対称性で減らして2^(3-1)=4通り)のうち、1通りは無意味なので綺麗な3通り!ってのが面白いと思った。極大/極小なもの以外無意味、ということは結構多そうなので、それを使った…
Ukkonen'sを実装したりした。 graphvizで描画するとなんかかっこいい。 Suffix Arrayでも同じことができて、メモリ消費も少ない。Suffix Treeの利点は? 文字種が少なければ線形なので速いのかな? 文字種が多い時、各ノードに配列を持つのはかなりきつい。 …
様々な情報を得て、様々に発想・考察・調査・実装をしていきたい。あわよくば、人たちと反応しあいたい。 なぜtwitterではだめか 1つとして、情報が"流れる"のが速すぎる。 自分はタイムラインのtweetを全て読もうとする。しかしtwitterはそういう使い方は…
http://www.kmonos.net/wlog/_log.html を全部読んでみた。 様々な(特にプログラミング言語に関連する内容が多い)事に関して、情報を得ていたり、様々に発想・考察・調査・実装していて面白かった。 そして、自分も今ではblogを見ているような人たちと反応し…