kunishi's memo

Inverted index - Wikipedia, the free encyclopedia

2008-04-22T10:21:00.000+09:00

Inverted index - Wikipedia, the free encyclopedia

今更ながら逆索引（inverted index）がどのようなものか調べる。あー恥ずかし。

プログラムコードを書くテスト

2007-11-22T10:48:00.001+09:00

ちょっとテスト

def say_goodnight(name)
 result = "Good night, " + name
 return result
end

なるほど、<pre>で囲めばいいのか。

論文：木スケルトンによるXPathクエリの並列化とその評価

2007-08-01T17:28:00.000+09:00

コンピュータソフトウェア, Vol.24, No.3, pp.51-62, 2007.

読んではいないのだが、XMLの並列処理の論文は少ないので、忘れないようにメモしておく。内容は、並列化技術に明るくないと理解が難しいかも。

Suffix tree - Wikipedia, the free encyclopedia

2007-06-19T19:37:00.000+09:00

Suffix tree - Wikipedia, the free encyclopedia

接尾辞木。PAT tree, position treeとも言う。基本的には、文字列Sのすべての接尾辞に対するradix tree。ただし、ある接尾辞が別の接尾辞の接頭辞（ああ、ややこしい）になるとradix treeにならないため、各接尾辞の最後に終端記号$をつける。複数の文字列に拡張したものがgeneralized suffix tree。Xαに対する節点からαに対する節点に対してリンク（接尾辞リンク）を張っておくことがある。

文字列検索や文字列の性質の発見に関して、計算量の少ないアルゴリズムが数多く提案されている（とても書き切れない）。構築もUkkonenにより線形時間のアルゴリズムが提案されている。その半面、記憶量は文字列長に比例する。

Radix tree - Wikipedia, the free encyclopedia

2007-06-19T18:33:00.000+09:00

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

Trie - Wikipedia, the free encyclopedia

2007-06-19T15:22:00.000+09:00

Trie - Wikipedia, the free encyclopedia

Wikipediaばかり読んでいるな…

別名は接頭辞木（prefix tree）。順序付き木の一種。キーが文字列である連想配列を格納するのに用いられる。枝に文字がついており、ルートからの経路上の文字をすべて連接すると、節点のラベルになる。これが連想配列のキーとなる。その構造上、決定性有限オートマトンとみなすことができる。読み方は「トライ」。

Longest common substring problem - Wikipedia, the free encyclopedia

2007-06-19T14:46:00.000+09:00

Longest common substring problem - Wikipedia, the free encyclopedia

2つの文字列に対し、共通の部分文字列のうち最長のものを求める問題。一般化接尾辞木（generalised suffix tree）を使うと、部分文字列の開始位置と長さが

Θ(n + m)で求まる。また動的計画法を用いると

Θ(n m)で求められる。一般化接尾辞木のほうは分かったが、動的計画法のほうは知識不足で読み切れず。

編集文献学に基づく人文科学資料エディティング・システム構築の試み

2007-06-19T14:10:00.000+09:00

明星聖子（埼玉大）, 永崎研宣（山口県立大）
情報処理学会研究報告 2007-CH-74, pp.25-32, 2007.05.

人文科学の研究者が資料をどうとらえているか、資料を継ぎ合わせるとはどういうことなのか、その一端が伺えると言う意味で興味深い。また、編集文献学（scholarly editing theory）という学問があるということも初めて知った。興味深い学問のような気配がする。

Suffix array - Wikipedia, the free encyclopedia

2007-06-19T14:08:00.000+09:00

Suffix array - Wikipedia, the free encyclopedia

接尾辞配列（suffix array）についての説明をWikipediaで読む。接尾辞を、その先頭の文字の添字番号でインデックス化すること、接尾辞の辞書順に並べ替えることで二分探索が使えることがミソか。日本語Wikipediaでは、実装例としてSaryが挙げられていた。

軽量のテキスト処理による部分類似単語列検出手法

2007-06-19T13:21:00.000+09:00

竹田隆治（総研大）, 高須淳宏（NII）
電子情報通信学会技術報告AI2007-7, pp.33-38, 2007.05.

N個の文書に対して、部分類似単語列を予備知識なしで自己組織的に検出する手法の提案。単語列の配列構造により類似領域を判定するが、通常の接尾辞配列ではなく、単語を出現頻度の少ない順に並び替え、辞書順に並べる。こうすることで、特徴的な単語が前のほうに来ることになり、類似領域が配列中で近くに集まる。

かなり目から鱗の手法。エピソード検索と非常に近いことをやろうとしているように思われる。応用できないかな。

二分決定グラフ(BDD)を活用したデータマイニング・知識発見技術の最近の話題

2007-06-19T13:15:00.000+09:00

湊真一, 電子情報通信学会技術報告 AI2007-6, pp.27-32, 2007.5.

湊さんの解説記事。ZBDDが何者か、データマイニング関係で最近いかに重要か、ということは分かったが、BDDに比べてZBDDの何がいいのか、データマイニングに関して本質的に何が効いているのか（突き詰めれば、論理関数が何を表現しているのか）はまだよくわかっていない。

それにしても、湊さん、BDD一筋20年ですよねえ。いやすごいもんだ。

Knuth–Morris–Pratt algorithm - Wikipedia, the free encyclopedia

2007-06-19T02:28:00.000+09:00

Knuth–Morris–Pratt algorithm - Wikipedia, the free encyclopedia

古典的文字列検索アルゴリズムだが、詳細を知らなかったので、読んでみた。論文は簡単に入手できなかった。検索自体は簡単で、partial match table が検索パタン W を1回走査するだけで構築できることがポイントである。ただし、上記ページにもある通り、検索文字列SにWの部分パタンが頻繁に出現しないとあまり速くならないため、自然言語の検索では有効に働きにくい。

開始

2007-06-19T01:29:00.000+09:00

以前から、読んだ論文についての備忘録や研究のメモをどうするか、試行錯誤を続けていた。論文をdel.icio.usに放り込んだこともあるし、デスクトップアプリもいろいろ試した。紙ベースの管理もやった。が、どれもうまくいかなかった。

うちの業界ですら、論文はWWWばかりでなく、紙ベースのものもある。だからWWWリソースのみを扱うブックマーク系ではうまくいかない。さりとてデスクトップアプリだと、共有するのが大変である。紙だと検索がつらい。論文は「超整理法」ではうまくいかない。

いろいろ考えて、ブログにメモを連ねていってはどうかと思いついた。まとまった文章になる前のメモや、読んだ論文の覚え書きみたいなものを想定しているので、本体のブログとは分けて、新しく開設することにした。そんなものなので、あまり積極的に宣伝はしないかも。

まとまった文章はこれくらいにして、メモ書きをスタートすることにしよう。