Comment puis-je détecter les sous-chaînes communes dans une liste de chaînes
https://stackoverflow.com/questions/1410822
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
É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 pouvoir détecter qu'il s'agit de trois ensembles de fichiers :
- EntierS[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 j'envisage consiste à examiner pour chaque chaîne toutes les autres chaînes et à trouver les caractères communs et les caractères différents, en essayant de trouver des ensembles de chaînes qui ont le plus en commun, mais je crains que cela ne soit pas très efficace et puisse donner faux positifs.
Notez que ce n’est pas la même chose que "Comment détecter des groupes de chaînes communes dans les noms de fichiers" car cela suppose qu'une chaîne sera toujours suivie d'une série de chiffres.
La solution
Je commencerais ici: http://en.wikipedia.org/wiki/Longest_common_substring_problem
Il existe des liens vers des informations supplémentaires dans les liens externes, y compris les implémentations Perl des deux algorithmes expliqués dans l'article.
Modifié pour ajouter:
Sur la base de la discussion, je pense toujours que la plus longue sous-chaîne commune pourrait être au cœur de ce problème. Même dans l'exemple de journal référencé dans votre commentaire, la sous-chaîne "Journal" est la caractéristique qui le définit.
Je voudrais d’abord examiner ce qui définit un ensemble distinct des autres. Cela vous donne votre partition pour diviser les données, et ensuite le problème est de mesurer combien de points communs existent dans un ensemble. Si la caractéristique qui définit est une sous-chaîne commune, la sous-chaîne la plus longue commune sera un point de départ logique.
Pour automatiser le processus de détection des ensembles, vous aurez généralement besoin d’une mesure par paires de points communs 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 donne 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 très bien, mais vous devez alors déterminer ce qu'elle sera. De toute évidence, il faut que vous puissiez mesurer quelque chose de concret.
N'oubliez pas non plus que les propriétés de votre mesure de différence auront une incidence 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. Ensuite, il serait probablement utile que votre mesure de distance soit telle que diff (A, C) & Lt; = diff (A, B) + diff (B, C). Et évidemment, diff (A, C) devrait être identique à diff (C, A).
En réfléchissant à cela, je commence également à me demander si nous pourrions concevoir la "différence" comme une distance entre deux cordes quelconques et, avec une définition rigoureuse de la distance, pourrions-nous alors tenter une sorte de analyse de cluster sur les chaînes d'entrée. Juste une pensée.
Autres conseils
Excellente question! Les étapes pour une solution sont les suivantes:
- tokenizing entrée
- utiliser des jetons pour créer une structure de données appropriée. un DAWG est idéal, mais un Trie est plus simple et constitue un bon point de départ.
- post-traitement facultatif de la structure de données pour simplifier ou regrouper des sous-arbres en sorties séparées
- la sérialisation de la structure de données en expression régulière ou syntaxe similaire
J'ai implémenté cette approche dans regrouper.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))
Quelque chose comme ça pourrait fonctionner.
- Créez un essai qui représente toutes vos chaînes.
Dans l'exemple que vous avez donné, il y aurait deux arêtes à partir de la racine :"E" et "J".La branche « J » se diviserait alors en « Jo » et « J2 ».
Un seul brin qui se fourche, par ex.E-n-t-i-r-e-S-(fourche à 1, 2) indique un choix, ce serait donc WholeS[1,2]
Si le brin est "trop court" par rapport à la fourche, par ex.B-A- (branches de 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" peut être aussi simple que "si la partie après la fourchette est plus longue que la partie avant", ou peut-être pondéré par le nombre de mots ayant un préfixe donné.
Si deux sous-arbres sont "suffisamment similaires", ils peuvent alors être fusionnés de sorte qu'au lieu d'un arbre, vous ayez maintenant un graphique général.Par exemple, si vous avez ABRed, ABBlue, ABGreen, CDRed, CDBlue, CDGreen, vous constaterez peut-être que le sous-arbre dont la racine est « AB » est le même que le sous-arbre dont la racine est « CD », vous les fusionnerez donc.Dans votre sortie, cela ressemblera à ceci :[branche gauche, branche droite][sous-arbre], donc :[AB,CD][Rouge,Bleu,Vert].Comment gérer des sous-arbres proches mais pas exactement identiques ?Il n'y a probablement pas de réponse absolue, mais quelqu'un ici aura peut-être une bonne idée.
Je marque cette réponse wiki communautaire.N'hésitez pas à le prolonger afin que nous puissions ensemble avoir une réponse raisonnable à la question.
Il existe de nombreuses approches de la similarité des chaînes. Je suggérerais de jeter un coup d'œil à cette bibliothèque open-source qui implémente de nombreuses métriques telles que la distance de Levenshtein.
Vous devriez pouvoir y parvenir avec des arborescences de suffixes généralisées: recherchez dans l’arborescence des suffixes de longs chemins provenant de plusieurs chaînes sources.
essayez & "; frak &"; . Il crée une expression rationnelle à partir d'un ensemble de chaînes. Peut-être que quelques modifications vous aideront. https://github.com/noprompt/frak
J'espère que ça aide.
Plusieurs solutions sont proposées pour résoudre le cas général de la recherche de sous-chaînes communes. 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 le plus long préfixe commun peut être trouvée à http://www.geeksforgeeks.org / longest-common-prefix-set-1 correspondance mot par mot /
Donc, mon " pythonese " proposé; Le pseudo-code est quelque chose comme ça (voir le lien pour une implémentation 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
Pour que cet exemple particulier de chaînes reste extrêmement simple, envisagez d'utiliser une simple séparation mot / chiffre.
Une séquence sans chiffres peut apparemment commencer par une lettre majuscule (entière). Après avoir brisé 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]
Ensuite, commencez à grouper par groupes, vous pourrez bientôt voir ce préfixe & "Entier &"; est commun à un groupe et que tous les sous-groupes ont S comme groupe de tête, ainsi seule la variable pour ceux-ci est 1,2. Dans le cas J27, vous pouvez voir que J27 n’est que feuille, mais qu’il se ramifie ensuite en rouge et vert.
Donc, certains membres de la liste < Pair < list, chaîne > > -structure (motif composite si je me souviens bien).
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));
}
}
