サフィックスツリーが拡張サフィックスアレイよりも優れている場合を知りたいだけです。
「サフィックス ツリーを強化されたサフィックス アレイに置き換える」を読んだ後、サフィックス ツリーを使用する理由がわかりません。一部のメソッドは複雑になる可能性がありますが、接尾辞配列を使用してすべてを行うことができ、接尾辞ツリーで実行できることと同じ時間の複雑さを必要としますが、メモリは少なくて済みます。
ある調査では、接尾辞配列の方がキャッシュにやさしく、キャッシュミスが少ないため、より高速であることが示されました (そのため、キャッシュは再帰ツリー構造よりも配列の使用をはるかによく予測できます)。
では、サフィックス配列よりもサフィックスツリーを選択する理由を知っている人はいますか?
編集 OK、もっと知っているなら教えてください、これまでのところ:
- Suffixarray はオンライン構築を許可しません
- 一部のパターン マッチング アルゴリズムは、Suffixtree で高速に実行されます
- (追加) オンライン構築のため、hd a に保存し、既存の suffixtree を拡大することができます。SSD を使用する場合は、静かで高速である必要があります。