最終更新:2009-10-28 (水) 21:03:09 (5293d)  

Suffixなんとか
Top / Suffixなんとか

  • 接尾辞?

Suffix Array, Suffix Tree は任意の部分列を高速に列挙可能なデータ構造である。しか し、これらを利用するには、必要領域量が問題となる。

処理対象データがN Byte の時、

  • Suffix Arrays? は5N ～9NByte
  • Suffix Trees? は10N Byte から100N Byte

必要となり、対象とするデータが小さい場合のみしか適用できない。

Compressed Suffix Arrays

Suffix Array は検索対象文字列の全接尾辞を辞書式順序で整列させた時の各接尾辞番 号を並べ保存した配列であり、Compressed Suffix Arrays はそれを圧縮させたものである。 Suffix Array を用いることで任意の部分文字列検索、頻度計数等の処理を非常に高速に 計算できる。

検索対象文字列の長さがN Byte の時、

↑

Compressed Suffix Trees?

Suffix Tree は検索対象文字列の全接尾辞?から構成されたTrie を各節点が必ず2 つの子 を持つように枝を縮退させたものでありSuffix Array と比較し、さらに多くの文字列処理を 高速に処理することが可能である。Compressed Suffix Trees? はそれを圧縮したものである。

検索対象文字列の長さがN Byte の時

  • Suffix Tree が10N～100N Bytes のメモリが必要なのに対して
  • CST? ではその1/5～1/50 程度の約2N Byte のメモリが必要である。
↑

参考




検索：