7

多くの文献を調べましたが、部分文字列のサフィックス ツリーへの削除または挿入に関する情報は見つかりませんでした。ツリーを構築するためのアルゴリズムは Ukkonen または McCreight のみです。
最も貧弱な方法は、部分文字列を削除または挿入した後にツリーを再構築することです。しかし、それが最善の方法だと思います。
例 (位置は 0 からカウントされます):
"abcdef" のサフィックス ツリーがあり、1 から 3 までのシンボルを削除する必要があります。次に、"aef" のサフィックス ツリーがあります。そして、位置 1 の文字列「as」から追加する必要があります。そして、この後、「aasef」の接尾辞ツリーができます。手伝って頂けますか？

4

2 に答える 2

1

質問に 2 つのタスクが混在しています。最初に文字を検索し、次に文字を置き換えます。サフィックス ツリーは、最初の部分で文字を検索します。次に、その文字を新しい文字に置き換えるための 2 番目のアルゴリズムが必要です。文字が置換されると、元のサフィックス ツリーが無効になるため、ツリーを再度マップして 2 回目の置換を行う必要があります。

必要なものは 2 つあります。1 つ目は「サフィックス配列」です。これにより、文字とその位置の検索をより詳細に制御できます。2 つ目は、置換に役立つ「キャッシュ アルゴリズム」です。

于 2013-05-16T09:55:50.207 に答える
0

私はサフィックス ツリーを使い始めたばかりなので、間違っているかもしれませんが、挿入や削除によってツリーが根本的に変わる可能性があるようです。

"abcdef" は本当に些細なサフィックス ツリーです。

abcdef
├a..$
├b..$
├c..$
├d..$
├e..$
└f$

末尾に 'g' を追加したり、先頭の 'a' を削除したりするのは非常に簡単です。

しかし、真ん中に別の 'a' を押し込んだとしましょう:

abcadef
├a
│├b..$
│└d..$
├b
├c
├...

これに基づいてノードを挿入する必要があるかどうかを確認するために、最初からすべての文字を確認する必要があります。最後から文字がある場合も同じです。

abafef
├a
│├bafef$
│└fef$
├bafef$
├f
│├ef$
│└$
└ef$

「ef」のようなものを最後に挿入すると、新しいノードをあちこちに追加する必要があります。

文字を挿入すると、文字列内のすべての文字を再検査する必要があるように見えます。つまり、線形時間です。Ukkonen のアルゴリズムはすでに線形時間を要しているため、動的挿入アルゴリズムを使用する価値はありません。これでもかなり良いという確信を持って、毎回最初からツリーを再生成する必要があります。

スペースを気にしない場合は、ツリー生成アルゴリズムの各ステップを常にキャッシュすることができます。その後、ポイント x で挿入または削除するときが来たら、ポイント x まで構築されたツリーをロードするだけです。

于 2013-06-23T02:46:25.743 に答える