Topic #7 -- Tries and suffix trees

http://www.cs.mcgill.ca/~cs251/oldcourses/1997/topic7/

trie（トライ）とは、k分位置木 (k-ary position tree)
で、辞書（連想配列）へのアクセスを効率化するためのデータ構造である。
辞書は、ある文字列がその辞書に入っているかどうかを調べる機能を持つ。
文字列のアルファベットは定数個とし、文字列には端記号が付けられているものとする。

非コンパクトtrie
枝のラベルがすべて1文字。
調べたい文字列の文字に対応する枝を、先頭文字から順にたどり、葉に行き着けば辞書にその文字列がある、ということ。
連想配列の場合、葉に、その文字列に対応するデータがある。
実装には、各ノードにアルファベットの大きさのポインタの配列を置く方法と、
配列ではなく連結リストでポインタを保持する方法がある。

コンパクトtrie
非コンパクトtrieにおいて、葉の直前の、分岐のないノードを削除したもの。
調べたい文字列の文字の枝をたどり、葉に行き着いたとき、
葉に格納されている文字列（文字列の残りでもよい）と調べたい文字列を比較し、一致すればその文字列がある、ということ。

PATRICIA[2005-09-03-1]
コンパクトtrieにおいて、分岐のないノードを統合したもの。
枝につくラベルは1文字以上になる。
通常、サイズ2のアルファベットで構成し（サイズがそれ以上ならサイズ2のアルファベットに符号化し）、
ノードに文字列中での分岐位置を格納し、枝には文字をラベル付けする。
調べたい文字列に対応する葉に行き着く方法：
ノードに書かれた位置の文字に対応する枝に進む。
葉に着いたら、そこに格納された文字列と調べたい文字列を比較し、一致すれば「ある」ということ。

suffix trie
ある文字列に対するすべての接尾辞を格納する辞書である、
非コンパクトtrie、または、コンパクトtrie、PATRICIA。
特に、PATRICIA、つまり、全ての分岐のないノードを統合したものを、Suffix Treeという。