Algorithme de pavage de chaînes

Question

Je cherche un algorithme efficace pour faire pavage. , Vous êtes essentiellement donné une liste de chaînes, dites BCD, CDE, ABC, A, et la résultante carrelée chaîne doit être ABCDE, parce que BCD aligne avec CDE Cédant BCDE, qui est puis aligné avec ABC, ce qui donne la finale ABCDE.

Actuellement, j'utilise un algorithme légèrement naïf, qui fonctionne comme suit. En commençant par une paire aléatoire de chaînes, par exemple BCD et CDE, j'utilise les éléments suivants (en 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 

Bien que cela fonctionne, il est pas très efficace, car il itère sur les mêmes personnages encore et encore. Donc, quelqu'un connaît-il un meilleur algorithme (plus efficace) pour le faire? Ce problème est similaire à un problème d'alignement de séquence d'ADN, donc tout conseil de quelqu'un dans ce domaine (et d'autres, bien sûr) sont les bienvenus. Notez également que je ne cherche pas un alignement, mais un carrelage, car j'ai besoin d'un chevauchement complet de l'une des chaînes sur l'autre.

Je suis actuellement à la recherche d'une adaptation du Rabin-Karp algorithm, afin d'améliorer la complexité asymptotique de l'algorithme, mais j'aimerais avoir quelques conseils avant d'approfondir cette question.

Merci d'avance.

---

Pour les situations où il y a une ambiguïté - par exemple, {ABC, CBA} ce qui pourrait entraîner ABCBA ou CBABC -, tout carrelage peut être retourné. Cependant, cette situation se produit rarement, parce que je suis des mots de carrelage, par exemple. {This is, is me} => {This is me}, qui sont manipulés pour que l'algorithme susmentionné fonctionne.

question similaires: Efficient Algorithm for String Concatenation with Overlap

Answer 1

La première chose à demander est si vous voulez trouver le labourage de {PEH, CDA}? Il n'y a pas de labour unique.

Answer 2

Je pense que cela devrait fonctionner pour le pavage de deux chaînes, et être plus efficace que votre implémentation actuelle en utilisant la sous-chaîne et contient. Conceptuellement, je fais une boucle sur les caractères de la chaîne 'gauche' et les compare à un caractère dans la chaîne 'droite'. Si les deux caractères correspondent, je passe au caractère suivant dans la chaîne de droite. En fonction de la chaîne dont la fin est atteinte, et si les derniers caractères comparés correspondent ou non, l'un des cas de tuiles possibles est identifié.

Je n'ai pensé à rien pour améliorer la complexité temporelle du carrelage plus de deux chaînes. Comme une petite note pour les chaînes multiples, cet algorithme ci-dessous est facilement étendu à la vérification de la mosaïque d'une seule chaîne 'gauche' avec plusieurs chaînes 'droite' à la fois, ce qui pourrait empêcher un peu de boucler les chaînes si vous essayez de savoir s'il faut faire ("ABC", "BCX", "XYZ") ou ("ABC", "XYZ", BCX ") en essayant simplement toutes les possibilités.

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; 
     } 
    } 
} 

Answer 3

Commander les chaînes par le premier caractère, puis la longueur (plus petit au plus grand), et ensuite appliquer l'adaptation à KMP trouvés dans this question sur les concaténer des chaînes qui se chevauchent.

Answer 4

Problème intéressant. Vous avez besoin d'une sorte de retour en arrière. Par exemple, si vous avez:

ABC, BCD, DBC 

La combinaison DBC avec des résultats BCD dans:

ABC, DBCD 

Ce qui n'est pas résoluble. Mais la combinaison ABC avec des résultats BCD dans:

ABCD, DBC

qui peut être combiné à:

ABCDBC. 

Answer 5

Si le code Open Source est acceptable, alors vous devriez vérifier le génome points de référence dans Stanford STAMP suite benchmark: elle fait exactement ce que vous cherchez. Commençant avec un tas de chaînes ("gènes"), il cherche la chaîne la plus courte qui incorpore tous les gènes. Par exemple, si vous avez ATGC et GCAA, vous trouverez ATGCAA. Il n'y a rien dans l'algorithme qui le limite à un alphabet à 4 caractères, donc cela devrait pouvoir vous aider.