最終更新:2009-10-28 (水) 21:03:09 (5293d)
Suffixなんとか
Top / Suffixなんとか
- 接尾辞?
Suffix Array, Suffix Tree は任意の部分列を高速に列挙可能なデータ構造である。しか し、これらを利用するには、必要領域量が問題となる。
処理対象データがN Byte の時、
必要となり、対象とするデータが小さい場合のみしか適用できない。
Compressed Suffix Arrays
Suffix Array は検索対象文字列の全接尾辞を辞書式順序で整列させた時の各接尾辞番 号を並べ保存した配列であり、Compressed Suffix Arrays はそれを圧縮させたものである。 Suffix Array を用いることで任意の部分文字列検索、頻度計数等の処理を非常に高速に 計算できる。
検索対象文字列の長さがN Byte の時、
- Suffix Array は文字列長がN の時5N~9NByteのメモリが必要なのに対し
- CSA ではその1/10 程度の0.3N~1Nのメモリが必要である。
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 のメモリが必要である。