Comment puis-je détecter les sous-chaînes communes dans une liste de chaînes

Question

Étant donné un ensemble de chaînes, par exemple:

EFgreen 
EFgrey 
EntireS1 
EntireS2 
J27RedP1 
J27GreenP1 
J27RedP2 
J27GreenP2 
JournalP1Black 
JournalP1Blue 
JournalP1Green 
JournalP1Red 
JournalP2Black 
JournalP2Blue 
JournalP2Green 

Je veux être en mesure de détecter que ces trois ensembles de fichiers:

• entires [1,2]
• J27 [Rouge, vert] P [1,2]
• JournalP [1,2] [Rouge, vert, Bleu]

Existe-t-il des moyens connus d'aborder ce problème - des articles publiés que je peux lire à ce sujet?

L'approche que je considère est pour chaque chaîne de regarder toutes les autres chaînes et trouver les caractères communs et où différents caractères sont, en essayant de trouver des ensembles de chaînes qui ont le plus en commun, mais je crains que ce n'est pas très efficace et peut donner des faux positifs. Notez que ce n'est pas la même chose que 'How do I detect groups of common strings in filenames' car cela suppose qu'une chaîne aura toujours une série de chiffres qui la suit.

Answer 1

Je commence ici: http://en.wikipedia.org/wiki/Longest_common_substring_problem

Il y a des liens vers des informations supplémentaires dans les liens externes, y compris les implémentations Perl des deux algorithmes expliqué dans l'article.

Edité à ajouter:

Sur la base de la discussion, je pense encore plus longue pourrait être commune Substring au cœur de ce problème. Même dans l'exemple de Journal que vous référencez dans votre commentaire, la caractéristique de définition de cet ensemble est la sous-chaîne 'Journal'.

Je considérerais d'abord ce qui définit un ensemble comme distinct des autres ensembles. Cela vous donne votre partition pour diviser les données, et ensuite le problème est de mesurer la quantité de points communs existant dans un ensemble. Si la caractéristique de définition est une sous-chaîne commune, alors la plus longue sous-chaîne commune serait un point de départ logique.

Pour automatiser le processus de détection d'ensemble, vous aurez généralement besoin d'une mesure de similarité par paire que vous pouvez utiliser pour mesurer la «différence» entre toutes les paires possibles. Ensuite, vous avez besoin d'un algorithme pour calculer la partition qui entraîne la différence totale la plus faible. Si la mesure de différence n'est pas la plus longue sous-chaîne commune, c'est bien, mais alors vous devez déterminer ce que ce sera. Évidemment, cela doit être quelque chose de concret que vous pouvez mesurer.

Gardez également à l'esprit que les propriétés de votre mesure de différence porteront sur les algorithmes pouvant être utilisés pour créer la partition. Par exemple, supposons que diff (X, Y) donne la mesure de la différence entre X et Y. Alors il serait probablement utile si votre mesure de distance était telle que diff (A, C) < = diff (A, B) + diff (AVANT JC). Et évidemment, diff (A, C) devrait être le même que diff (C, A). En réfléchissant à cela, je commence aussi à me demander si nous pouvions concevoir la «différence» comme une distance entre deux cordes, et, avec une définition rigoureuse de la distance, pourrions-nous alors essayer une sorte de sur les chaînes d'entrée. Juste une pensée.

Answer 2

Il existe de nombreuses approches pour la similarité de chaînes. Je suggère de jeter un oeil à cette bibliothèque open-source qui implémente beaucoup de métriques comme Levenshtein distance.

http://sourceforge.net/projects/simmetrics/

Answer 3

Quelque chose comme ça pourrait fonctionner.

1. Créez un trie qui représente toutes vos chaînes.

Dans l'exemple que vous avez donné, il y aurait deux bords de la racine: "E" et "J". La branche "J" se scindait alors en "Jo" et "J2".

2. Un seul brin qui fourche, par ex. E-n-t-i-r-e-S- (fourches à 1, 2) indique un choix, de sorte que ce serait WholeS [1,2]

3. Si le toron est "trop ​​court" par rapport à la fourche, par ex. B-A- (fourches à N-A-N-A et H-A-M-A-S), nous listons deux mots ("banane, bahamas") plutôt qu'un choix ("ba [nana, hamas]"). "Trop court" pourrait être aussi simple que "si la partie après la fourche est plus longue que la partie précédente", ou pondérée par le nombre de mots qui ont un préfixe donné.

4. Si deux sous-arbres sont "suffisamment similaires", ils peuvent être fusionnés de sorte qu'au lieu d'un arbre, vous disposez maintenant d'un graphe général. Par exemple, si vous avez ABRed, ABBlue, ABGreen, CDRed, CDBlue, CDGreen, vous pouvez trouver que la sous-arborescence "AB" est la même que la sous-arborescence de "CD", donc vous les fusionner. Dans votre sortie, cela ressemblera à ceci: [branche gauche, branche droite] [sous-arbre], donc: [AB, CD] [Rouge, Bleu, Vert]. Comment faire face aux sous-arbres qui sont proches mais pas exactement les mêmes? Il n'y a probablement pas de réponse absolue, mais quelqu'un ici peut avoir une bonne idée.

Je marque cette réponse wiki communautaire. N'hésitez pas à l'étendre afin que, ensemble, nous puissions avoir une réponse raisonnable à la question.

Answer 4

