12:02:08 # Life Marisa Trieの論文を読んだのでメモ。 TrieというのはRetrievalから名付けられたデータ構造で、Retrievalに便利なようになっててコンパクトなデータ表現になっているデータ構造。 Marisa TrieというのはTrieの実装でNLP2011での発表資料とかがドキュメントからリンクされている。 一番ナイーブなTrieというのは一文字ごとにツリーのノードになっていて、文字列に対応する文字を全部たどっていくとデータが格納されているノード を発見できる。プリフィックスの同じ文字列を探索するときとかプリフィックス文字列まで検索してそれ以降はツリーをWalkしていけばよいので便利なデータ構造。 しかしそれのナイーブな実装では一致しないプリフィックスの文字列のためのノードが大量にできてしまいデータ効率が悪いので、一致しない文字列は一文字づつじゃなくてまとめて保持するというのがPatricia Trieのコンセプト。たとえば英語文字列では語尾数文字は一致しないことが多いので効率がよい。 ここまではまぁわかる。 あとDouble Trieで語尾から保持するというのとか、入れ子になるとか書いてあるんだけどまだ良くわかってない。LOUDSってなんですか。