12

文字列タイリングを行う効率的なアルゴリズムを探しています。基本的に、文字列のリスト ( 、 、 、 など) が与えられ、BCD結果CDEのABCタイルA化された文字ABCDE列はになるはずです。BCDCDEBCDEABCABCDE

現在、私は次のように動作する少し素朴なアルゴリズムを使用しています。文字列のランダムなペアから始めて、たとえばBCDand CDE、次を使用します（Javaで）：

public static String tile(String first, String second) {
  for (int i = 0; i < first.length() || i < second.length(); i++) {
    // "right" tile (e.g., "BCD" and "CDE")
    String firstTile = first.substring(i);
    // "left" tile (e.g., "CDE" and "BCD")  
    String secondTile = second.substring(i);
    if (second.contains(firstTile)) {
      return first.substring(0, i) + second;
    } else if (first.contains(secondTile)) {
      return second.substring(0, i) + first;
    }
  }
  return EMPTY;
}

System.out.println(tile("CDE", "ABCDEF")); // ABCDEF
System.out.println(tile("BCD", "CDE")); // BCDE
System.out.println(tile("CDE", "ABC")); // ABCDE
System.out.println(tile("ABC", tile("BCX", "XYZ"))); // ABCXYZ

これは機能しますが、同じ文字を何度も反復するため、あまり効率的ではありません。

それで、これを行うためのより良い（より効率的な）アルゴリズムを知っている人はいますか？この問題は DNA 配列アラインメントの問題に似ているので、この分野の誰か (そしてもちろん他の人も) からのアドバイスは大歓迎です。また、配置を探しているのではなく、タイリングを探していることにも注意してください。

私は現在、アルゴリズムの漸近的な複雑さを改善するためにRabin-Karp アルゴリズムの適応を探していますが、この問題をさらに掘り下げる前にアドバイスを聞きたいです。

前もって感謝します。

あいまいさがある状況 (たとえば、{ABC, CBA}結果がABCBAorになる可能性がある) のCBABC場合、任意のタイルを返すことができます。ただし、このような状況はめったに発生しません{This is, is me} => {This is me}。これは、前述のアルゴリズムが機能するように操作された単語をタイリングしているためです。

類似の質問:オーバーラップによる文字列連結の効率的なアルゴリズム

4

5 に答える 5

4

文字列を最初の文字、次に長さ (最小から最大) で並べ替えてから、重複する文字列の連結に関するこの質問にある KMP に適応を適用します。

于 2009-09-18T02:27:49.153 に答える
2

これは 2 つの文字列のタイリングで機能し、substring と contains を使用する現在の実装よりも効率的であると思います。概念的には、「左」文字列の文字をループして、「右」文字列の文字と比較します。2 つの文字が一致する場合は、正しい文字列の次の文字に移動します。どの文字列の最後に最初に到達したかによって、また最後に比較した文字が一致するかどうかに応じて、可能なタイリング ケースの 1 つが識別されます。

2 つ以上の文字列を並べて表示する時間の複雑さを改善する方法は考えていません。複数の文字列に関する注意点として、以下のこのアルゴリズムは、単一の「左」文字列と複数の「右」文字列のタイリングを一度にチェックするように簡単に拡張できます。 ("ABC", "BCX", "XYZ") または ("ABC", "XYZ", BCX") のどちらを行うかを、すべての可能性を試してみてください。

string Tile(string a, string b)
{
    // Try both orderings of a and b,
    // since TileLeftToRight is not commutative.

    string ab = TileLeftToRight(a, b);

    if (ab != "")
        return ab;

    return TileLeftToRight(b, a);

    // Alternatively you could return whichever
    // of the two results is longest, for cases
    // like ("ABC" "BCABC").
}

string TileLeftToRight(string left, string right)
{
    int i = 0;
    int j = 0;

    while (true)
    {
        if (left[i] != right[j])
        {
            i++;

            if (i >= left.Length)
                return "";
        }
        else
        {
            i++;
            j++;

            if (i >= left.Length)
                return left + right.Substring(j);

            if (j >= right.Length)
                return left;
        }
    }
}
于 2009-09-18T02:06:07.693 に答える
1

オープン ソース コードが受け入れられる場合は、スタンフォード大学のSTAMPベンチマーク スイートでゲノムベンチマークを確認する必要があります。これは、探しているものとほとんど同じです。一連の文字列 (「遺伝子」) から始めて、すべての遺伝子を組み込んだ最短の文字列を探します。たとえば、ATGC と GCAA がある場合、ATGCAA が見つかります。4文字のアルファベットに制限するアルゴリズムについては何もないので、これはあなたを助けることができるはずです.

于 2009-09-21T13:21:03.327 に答える
0

最初に質問することは、{CDB、CDA} の耕作を見つけたいかどうかです。1回の耕うんはありません。

于 2009-09-17T20:48:53.297 に答える
0

興味深い問題です。ある種のバックトラックが必要です。たとえば、次の場合:

ABC, BCD, DBC

DBC と BCD を組み合わせると、次のようになります。

ABC, DBCD

これは解決できません。しかし、ABC と BCD を組み合わせると、次のようになります。

ABCD、DBC

次のように組み合わせることができます。

ABCDBC.
于 2009-09-18T12:03:16.910 に答える