Sublime Text スクリプトを作成して、数行のコードを整列させています。スクリプトは各行を取得し、定義済みの区切り文字 ( ,;:=) のセットで分割し、同じ幅にパディングされた「列」内の各セグメントと再結合します。これは、すべての行に同じ区切り記号のセットがある場合にうまく機能しますが、一部の行には余分なセグメントや末尾のオプションのカンマなどがある場合があります。
私の考えは、区切り文字の標準的なリストを考え出すことです。具体的には、いくつかの区切り文字列が与えられた場合、挿入のみを使用して、与えられた文字列のいずれかから形成できる最短の文字列を見つけたいと思います。いくつかの調査の後、これはグローバルな複数配列アラインメントのよく知られた問題であることがわかりました。ただし、ミスマッチはなく、一致とインデルのみが存在します。
残念ながら、動的プログラミングのアプローチは、少なくとも一般的なケースでは、文字列の数が指数関数的です。不一致が許可されていない場合、より迅速な解決策の希望はありますか?
ミスマッチが許されない場合でも、そのような希望はないという包括的な声明を出すのは少しためらいますが、そうではないことは確かです. 理由は次のとおりです。
シーケンス アラインメントを実行するときに生成される動的プログラミング テーブルのサイズは、およそ (文字列の長さ)^(文字列の数) であるため、実行時間/スペースの要件は指数関数的になります。それがどこから来たのかを感じてもらうために、それぞれの長さが 3 の 2 つの文字列 ABC と ACB の例を次に示します。これにより、3x3 テーブルが得られます。
A B C
A 0 1 2
C 1 1 1
B 2 1 2
このテーブルを左上から開始し、そこから右下に向かって初期化します。テーブル内の任意の場所に到達するための総コストは、その場所の数値で示されます (簡単にするために、挿入、削除、および置換のコストはすべて 1 であると想定しています)。特定の位置に到達するために使用される操作は、前の値から移動した方向によって決まります。右に移動するということは、一番上の文字列から要素を挿入していることを意味します。下に移動すると、横方向の文字列から要素が挿入されます。斜めに移動するということは、エレメントを上下から整列させることを意味します。これらの要素が一致しない場合、これは代替を表し、そこに到達するためのコストを増やします。
そして、それが問題です。不一致が許可されていないと言っても、テーブルの長さと高さの原因となる操作 (挿入/削除) を除外するわけではありません。さらに悪いことに、ミスマッチを認めないということは、潜在的な動きを排除することさえできません。2 つの要素が一致しない場合だけでなく、テーブル内の斜めの動きが可能な場合もあります。さらに、要素が一致するかどうかを確認する必要があるため、基本的にはまだその動きを検討しています. 結果として、これは最悪の場合の時間を改善することはできず、平均または最良の場合の時間にも実質的な影響を与える可能性は低いと思われます.
明るい面としては、これはバイオインフォマティクスの非常に重要な問題であるため、人々はいくつかの解決策を考え出しています. それらには欠点がありますが、あなたの場合には十分に機能する可能性があります（特に、文字列が4文字で構成されていないことを考えると、DNAの場合よりも偽のアラインメントを持つ可能性が低いと思われるため）アルファベット）。スター アラインメントとネイバー ジョインを見てみましょう。