algorithm - サフィックスツリー検索時間

Question

以下の発言の理由を知っている人はいますか？または、この種の質問をするためのより良いウェブサイトはありますか? 任意のポインタをいただければ幸いです。

パターンが (長さ n) のテキストに k 回出現する場合、そのテキストのサフィックス ツリーで k 回すべてのパターンを検索すると、O(n+k) のコストがかかります。

Answer 1

サフィックス ツリーの検索にかかる時間は、検索するパターンの長さに比例します。ミシシッピのサフィックス ツリーを作成し、ssi を検索したとします。実行する必要があるルックアップは 3 です。時間は O(n) で、n はパターンの長さです。

Answer 2

このステートメントを見つけた場所によっては、コンテキストでそれが真実である特定の理由がある場合があります.

ただし、「+k」の通常の理由は、ユーザーに返される結果リストで見つかった各一致を挿入するのに O(k) 余分な操作が必要だからです。サフィックス ツリーの代わりに反転ファイルが使用される場合、これは必ずしもそうではありません。なぜなら、インデックスで見つかった反転リスト (投稿リスト)は既に最終結果リストだからです (少なくとも (a) クエリが単一のトークンのみで構成され、(b) インバーテッド リストは圧縮されずに格納されます)。

しかし、接尾辞ツリーは通常 (特別に準備されていない限り)、そのような一致リストを含みません。したがって、マッチング中に、ツリーを通るパスを特定し、内部ノードで終了します。そこから、その内部ノードのサブツリー内のすべてのパスをたどって、一致の実際の位置を示すリーフ ノード (一致ごとに 1 つのリーフ ノード) を特定し、返される結果リストに一致位置を挿入する必要があります。ユーザー。この最後のステップには、O(k) 時間がかかります。

また、見つけた内部ノードのサブツリー内のすべてのパスをたどると、かなりの余分な時間がかかる可能性があることに注意してください。全体の複雑さは O(n+k) よりもさらに高くなります。これは、内部ノードからサブツリー内のリーフ ノードへの直接ポインタがあるかどうかによって異なります。