問題タブ [string-algorithm]

(この質問は音楽に関するものではありませんが、ユースケースの例として音楽を使用しています。)

音楽では、フレーズを構造化する一般的な方法は、中間部分が 1 回以上繰り返される音符のシーケンスです。このように、フレーズはイントロ、ループパート、アウトロで構成されています。以下に一例を示します。

イントロが [ EEE ] 繰り返し部分が [ FGA F ] で、アウトロが [ CD ] であることが「わかります」。したがって、リストを分割する方法は次のようになります

ここで、最初の項目はイントロ、2 番目の繰り返し部分の繰り返し回数、3 番目の部分はアウトロです。

このような分割を実行するアルゴリズムが必要です。

ただし、リストを分割する方法が複数ある可能性があるという注意点が 1 つあります。たとえば、上記のリストは次のように分割できます。

しかし、これはイントロとアウトロが長いため、より悪い分割です。したがって、アルゴリズムの基準は、ループ部分の長さを最大にし、イントロとアウトロを合わせた長さを最小にする分割を見つけることです。つまり、正しい分割

は

イントロとアウトロを合わせた長さは2で、ループ部分の長さは9です。

また、イントロとアウトロは空にすることができますが、「真の」繰り返しのみが許可されます。したがって、次の分割は許可されません。

シーケンスの最適な「圧縮」を見つけることと考えてください。一部のシーケンスでは繰り返しがない場合があることに注意してください。

これらの退化したケースでは、適切な結果が許容されます。

アルゴリズムの私の実装は次のとおりです。

それが正しいかどうかはわかりませんが、説明した簡単なテストには合格しています。それに関する問題は、それが遅くなることです。接尾辞ツリーを見てきましたが、私が求めている部分文字列は重複せず隣接している必要があるため、それらは私のユースケースに適合していないようです。

Longest Common Subsequence (LCS)問題は次のとおりです: 2 つのシーケンスAとが与えられた場合、とBの両方で見つかった最長のサブシーケンスを見つけます。たとえば、 と が与えられた場合、最長の共通部分列はです。ABA = "peterparker"B = "spiderman""pera"

誰かがこのLongest Common Subsequenceアルゴリズムを説明できますか?

書かれているアルゴリズムは の長さを見つけますが、変更して完全なlongest common subsequenceものを見つけることができます。longest common subsequence

leetcode linkで同等の問題に対する最速のpythonソリューションを調べていたときに、このアルゴリズムを見つけました。このアルゴリズムは、問題に対する最速の Python ソリューション (40 ミリ秒) であり、時間の複雑さもあるようです。これは、他のほとんどのソリューションO(m log m)の時間の複雑さよりもはるかに優れています。O(m*n)

なぜそれが機能するのか完全には理解できず、Longest Common Subsequence問題に対する既知のアルゴリズムを探して他の言及を見つけようとしましたが、そのようなものは見つかりませんでした。私が見つけた最も近いものは、実際にもあると言われているHunt–Szymanski algorithm リンクO(m log m)でしたが、同じアルゴリズムではないようです。

私が理解していること：

1. indeces_afor ループで小さい方のインデックスが保持されるように逆にiAsなります (これは、以下のウォークスルーを実行するとより明確になります)。
2. 私が知る限り、iAsfor ループはlongest increasing subsequenceof を見つけindeces_A_filteredます。

ありがとう！

たとえば、アルゴリズムのウォークスルーを次に示しますA = "peterparker"。B = "spiderman"