多くの文献を見直しましたが、サフィックスツリーへの部分文字列の削除や挿入に関する情報は見つかりませんでした。 UkkonenやMcCreightの樹木構築のアルゴリズムしかありません。
最下位の方法は、部分文字列を削除または挿入した後にツリーを再構築することです。しかし、私はそれが最良の方法であると考えています。
たとえば、(位置は0からカウントされます):
私は「abcdef」という接尾辞ツリーを持っています.1から3までのシンボルを削除する必要があります。その後、「aef」という接尾辞ツリーを使用します。そして、私は位置1文字列から "as"を追加する必要があります。その後、私は "aasef"という接尾辞の木を持っていきます。 私を助けることができますか?サフィックスツリーから部分文字列を削除するには?
答えて
質問で2つのタスクをミックスしている場合は、最初に文字を検索し、2番目の文字を置き換えます。接尾辞ツリーは、最初の部分があなたのために文字を検索するので、その文字を新しい文字に置き換える第2のアルゴリズムが必要になります。文字が置き換えられると、元のサフィックスツリーは無効になります。したがって、ツリーを再度マップして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まで構築されたツリーをロードします。
- 1. MySQL - エントリから部分文字列を削除する
- 2. 文字列から部分文字列を削除しますか?
- 3. PHPの部分文字列の削除
- 4. Pandas DataFrame:列の文字列から不要な部分を削除する
- 5. VB.NETで文字列の部分を削除する
- 6. 文字列から削除
- 7. Ruby:配列内の他の文字列の部分文字列である文字列を削除する
- 8. 2文字間の部分文字列を削除する正規表現
- 9. 文字列から大文字小文字を削除する
- 10. PHPの爆発 - 文字列の最初の部分を削除し、最後の部分を削除します
- 11. C#のデータリスト内のラベルから文字列の部分を削除し
- 12. bashで文字列の最初の部分を削除するには?
- 13. 文字列と文字列をすべて文字列から削除する
- 14. 文字列から重複する文字を削除する
- 15. 文字列から部分文字列を抽出します。
- 16. JavaScriptオブジェクトから部分文字列を削除するにはどうすればよいですか?
- 17. 文字列jqueryから文字列を削除します
- 18. javaの文字列の一部を削除するには?
- 19. 文字列から小文字の部分文字列を簡単に削除する方法はありますか?
- 20. Java文字列から行末文字を削除する
- 21. 文字列からNULL文字を削除する方法
- 22. Nyquistの文字列から文字を削除する
- 23. 変数から文字列や文字を削除する
- 24. 文字列から不要な文字を削除する
- 25. 文字列から特定の文字を削除するR
- 26. Python文字列から文字を削除する
- 27. Pythonの文字列から特殊文字を削除する
- 28. 文字列から文字を削除する
- 29. 文字列から文字を削除する
- 30. 文字列から文字を削除する
あなたはより具体的ですか?私が見るところでは、あなたは文字列 "abdc"を挿入しました。そして今はそれを "abd"(部分文字列の削除)または "abced"(部分文字列の挿入)にしたいのですか? – ElKamina
はい、正しくありません – user2386656
対応する接尾辞配列["Dynamic Extended Suffix Arrays"](http://www-igm.univ-mlv.fr/~lecroq/articles/jda2009)の更新中に部分文字列を追加/削除できます。 pdf)(pdf)。しかし、サフィックスの木については何も言えません。 –