問題タブ [lcs]

問題: 2 つの文字列間の LCS の長さが必要です。文字列のサイズは最大 100 文字です。アルファベットはいつものDNAのもので、4文字の「ACGT」。動的なアプローチは十分に迅速ではありません。

私の問題は、たくさんのペア (私が見る限り数億のランク) を扱っていることです。LCS_length 関数の呼び出しを可能な限り最小限に減らしたと思うので、プログラムの実行を高速化する他の唯一の方法は、より効率的な LCS_Length 関数を使用することです。

通常の動的プログラミングのアプローチで実装することから始めました。それは正しい答えを与え、うまくいけば適切に実装されます。

それは O(mn) である必要があります (うまくいけば)。

次に、速度を求めて 、Myers によるO(ND) 論文 を提供するこの投稿Longest Common Subsequenceを見つけました。LCSを最短の編集スクリプト（SES）に関連付けるこれを試しました。彼らが与える関係は D = M + N - 2L で、D は SES の長さ、M と N は 2 つのストリングの長さ、L は LCS の長さです。しかし、これは私の実装では常に正しいとは限りません。私は私の実装を与えます（私は正しいと思います）：

主に例があります。例えば。"tomato" と "potato" (コメントしないでください) の LCS の長さは 4 です。実装では、SES (コード内の D) が 4 ではなく 2 として出力されるのは 5 サイスであることがわかります ( 「t」を削除、「p」を挿入、「m」を削除、「t」を挿入）。おそらく O(ND) アルゴリズムも置換をカウントするのではないかと思う傾向がありますが、これについてはよくわかりません。

実装可能なアプローチ (私は膨大なプログラミング スキルを持っていません) であれば、どんなアプローチでも大歓迎です。（たとえば、小さなアルファベットを利用する方法を誰かが知っている場合）。

編集: いつでも任意の 2 つの文字列間で LCS 関数を使用することを何よりも強調すると便利だと思います。したがって、数百万の他の文字列と比較して、s1 などの文字列だけではありません。s1000 で s200、s10000 で s0、s100000 で 250 の可能性があります。ほとんどの使用文字列も追跡できない可能性があります。近似アルゴリズムを実装しており、余分なエラーを追加したくないため、LCSの長さは近似ではないことが必要です。

編集: callgrind を実行しました。10000 個の文字列の入力の場合、文字列のさまざまなペアに対して、lcs 関数を約 50,000,000 回呼び出すようです。(10000 文字列は実行したい最小値であり、最大値は 100 万です (実行可能な場合))。

[注: 事前に検索したところ、すべてのサブシーケンスの LCS 問題を解決するためのアドバイスが見つかりませんでした。]

2 つの入力文字列に対してすべての最長共通サブシーケンスを返す「最長共通サブシーケンス」問題の解決策をコーディングするのに問題があります。ウィキペディアのページを見て、そこに疑似コードを実装しようとしましたが、「backtrackAll」メソッドで問題が発生しました。以下で LCS 行列を正しく計算していると思いますが、「backtrackAll」メソッドは空のセットを返します。私が間違っていることに関するヒントはありますか？

2 つのシーケンスの最長共通サブシーケンスを見つけるための動的計画法アルゴリズムがあります。2 つのシーケンス X と Y の LCS アルゴリズムを見つけるにはどうすればよいですか (正しさのテスト)

OKこれは私がやりたいことです:

2 つ以上の文字列を取得し、それらを「整列」します (DNA/RNA シーケンスなどはなく、それぞれに 1000 個ほどのアイテムがない通常の文字列のみ)。

ペアワイズ アラインメント (2 つの文字列をアラインする) については既にいくつかの作業を行っていますが、複数のペアをアラインしようとすると、「ギャップ」が問題を引き起こします。

例（私が現在テストしているもの）：

そして別の（より説明的な）例：

私が現在していること：

• 文字列を並べ替える (長い文字列がリストの最初に来る)
• 最初のペア : AB を整列させ、結果を取得します (たとえばR1)
• 次に、2 番目のペア :R1とC(結果はR2)を揃えます。
• 次に、3 番目のペアR2を揃えます。D
• 等々...

それで、あなたの心の中には何がありますか？どうすればそれを手に入れることができますか？より良い方法はありますか？（もちろんあるはず…）

私はPerl/Pythonまたはこれらの行に沿った何かでそれを行いたいと思っていますが、あらゆるタイプのコード/リファレンスは大歓迎です! :-)

オンラインで C++ の Longest Common Substring の実装を検索しましたが、適切なものが見つかりませんでした。部分文字列自体を返す LCS アルゴリズムが必要なので、LCS だけではありません。

ただし、複数の文字列間でこれを行う方法については疑問に思っていました。

私の考えは、2 つの文字列の間で最も長い文字列をチェックしてから、他のすべての文字列をチェックすることでしたが、これは非常に遅いプロセスであり、メモリ上で多くの長い文字列を管理する必要があり、プログラムが非常に遅くなります。

これを複数の文字列で高速化する方法について何か考えはありますか? ありがとうございました。

重要な編集 私が与えられた変数の 1 つは、最長の共通部分文字列が必要な文字列の数を決定するため、10 個の文字列を与えられ、それらすべての LCS (K=10)、または 4 の LCS を見つけることができますでもどの4つかはわからないので、ベスト4を見つけなければなりません。

そこで、Introduction to Algorithms book (CLRS) の Longest Common Subsequence アルゴリズムを C++ で実装しましたが、問題なく動作します。私がこのようなことをすると：

./lcs abc bc > OUTPUT

OUTPUTでファイルを開くと、次のvimように表示されます。

2 bc^@

どちらが正しいですか、その奇妙な^@記号はありません。私はいくつかのグーグルをしましたが、これはある種のNULLキャラクターのように見えますか?

私は前にこの問題に遭遇したことはありません..誰もそれを取り除く方法を知っていますか?

ありがとう！-kstruct

編集 印刷を行うコードは次のとおりです。

はどこlcsStringですかstd::string。それが役立つかどうかはわかりません...

問題10635 uvaの最長共通サブシーケンスから O(nlog n) 最長増加サブシーケンスへの削減を行う方法。問題を解決するために適用されるロジックに関して、助けが必要です。

特定の文字列を回文に変換するために必要な挿入の最小数を見つけるために、文字列（lcs_string）の最長共通部分列とその逆を見つけます。したがって、行われる挿入の数はlength（s）-length（lcs_string）です。

挿入の数を知る上で同等の回文文字列を見つけるには、どのような方法を採用する必要がありますか？

例えば ​​：

1）azbzczdzez

必要な挿入数：5回文文字列：azbzcezdzeczbza

同じ文字列に対して複数の回文文字列が存在する場合がありますが、1つの回文文字列のみを検索したいですか？

誰かが Ocaml 言語で一連の文字列の最長共通部分列を見つける方法を知っていますか?

Rubydiff-lcsライブラリは、あるシーケンスから別のシーケンスに取得するために必要なチェンジセットを生成するという素晴らしい仕事をしますが、出力の形式は私には多少混乱します。変更のリストを期待しますが、代わりに、出力は常に1つまたは2つの変更のリストを含むリストになります。複数の変更リストを持つことの意味/意図は何ですか？

次の簡単な例を考えてみましょう。

最後の変更が空白であるという事実を無視すると、なぜ1つではなく2つの変更リストがあるのでしょうか。