|
接尾辞木（せつびじき）またはサフィックス木（）は、与えられた文字列の接尾部を木構造(基数木)で表すデータ構造であり、多くの文字列操作の高速な実装に利用されている。 文字列 の接尾辞木は木構造であり、その枝には文字列が対応し、木構造の根から葉までの経路ごとにそれぞれ の接尾部の1つが対応している。従って、これは の接尾部に関する基数木である。 文字列 からそのような木構造を構築するには、 の長さに対して線形な時間と空間を要する。構築できれば、いくつかの操作が高速化される（ の部分文字列を探す、誤字をある程度許容した上での部分文字列特定、正規表現パターンとのマッチングなど）。接尾辞木は最長共通部分文字列問題の線形な解法の1つでもある。これらの高速化の代償として、接尾辞木に要するメモリ空間は文字列そのものを格納するのに要するメモリ空間よりもかなり大きくなる。 == 歴史 == この概念は ''position tree'' として 1973年、Weiner が初めて紹介した。ドナルド・クヌースはその論文を "Algorithm of the Year 1973" と評した。1976年、McCreight が構築法を大幅に単純化し、1995年には Ukkonen がさらに洗練させた。Ukkonen のアルゴリズムは接尾辞木を線形時間かつオンラインで構築する最初のアルゴリズム（文字列全体を入力する前から構築を開始できるアルゴリズム）であった。 == 接尾部の例 == ある文字列の接尾部とは、その文字列の先頭から1文字ずつ文字を除いていった残りの部分文字列全体を指す。例えば、"BANANA" の接尾部は次のようになる。 : BANANA : ANANA : NANA : ANA : NA : A 従って、長さ の文字列の接尾部としては、元の文字列も含めると 個の文字列が存在することになる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「接尾辞木」の詳細全文を読む スポンサード リンク
|