問題タブ [suffix-tree]

複数の固定長文字列の同じ位置から、可能な限り最長の共通部分列をすべて見つけようとしています (合計で 700 個の文字列があり、各文字列には 25 個のアルファベットがあります)。最長の共通サブシーケンスには、少なくとも 3 つのアルファベットが含まれ、少なくとも 3 つの文字列に属している必要があります。だから私が持っている場合：

私は答えが必要です：

私の1つの問題は、これをできるだけ速くする必要があることです。サフィックスツリーで答えを見つけようとしていますが、サフィックスツリーメソッドの解決策は.サフィックスツリーは["ab","pq"]複数の文字列から連続した部分文字列しか見つけることができません.共通の最長共通部分列アルゴリズムはこの問題を解決できません. 時間コストを抑えてこれを解決する方法を知っている人はいますか? ありがとう

Ukkonen の論文の手順を変更して、単語がテキストに出現する回数の値を保持するにはどうすればよいですか。文字列の頻度も提供する実装はありますか?

私が望む変更は、文字列「hehe」のようなものです。すべての「h」、「e」、「he」の頻度カウントは、ツリー内で 2 にする必要があります。レスト ノードのデフォルト値は 1 です。

これまでで最高のようなライブラリと、このような以前の質問がいくつか見つかりました。

しかし、どれも私の問題に対する十分な解決策を説明していません。また、非常に大きな辞書ファイル (約 10 億語) を処理する必要があります。次に、アルゴリズムは非常に高速である必要があります。そして、私はスペースについて少し妥協する準備ができています.

サフィックス ツリーを使用して、(部分文字列ではなく) 個別の部分列の数を数えることはできますか?

定義: 文字列のサブシーケンスは、残りの文字の相対位置を乱すことなく文字の一部を削除することによって、元の文字列から形成される新しい文字列です。(つまり、「ACE」は「ABCDE」のサブシーケンスですが、「AEC」はそうではありません)。

では、String S = "rabbbit"、サブシーケンスのパターン P = "rabbit" が与えられた場合、サフィックス ツリーを使用して、S 内の P の異なるサブシーケンスの数を見つけることができますか?

手動検査から 3 を返す必要があります。

「ウサギ」の接尾辞ツリーを描画してこの問題を解決することで、誰かがこのトピックについて良い教育をしてくれると本当にありがたいです。

注 - この問題は DP などの他の手法で解決できますが、接尾辞ツリーを使用して解決できるかどうかに興味があります。ありがとう！

この記事では、サフィックス ツリーを利用してマッチング時間を改善する近似部分文字列マッチング手法について説明します。各回答は、異なるアルゴリズムに対応しています。

1. P部分文字列の近似一致では、文字列内の部分文字列 (パターン) を見つけようとしますが、不一致はT許容されます。k
2. サフィックス ツリーの作成方法については、ここをクリックしてください。ただし、一部のアルゴリズムでは追加の前処理が必要です。

新しいアルゴリズムを追加し (不完全であっても)、回答を改善するように人々を招待します。

私は今学期にアルゴリズムを勉強しており、Aho-Corasick 文字列マッチング アルゴリズムと接尾辞ツリーを構築するための Ukkonen のアルゴリズムについて読みました。

私はそれらの両方を読みましたが、障害リンクがプレフィックスをチェックし、サフィックスリンクがサフィックスをチェックすることを除いて、これら2つの主な基本的な違いを理解できません。

これら2つのアルゴリズムの違いは何ですか?