Pour cet exemple particulier de chaînes pour le garder extrêmement simple, pensez à utiliser une simple séparation mot/chiffre.

Une séquence non-numérique peut apparemment commencer par une lettre majuscule (entière). Après avoir rompu toutes les chaînes en groupes de séquences, quelque chose comme

[Entire][S][1] 
[Entire][S][2] 
[J][27][Red][P][1] 
[J][27][Green][P][1] 
[J][27][Red][P][2] 
.... 
[Journal][P][1][Blue] 
[Journal][P][1][Green] 

commencer ensuite le regroupement par des groupes, vous pouvez voir assez vite que le préfixe « entier » est une commune pour un groupe et que tous les sous-groupes ont S comme groupe de tête, donc seule variable pour ceux-ci est de 1,2. Pour le cas J27, vous pouvez voir que J27 est seulement une feuille, mais qu'elle se ramifie alors au rouge et au vert.

Donc un peu de liste < Liste < liste, chaîne > > -structure (motif composite si je me souviens bien).

Answer 5

Vous devriez pouvoir y parvenir avec des arborescences de suffixes généralisées: recherchez les chemins longs dans l'arborescence de suffixes provenant de plusieurs chaînes sources.

Answer 6

import java.util.*; 
class StringProblem 
{ 
    public List<String> subString(String name) 
    { 
     List<String> list=new ArrayList<String>(); 
     for(int i=0;i<=name.length();i++) 
     { 
      for(int j=i+1;j<=name.length();j++) 
      { 
       String s=name.substring(i,j); 
       list.add(s); 
      } 
     } 
     return list; 
    } 
    public String commonString(List<String> list1,List<String> list2,List<String> list3) 
    { 
     list2.retainAll(list1); 
     list3.retainAll(list2); 

     Iterator it=list3.iterator(); 
     String s=""; 
     int length=0; 
     System.out.println(list3); // 1 1 2 3 1 2 1 
     while(it.hasNext())  
     { 
      if((s=it.next().toString()).length()>length) 
      { 
       length=s.length(); 
      } 
     } 
     return s; 
    } 
    public static void main(String args[]) 
    { 
     Scanner sc=new Scanner(System.in); 
     System.out.println("Enter the String1:"); 
     String name1=sc.nextLine(); 
     System.out.println("Enter the String2:"); 
     String name2=sc.nextLine(); 
     System.out.println("Enter the String3:"); 
     String name3=sc.nextLine(); 
     // String name1="salman"; 
     // String name2="manmohan"; 
     // String name3="rahman"; 

     StringProblem sp=new StringProblem(); 

     List<String> list1=new ArrayList<String>(); 
     list1=sp.subString(name1); 

     List<String> list2=new ArrayList<String>(); 
     list2=sp.subString(name2); 


     List<String> list3=new ArrayList<String>(); 
     list3=sp.subString(name3); 

     sp.commonString(list1,list2,list3); 
     System.out.println(" "+sp.commonString(list1,list2,list3)); 
    } 
} 

Answer 7

essayez "frak". Il crée une expression regex à partir d'un ensemble de chaînes. Peut-être qu'une modification de cela vous aidera. https://github.com/noprompt/frak

Espérons que cela aide.

Answer 8

Bonne question!Les étapes d'une solution sont les suivants:

1. tokenizing entrée
2. utilisant des jetons pour construire un data structure approprié. un DAWG est idéal, mais un Trie est plus simple et un point de départ décent.
3. post-traitement optionnel de la structure de données pour simplifier ou regroupement des sous-arbres dans des sorties séparées
4. serialization de la structure de données à une syntaxe regular expression ou similaire

Je l'ai mis en œuvre cette approche dans regroup.py. Voici un exemple:

$ cat | ./regroup.py --cluster-prefix-len=2 
EFgreen 
EFgrey 
EntireS1 
EntireS2 
J27RedP1 
J27GreenP1 
J27RedP2 
J27GreenP2 
JournalP1Black 
JournalP1Blue 
JournalP1Green 
JournalP1Red 
JournalP2Black 
JournalP2Blue 
JournalP2Green 
^D 
EFgre(en|y) 
EntireS[12] 
J27(Green|Red)P[12] 
JournalP[12](Bl(ack|ue)|(Green|Red)) 

Answer 9

Il existe de nombreuses solutions proposées qui résolvent le cas général de la recherche de sous-chaînes courantes. Cependant, le problème ici est plus spécialisé. Vous recherchez des préfixes communs, pas seulement des sous-chaînes. Cela le rend un peu plus simple. Une bonne explication pour trouver plus long préfixe commun se trouvent à http://www.geeksforgeeks.org/longest-common-prefix-set-1-word-by-word-matching/

Donc, mon projet « pythonese » pseudo-code est quelque chose comme ceci (voir le lien pour une mise en œuvre de find_lcp:

def count_groups(items): 
    sorted_list = sorted(items) 

    prefix = sorted_list[0] 
    ctr = 0 
    groups = {} 
    saved_common_prefix = "" 
    for i in range(1, sorted_list): 
    common_prefix = find_lcp(prefix, sorted_list[i]) 
    if len(common_prefix) > 0: #we are still in the same group of items 
     ctr += 1 
     saved_common_prefix = common_prefix 
     prefix = common_prefix 
    else: # we must have switched to a new group 
     groups[saved_common_prefix] = ctr 
     ctr = 0 
     saved_common_prefix = "" 
     prefix = sorted_list[i] 
    return groups