サフィックスツリーから部分文字列を削除するには？

Question

多くの文献を見直しましたが、サフィックスツリーへの部分文字列の削除や挿入に関する情報は見つかりませんでした。 UkkonenやMcCreightの樹木構築のアルゴリズムしかありません。
最下位の方法は、部分文字列を削除または挿入した後にツリーを再構築することです。しかし、私はそれが最良の方法であると考えています。
たとえば、（位置は0からカウントされます）：
私は「abcdef」という接尾辞ツリーを持っています.1から3までのシンボルを削除する必要があります。その後、「aef」という接尾辞ツリーを使用します。そして、私は位置1文字列から "as"を追加する必要があります。その後、私は "aasef"という接尾辞の木を持っていきます。 私を助けることができますか？

Answer 1

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

あなたが必要とするのは、最初に "接尾辞配列"とすると、文字とその場所の検索をより詳細に制御できるようになります。次に、 "キャッシュアルゴリズム"が置換えに役立ちます。

Answer 2

私はちょうどサフィックスツリーの作業を開始したばかりなので、間違っているかもしれませんが、挿入や削除がかなり根本的な方法でツリーを変更するようです。 「」最初に信じられないほど簡単です

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

末尾に「G」を追加または削除：

は「ABCDEF」は本当に些細な接尾辞木です。

しかし、私たちは「」途中で別のを突き出すと言う：

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

我々は戻って、私たちはこれに基づいてノードを挿入する必要があるかどうかを確認するために、最初からすべての文字を確認する必要があります。あなたは今、最後まで「EF」のようなものを挿入した場合

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

は、あなたを介して行って、あらゆる場所に新しいノードを追加する必要があるだろう：私たちは最後の文字を持っている場合と同じ！

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

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