問題タブ [suffix-tree]

これは、入力テキスト「mississippi」のサフィックス ツリーのビジュアル グラフです。この例では、検索するキーワードは「si」です。「si」の最初のインデックスを取得する方法を理解していると思います

• ルートノード #1 から開始
• 最初のエッジは「s」なので、ノード #2 に移動します
• ノード #2 の 2 番目のエッジは「i」であるため、ノード #7 を取得します。このノードはインデックスをテキストに格納します。

しかし、「si」の 2 番目の出現については... サブツリー #7 で次の出現を検索し続けますか? 私には本当に意味がありません。

または、複数のインデックスをサポートするためにツリーを別の方法で組み立てる必要がありますか?

Input: string S = AAGATATGATAGGAT.

Output: Maximal repeats such as GATA (as in positions 3 and 8), GAT (as in position 3, 8 and 13) and so on...

• A maximal repeat is a substring t occurs k>1 times in S, and if t is extended to left or right, it will occur less than k times.

• An internal node’s leaf descendants are suffixes, each of which has a left character.

• If the left characters of all leaf descendants are not all identical, it’s called a “left-diverse” node.

• Maximal repeats is left-diverse internal nodes.

Overall idea:

• Build a suffix tree and then do a DFS (depth first search) on the tree

• For each leaf, label it with its left character

• For each internal node:

• If at least one child is labelled with *, then label it with *

• Else if its children’s labels are diverse, label with *.

• Else then all children have same label, copy it to current node

Is the above idea is correct? How does the pseudo-code to be? Then I can try to write programming myself.

接尾辞木は、文字列に関連する多数のタスクにとって優れた便利な構造であることがわかりました。それらについて詳しく知りたいと思います。誰かがこれらのことを理解するための良い出発点を提案できますか？つまり、それを実装する既製のコードやライブラリは必要ありませんが、それらがどのように構築され、それらを使用して何ができるかを示すチュートリアルが必要かもしれません。私は「レクリエーションプログラミング」を楽しんでおり、接尾辞木は私の学ぶべきことのリストの上位にあります:)

PS：私はDelphi / pascalが好きですが、どの言語のチュートリアルでも大歓迎です。

C++ でサフィックス ツリーを構築するための Ukkonen のアルゴリズムの実装はありますか? 高水準言語での実装も適切です。

これはインタビューの質問です：

文字列を指定して、辞書内の単語であるすべての順列を見つけます。

私の解決策：

辞書のすべての単語を接尾辞木に入れてから、ツリー内の文字列の各順列を検索します。

検索時間はO(n)、です。ここnで、は文字列のサイズです。ただし、文字列にはn!順列がある場合があります。

どうすれば効率を改善できますか？

少し前に、ディスクからのサフィックス ツリーの保存/取得に関する質問を投稿しました。最終的にはうまくいきましたが、今は構築が非常に遅いので、今はウッコネンのアルゴリズム (線形構築) を台無しにしたくありません。

そのため、ツリーをスレッドセーフにすることなくプロセスを高速化するために、同時挿入を行いたいと考えました。

サフィックス ツリーは単語を最初の文字で格納します (私の前の質問に投稿された画像を見てください)。したがって、単語 Banana はルート ノードの 'B' 子にあり、Apple は 'A' 子などになります。 . したがって、'B' で始まる単語を挿入しても、'A' で始まる挿入が妨げられることはありません。私の考えは、挿入される一連の単語の最初の文字ごとにスレッドを作成することです。「A」を挿入するスレッド、「B」を挿入する別のスレッドなどです。

Executerだから私は、それぞれの単語のキューに単語を追加するだけ のクラスについて考えていましたProcess（存在しない場合は最初に作成してください）。

そして、クラスProcessは挿入を行うものです。各Processインスタンスは独立したスレッドであり、Queue挿入する単語が含まれています。

このProcessクラスでは、私が問題を抱えている場所です。threading.Thread各インスタンスはスレッドである必要があるため、から継承する必要があると思いますが、すべてのテキスト処理が完了するまでどうすればそれを維持できますか? つまり、その単語から単語を挿入する必要がQueueありますが、Queueが空の場合、スレッドが終了することはありません。さらに単語がいっぱいになるまで待ち続けてQueue、「目覚め」、挿入を続けます。

入力として文字ストリームがあるとします。

文字列全体 を最初から
再処理せずに、新しい文字が追加されるたびに最も長い回文部分文字列を見つける最適な方法は何ですか?

新しい文字が入力されるたびに、以前に処理された文字列 に移動することは避けたいと思います。

使用できるツリー データ構造はあります
か。 1. 新しいキャラクターごとに最初から再構築しないこと。
2. 文字列が徐々に長くなるにつれて、ノードとリーフをシフトできる場所。

文字列用 (プレフィックス ツリー) と
文字列の反転用 (サフィックス ツリー) の 2 つのツリーを構築する場合はどうでしょうか。

接尾辞ツリー/配列を線形時間で構築するのに役立つPythonのCベースの拡張機能を知っているかどうか疑問に思っていますか?

ウィキペディアでは、人々が使用できる多くの顔文字を定義しています。このリストを文字列内の単語に一致させたい。私は今これを持っています：

出力：

したがって、原則としてこれは機能します。ただし、次の 2 つの質問があります。

1. ご覧のとおり、':-)' の代わりに ':-)' のように、配列内の各絵文字の周りにスペースを入れています。これにより、配列が読みにくくなっていると思います。スペースなしで顔文字を保存する方法はありますが、それでも $string と一致し、それらの周りにスペースがありますか? (そして、コードは今と同じくらい効率的ですか?)

2. それとも、顔文字を 1 つの変数に入れ、スペースを爆発させて $string をチェックする方法はありますか? 何かのようなもの

   $emoticons = array( '[HAPPY]' => ">:] :-) :) :o) :] :3 :c) :> =] 8) =) :} :^)", '[SAD] ' => ":'-( :'( :'-) :')" //etc...

3. str_replace はこれを行う最も効率的な方法ですか?

何百万もの文字列をチェックする必要があるため、処理時間を節約する最も効率的な方法を探しています:)

私は自分の仕事のためにウッコネンの接尾辞ツリーを読んでいて、次のことが正しいかどうかを確認したかった.

Ukkonen Suffix Tree で次のように言うのは正しいでしょうか?

リーフ ノードにつながるエッジのみが、複数の連続した文字をその一部として圧縮できます。また、内部ノード間のエッジ (たとえば、ルートから内部ノードまで) は、1 つの文字のみを表すことができます。