string
http://www.cs.ucr.edu/~stelo/pattern.html#resources 文字列アルゴリズム、情報検索周辺の学会、本、ソフトウェア
http://web.njit.edu/~rytter/teaching/texts/book.html 少し古い(1994)文字列アルゴリズムの本。
意外な単語がアナグラムだったりします。 thread HATRED reproduce PROCEDURE thousand HANDOUTS generate TEENAGER process CORPSES PROCESS ruby -e'class String; def sort(); self.split(//).sort.join;end;end; dic={}; ARGV.each{|f| File.open(f).eac…
文字2-gram確率の最大化だけを目的としたいろは歌生成は、 文字＝都市の巡回セールスマン問題インスタンスに相当する。日本語の音韻的制約（iaはあるけどiuはないとか）を反映した程度の ゆるい文法性しか付与できないと思われる。文字N-gram化することも可…
出てました。 あまり分厚くない文字列アルゴリズム本。 最近の文字列アルゴリズムの進展は全くついていけなくて、 書籍である程度基礎がためしないとなと思っていたので読んでみる。数ページしか読んでませんが、 この著者って Jewels の人ですね。 amazonで…
http://www.chasen.org/~taku/software/darts/ suffix array とかの template library つくるのにも参考にできると思う。 NodeType Trie の各ノードの型です. 一般的な C 文字列の検索なら, char 以外に設定する必要はありません. NodeUType Trie の各ノード…
A Guided Tour to Approximate String Matching
http://www.stringology.org/event/2005/p3.html Suffix Vector 、その後。 ぱっと見では、Review の性格が強そう。
http://citeseer.ist.psu.edu/35617.html オートマトンの最小化も、奥が深い。
http://scholar.google.com/scholar?hl=en&lr=&cluster=2191706408632576091 AND,OR,region algebra のクエリに対して、 データベースの部分文字列（位置）のリストを返す。リスト中の部分文字列は、クエリに適合する極小な部分文字列。 リストは文字列の長…
http://cs.haifa.ac.il/~landau/ Construction of Aho Corasick Automaton in Linear Time for Integer Alphabets など。
http://www.dcc.uchile.cl/~gnavarro/eindex.html 自然言語の全文字列索引付けとか、 あいまい検索とか。
http://www.research.ibm.com/journal/rd/501/agarwal.html Differential compression arose as part of the string-to-string correction problem [2], finding the minimum cost of representing one string in terms of another. 問題： 差分圧縮：参照フ…
http://theory.lcs.mit.edu/~indyk/ 雑音のあるパターンマッチング。 FFTをツールとして、というのが面白そう。
Sparse Suffix Tree とは、Krisztian さんの論文[2005-11-02-1]で紹介されている、 単語単位 Suffix Tree のようなもの。 形式的には、文字列と文字列中でのすべての単語の開始位置（区切り記号の位置 -1）が与えられたとき、 単語の開始位置から始まる suff…
Krisztian Monostori さんの博士論文[2005-11-02-1]が原典 suffix tree を格納する形式のひとつ 他の形式： suffix tree は木なので、一般的な木の格納形式が使える suffix tree 特有の冗長性を利用した、より効率的な格納形式がありえる ほかにも冗長性を利…
ふつうの Suffix Tree は、文字列のランダムアクセス性を仮定している。でも、いま考えている選択的アルファベット拡大（文字の連結によるアルファベットへの新文字追加）を 行うには、配列よりも連結リストの方が都合がいい。 連結リストではランダムアクセ…
[2005-11-18-1] の検索は sagrep で行った。 ディレクトリ pyxis:/home/data/documents/suffix_array で、 sagrep "尼崎公害訴訟" yomiuri-2000 | ./get_context.pl とやろうとしたら、yomiuri-2000 を作ったときと Perl のバージョンが違っていて動かなかっ…
拡大されたSuffix Tree は文字単位ではなく単語単位のSuffix Treeとなり、 枝は「単語」でラベルづけされる。 単語は文字列なので、 ノードからノードに枝をたどるときには、 単語数で長さ 1 の枝でも、その文字数分のマッチが必要になる。このため、単語単…
長さ n のランダムな2進列があります。 0の数と1の数が分かっているものとします。 また 00、01、10、11の数も分かっています。 ただし 00 と 11 の数は、重複ありで数えたものです。 これらから、00 または 11 の重複無しでの数を求められますか？ 証明、ま…
Kriszti'an Monostori et al., Suffix vector: space- and time-efficient alternative to suffix trees ACM掲載の論文。短くまとめられているが、わかりにくい。 同氏の博士論文 ドキュメント集合から部分一致チャンクを見つけ出す、というシステム。 その…
Gusfield, "Algorithms on Strings, Trees and Sequences" 7.7.節より。 suffix tree の方で、枝を結んでしまえばいい、ということ。 索引（部分文字列を入力してその出現位置を得る）としての機能は失われるが、 出現回数はわかる。
Ukkonen のアルゴリズムで付加される Suffix Link を利用する。 Suffix Link は下層から上層のノードに向かう枝であり、 元のノードと先のノードには、 「根から元のノードまでのラベルの先頭を取り除くと、根から先のノードまでのラベルになる」 という関係…
http://www.cas.mcmaster.ca/~franek/proceedings/psc05.pdf アルファベットの順序を再定義したときの接尾辞配列の再構築。アルファベットを拡大したときの再構築手法が欲しい。
数Mバイトのデータの木を作るのに、Gバイトに近いメモリを必要とするのを 改善しようと、プロファイラにかけてメモリ使用量の多い変数を探した。 java -agentlib:hprof=cpu=samples,heap=sites,file=sample.prof -Xms20M -Xmx1000M SuffixTree cpu=samples …
基本的には、対象文字列の区間と一致している事例データの区間を見つけ、 そこでの分割を真似する、という方法。 対象文字列中の各位置からの部分文字列のうち、事例文字列に現れ、 かつ長さ極大の部分文字列に対する事例での分割を類似度の重みつきで採用す…
http://www.cs.mcgill.ca/~cs251/oldcourses/1997/topic7/trie（トライ）とは、k分位置木 (k-ary position tree) で、辞書（連想配列）へのアクセスを効率化するためのデータ構造である。 辞書は、ある文字列がその辞書に入っているかどうかを調べる機能を持…
http://www.csse.monash.edu.au/~lloyd/tildealgds/tree/patricia/
概念 対象文字列の最後尾に1文字増えたとき、接尾辞木を更新する。 ただし、ここでの接尾辞木は終端文字を含まず、葉以外のノードで接尾辞が終わることもあるような木である。 対象文字列にxが追加されたとき、それまでの任意の接尾辞aをaxに変えることがこ…
接尾辞配列を直接構築する方法のほとんどは、 全部をソートせず、一部分だけをソートし、 残りは接尾辞同士の関係から順序を決める、というものが多いようだ。 直接構築でないのは、いったん接尾辞木を作る方法。また、自然言語データは、長い部分一致箇所が…
