3

サフィックス ツリーで循環文字列を使用できますか? したがって、最後の文字の後にリストの最初の文字が続きます。

もしそうなら、この接尾辞ツリーの表現は通常の接尾辞ツリーとどう違うのですか?

4

3 に答える 3

1

「使用」の意味によって異なります。

1) まず、あなたの質問を最も直接的な方法で解釈して、長さ n の円形の文字列、つまり n 文字ごとに繰り返される無限の文字列を考えてみましょう。このようなオブジェクトには、通常の意味での接尾辞がありません。これは、終わらないためです。そのため、接尾辞ツリーを構築することはできません。

2)しかし、アイデアは確かに、最後の文字から最初の文字へのリンクを使用する循環ストリングの有限表現を持っているということです。同様に、循環ストリングのすべての (無限に長い) 接尾部を表す循環接尾部ツリーへのリンクを使用して、特定の接尾部ツリーを拡張できます。これは、各リーフからノードのルートへのリンクを挿入しても実行できないことに注意してください。文字列の接尾辞ですが、そのような円形文字列の葉からは、1 つの出力エッジしか存在できません。例: "mississippi$" の接尾辞 "ssippi$" を表すリーフには、無限ラベル "mississippi$mississippi$mississippi$...." を持つ発信エッジが必要であり、他のエッジはありません。ツリーのルートにリンクすると、間違った継続がさらに多くなります。

したがって、次の 2 つのことが必要です。

  • 葉から外に出るエッジ (これは面白いコンセプトです)。各リーフは 1 つの出力エッジを取得します。
  • 無限のラベルを持つエッジ。このラベルは、円形の文字列として表すことができます (その円形の文字列は、葉のすべての出力エッジで同じになります)。

これにより、循環ストリングのすべての (無限の) サフィックスの有効な表現が得られます。

3）その表現が何かに役立つかどうかはよくわかりません。接尾辞ツリーを構築する目的が部分文字列検索を有効にすることである場合、循環文字列 (リンクを含まない) の有限表現をそれ自体に連結し、そこから接尾辞ツリーを構築するという通常のトリックで十分です。自体が n 文字より長い。

接尾辞ツリーの特定の他の用途では、さらに「無限」の概念を導入する必要があることに注意することも重要です。たとえば、特定のアプリケーションでは、ツリー ノードの文字の深さ (つまり、ルートから特定のノードにつながるエッジ ラベルの合計の長さ) をそのノードに格納する必要がある場合があります。上記で提案された「循環サフィックス ツリー」では、葉の外側のエッジがある種の特別な「制限内の葉」につながり、ラベルとして円形の文字列を運ぶことになります。このような循環文字列に一致するクエリには、一致する深さを追跡するための特別な方法が必要になります。これは、そのエッジに深さ情報を格納する内部ノードがないためです。

4)以上のことをすべて述べたが、実際には少なくとも 1 つのサフィックス ツリーの循環文字列への既知のアプリケーションがありますが、上記の (1)、(2)、または (3) の意味ではありません。サフィックスツリーの使用。むしろ、円形文字列の有限部分文字列のサフィックス ツリーを使用して、辞書編集上の最小回転の問題を解決します。この問題はWikipediaで説明されていますが、そこにリストされている解決策には接尾辞ツリーを利用するものは含まれていません。ただし、Dan Gusfield は、セクション 7.13のAlgorithms on Strings, Trees and Sequencesで解決策を説明しています。

アイデアは、長さ n の文字列 S の辞書編集的に最小の回転のセットを、円形文字列の最初の長さ n の部分文字列のセットと同等であると見なすことです。この問題は、辞書編集的に最小のカットオフ ポイントを見つける問題と同じです。Gusfield は、文字列 SS$ のサフィックス ツリーを構築することでそれを解決し、各ノードで辞書編集的に最小のエッジを取得してこのツリーをトラバースし、辞書編集的に最小のカットオフ ポイントに対応するノードに到達します。

したがって、(4) が示すように、循環文字列のコンテキストで接尾辞ツリーの特定の実用的な「使用」がありますが、それがあなたが興味を持っている種類の使用であるかどうかはわかりません。

于 2012-11-16T07:31:08.783 に答える
0

次の回避策を念頭に置いて、これが何のために必要かを考えます。

円形の文字列の接尾辞配列がある場合、これはほとんどの場合、文字列内のオフセットのリストであり、各オフセットで開始されるシーケンスは並べ替えられた順序になります。

ここで、ABCDを包んで作った円形のひもがあるとします。それ自体の文字の1つを除くすべて（ABCDABC）を追加して形成された文字列と、それから接尾辞配列を作成するとどうなるかを考えてみます。円形文字列（ABCD BCDA CDAB DABC）のすべてのシーケンスは、ABCDABC内に表示されるため、そこから接尾辞配列を作成すると、円形文字列から作成した場合と同じ接尾辞配列が得られ、一部のシーケンスには文字が追加されます終わり（ABCDの代わりにABCDABC）と短すぎるいくつかの余分なシーケンス（ABC）。サブシーケンスの長さ、または同等にABCDABC内の開始位置を確認するだけで、これらの両方のケースを認識できます。

明らかに、あなたはmississippimississipp内でpimを見つけることができます。

于 2012-11-15T20:18:27.163 に答える
0

はい、文字列の長さが有限であれば、循環文字列を格納できます。

ばんばんという言葉を考えてみましょう。

以下は構造です

root -> b -> a -> n -> b -> a -> n -> $

                    -> $

root -> a -> n -> b -> a -> n -> $

                -> $

root -> n -> b -> a -> n -> $

          -> $

ドル記号は、サフィックスの終了を表します

編集：

Java プログラミング言語を使用したサフィックス ツリーの適切な実装は、ここにあります。

編集：コメントセクションで尋ねられたように：

「mississippi という文字列があり、'pim' を検索したい場合はどうすればよいですか?」

pim はミシシッピのサフィックスではないため、検索は失敗します。

編集:しかし、pimは円形の文字列にあり、トライにも追加したい

これを行うには、prim を別の単語として扱い、それを trie に追加して、グローバルな拡張接尾辞 trie を形成する必要があります。

anb は、元の単語 banban の循環ストリングにあると考えてください。

したがって、グローバルな拡張サフィックス トライは次のようになります。

root -> b -> a -> n -> b -> a -> n -> $ (original word)

          -> a -> n -> $ (original word)

          -> $ (from anb)

root -> a -> n -> b -> a -> n -> $ (original word)

               -> $ (original word)

               -> b -> $ (from anb)

root -> n -> b -> a -> n -> $ (original word)

                -> $ (from anb)

          -> $ (original word)
于 2012-11-15T18:24:35.253 に答える