今更ながら逆索引（inverted index）がどのようなものか調べる。あー恥ずかし。
2008年4月22日火曜日
2007年11月22日木曜日
プログラムコードを書くテスト
ちょっとテスト
なるほど、<pre>で囲めばいいのか。
def say_goodnight(name)
result = "Good night, " + name
return result
end
なるほど、<pre>で囲めばいいのか。
2007年8月1日水曜日
論文：木スケルトンによるXPathクエリの並列化とその評価
コンピュータソフトウェア, Vol.24, No.3, pp.51-62, 2007.
読んではいないのだが、XMLの並列処理の論文は少ないので、忘れないようにメモしておく。内容は、並列化技術に明るくないと理解が難しいかも。
読んではいないのだが、XMLの並列処理の論文は少ないので、忘れないようにメモしておく。内容は、並列化技術に明るくないと理解が難しいかも。
2007年6月19日火曜日
Suffix tree - Wikipedia, the free encyclopedia
Suffix tree - Wikipedia, the free encyclopedia
接尾辞木。PAT tree, position treeとも言う。基本的には、文字列Sのすべての接尾辞に対するradix tree。ただし、ある接尾辞が別の接尾辞の接頭辞（ああ、ややこしい）になるとradix treeにならないため、各接尾辞の最後に終端記号$をつける。複数の文字列に拡張したものがgeneralized suffix tree。Xαに対する節点からαに対する節点に対してリンク（接尾辞リンク）を張っておくことがある。
文字列検索や文字列の性質の発見に関して、計算量の少ないアルゴリズムが数多く提案されている（とても書き切れない）。構築もUkkonenにより線形時間のアルゴリズムが提案されている。その半面、記憶量は文字列長に比例する。
接尾辞木。PAT tree, position treeとも言う。基本的には、文字列Sのすべての接尾辞に対するradix tree。ただし、ある接尾辞が別の接尾辞の接頭辞（ああ、ややこしい）になるとradix treeにならないため、各接尾辞の最後に終端記号$をつける。複数の文字列に拡張したものがgeneralized suffix tree。Xαに対する節点からαに対する節点に対してリンク（接尾辞リンク）を張っておくことがある。
文字列検索や文字列の性質の発見に関して、計算量の少ないアルゴリズムが数多く提案されている（とても書き切れない）。構築もUkkonenにより線形時間のアルゴリズムが提案されている。その半面、記憶量は文字列長に比例する。
Radix tree - Wikipedia, the free encyclopedia
Radix tree - Wikipedia, the free encyclopedia
Patricia tree, Patricia trie, crit bin treeとも言う。トライとの違いは、枝に文字列をラベル付けできること。lookup, insert, delete, find predecessor（与えられた文字列に対して、辞書順で直前の文字列を探す）, find successorがいずれもO(k)（kは格納されている文字列の最大長さ）で可能。
下記論文が原典だが、読みにくいので、これを読むのは当分保留。
http://doi.acm.org/10.1145/321479.321481
Patricia tree, Patricia trie, crit bin treeとも言う。トライとの違いは、枝に文字列をラベル付けできること。lookup, insert, delete, find predecessor（与えられた文字列に対して、辞書順で直前の文字列を探す）, find successorがいずれもO(k)（kは格納されている文字列の最大長さ）で可能。
下記論文が原典だが、読みにくいので、これを読むのは当分保留。
http://doi.acm.org/10.1145/321479.321481
Trie - Wikipedia, the free encyclopedia
Trie - Wikipedia, the free encyclopedia
Wikipediaばかり読んでいるな…
別名は接頭辞木（prefix tree）。順序付き木の一種。キーが文字列である連想配列を格納するのに用いられる。枝に文字がついており、ルートからの経路上の文字をすべて連接すると、節点のラベルになる。これが連想配列のキーとなる。その構造上、決定性有限オートマトンとみなすことができる。読み方は「トライ」。
Wikipediaばかり読んでいるな…
別名は接頭辞木（prefix tree）。順序付き木の一種。キーが文字列である連想配列を格納するのに用いられる。枝に文字がついており、ルートからの経路上の文字をすべて連接すると、節点のラベルになる。これが連想配列のキーとなる。その構造上、決定性有限オートマトンとみなすことができる。読み方は「トライ」。
Longest common substring problem - Wikipedia, the free encyclopedia
Longest common substring problem - Wikipedia, the free encyclopedia
2つの文字列に対し、共通の部分文字列のうち最長のものを求める問題。一般化接尾辞木（generalised suffix tree）を使うと、部分文字列の開始位置と長さがΘ(n + m)で求まる。また動的計画法を用いるとΘ(nm)で求められる。一般化接尾辞木のほうは分かったが、動的計画法のほうは知識不足で読み切れず。
2つの文字列に対し、共通の部分文字列のうち最長のものを求める問題。一般化接尾辞木（generalised suffix tree）を使うと、部分文字列の開始位置と長さがΘ(n + m)で求まる。また動的計画法を用いるとΘ(nm)で求められる。一般化接尾辞木のほうは分かったが、動的計画法のほうは知識不足で読み切れず。
登録:
投稿 (Atom)
