問題タブ [lcs]

したがって、基本的には、次のような長さが等しくないトレーニングおよびテスト データ セット (一連の配列) を扱っています。

私は機械学習分野に不慣れで、これらの長さが等しくない入力配列を同じ長さにする方法に行き詰まっているため、既存の機械学習アルゴリズムを簡単に活用できます..

現在、Largest Common Sequence を使用して、長さが異なる入力配列間の類似性を見つけることが考えられます。

しかし、基本的に LCS 情報を取得した後、入力配列を同じ長さの配列に変換するにはどうすればよいでしょうか..?

私は正しい道を進んでいますか？誰か助けてくれませんか？

この後、私は完全に頭がおかしくなりました。小さなファイルと大きなファイルの 2 つのファイル間で最も長い共通部分文字列を見つける必要があります。どこから検索を開始すればよいかさえわかりません。これまでに持っているものは次のとおりです

これまでに行ったことは、各ファイルを文字列ビルダーに入れ、次に文字列に入れて二重スペースを取り除くことでした (MobyDick.txt でよく出てきました)。このコードを見つけました

このコードは役立ちますが、小さなファイルでのみ役立ちます。大きなファイルで実行するたびに、「メモリ不足: Java ヒープ領域」エラーが発生します。ヒープスペースの問題から逃れるには適切なアルゴリズムが必要ですが、Javaメモリを増やすことはできません。誰かが私を助けたり、正しい方向に向けたりできますか?

標準の linuxコマンドをいじってみたところ、出力で次のタイプのグループ化を回避する方法が見つかりませんでした (ここでのdiff出力リストでは、.unified format

この質問は、各行が他のファイルの対応する行とわずかに異なる場合を対象としています。対応する行の隣に各行を表示する方が便利です。

このようなグループを比較出力に表示する代わりに、次のようにします。

- line 1 - line 2 - line 3 + line 1 modified + line 2 modified + line 3 modified

これを取得するには：

- line 1 + line 1 modified - line 2 + line 2 modified - line 3 + line 3 modified

もちろん、これは便利な質問です。これは、独自のコードを記述して diff 出力を後処理するか、独自のアルゴリズムで lcs アルゴリズムから分岐することで実現できます。plain diff -U0出力形式は、このグループ化プロパティを除いて私のニーズに非常によく適合するため、wdiff などのバリアントはあまり役に立たないと思いますが、wdiff は私の場合に最適ではない他の側面を導入します。

UIツールではなく、コマンドラインの方法、またはコードで使用できるライブラリを探しています。

2 つの別個の文字列を比較する際に、2 つの別々の文字列で最も長く繰り返される部分文字列のアルゴリズムを作成する方法についてのヒントしか見つけることができません。しかし、私が助けを必要としているのは、1 つの長い文字列 (テキスト ファイルから読み取られる) で最も長く繰り返される部分文字列を見つける方法です。それを行う方法についてのヒントが見つかりません。誰でも私を助けてくれますか？

TACGCTGGTACTGGCAT と AGCTGGTCAGAA の 2 つのシーケンス間の LCS を見つけようとしています。どのシーケンスが一般的か (GCTGGT) をバックトラックできるように、答えを行列として出力する必要があります。以下のコードを使用すると、次のエラーが発生します。IndexError: リスト インデックスが範囲外です。以下のコードでこのエラーを回避するにはどうすればよいですか?

2 つの DNA 配列の LCS を見つけようとしています。行列形式と、最長の共通シーケンスを含む文字列を出力しています。ただし、コードでマトリックスとリストの両方を返すと、次のエラーが発生します: IndexError: string index out of range

変数 temp と higestcount を含むコーディングを削除すると、コードは行列を適切に出力します。マトリックスに同様のコーディングを使用してリストを生成しようとしています。このエラーを回避する方法はありますか? シーケンス AGCTGGTCAG および TACGCTGGTGGCAT に基づくと、最も長い共通シーケンスは GCTGGT になります。

LCSの問題には時間が必要であることを知っています〜O（m n）ここで、mとnはそれぞれ2つのシーケンスXとYの長さです。しかし、私の問題は少し簡単なので、~O(m n) よりも高速なアルゴリズムを期待しています。

これが私の問題です：

入力：

正の整数 Q、2 つのシーケンス X=x1,x2,x3...xn および Y=y1,y2,y3...yn、両方とも長さ n。

出力：

X と Y の LCS の長さが少なくとも n - Q の場合は true。

そうでなければ、偽。

よく知られているアルゴリズムのコストはここでは O(n^2) ですが、実際にはそれよりも優れた処理を行うことができます。共通の要素を見つけることなく、いずれかのシーケンスで Q 個の要素を削除するたびに、結果は False を返すためです。O(Q*n) に匹敵するアルゴリズムがあるはずだと誰かが言っていましたが、私にはわかりません。

更新: すでに答えが見つかりました!

テーブル c[i,j] の対角ブロックを計算するだけでよいと言われました。なぜなら、|ij|>Q の場合、両方のシーケンスに一致しない要素が既に Q 個以上あることを意味するからです。したがって、|ij|<=Q の場合にのみ c[i,j] を計算する必要があります。