Comment trouver des modèles similaires dans des listes / tableaux de chaînes
https://stackoverflow.com/questions/483429
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je cherche des moyens de trouver des modèles correspondants dans des listes ou des tableaux de chaînes, en particulier dans .NET, mais des algorithmes ou une logique provenant d'autres langages seraient utiles.
Disons que j'ai 3 tableaux (ou dans ce cas spécifique List (Of String))
Array1
"Do"
"Re"
"Mi"
"Fa"
"So"
"La"
"Ti"
Array2
"Mi"
"Fa"
"Jim"
"Bob"
"So"
Array3
"Jim"
"Bob"
"So"
"La"
"Ti"
Je souhaite signaler les occurrences des correspondances de
("Mi", "Fa") In Arrays (1,2)
("So") In Arrays (1,2,3)
("Jim", "Bob", "So") in Arrays (2,3)
("So", "La", "Ti") in Arrays (1, 3)
... et d'autres.
J'utilise ceci pour résoudre un problème, non pour en faire un produit commercial, mais plutôt pour le faire manuellement (il existe 110 listes d'environ 100 à 200 éléments).
Existe-t-il des algorithmes, du code existant ou des idées qui m'aideront à trouver les résultats décrits?
La solution
Comme d'autres l'ont déjà mentionné, la fonction que vous souhaitez utiliser est Intersection. Si vous utilisez .NET 3.0, envisagez d’utiliser la fonction Intersection de LINQ.
Voir l'article suivant pour plus d'informations
Pensez à utiliser LinqPAD pour expérimenter.
Autres conseils
La méthode la plus simple consiste à créer un dictionnaire, puis à parcourir en boucle chaque élément de chaque tableau. Pour cela, procédez comme suit:
Vérifiez si l’élément est dans le dictonary, le cas échéant, ajoutez la liste au tableau. Si l'élément n'est pas dans le dictionnaire, ajoutez-le et la liste.
Comme vous l'avez dit, les performances du code de non-production importent peu, donc cette approche devrait fonctionner correctement.
Voici une solution utilisant le module SuffixTree pour localiser les sous-séquences:
#!/usr/bin/env python
from SuffixTree import SubstringDict
from collections import defaultdict
from itertools import groupby
from operator import itemgetter
import sys
def main(stdout=sys.stdout):
"""
>>> import StringIO
>>> s = StringIO.StringIO()
>>> main(stdout=s)
>>> print s.getvalue()
[['Mi', 'Fa']] In Arrays (1, 2)
[['So', 'La', 'Ti']] In Arrays (1, 3)
[['Jim', 'Bob', 'So']] In Arrays (2, 3)
[['So']] In Arrays (1, 2, 3)
<BLANKLINE>
"""
# array of arrays of strings
arr = [
["Do", "Re", "Mi", "Fa", "So", "La", "Ti",],
["Mi", "Fa", "Jim", "Bob", "So",],
["Jim", "Bob", "So", "La", "Ti",],
]
#### # 28 seconds (27 seconds without lesser substrs inspection (see below))
#### N, M = 100, 100
#### import random
#### arr = [[random.randrange(100) for _ in range(M)] for _ in range(N)]
# convert to ASCII alphabet (for SubstringDict)
letter2item = {}
item2letter = {}
c = 1
for item in (i for a in arr for i in a):
if item not in item2letter:
c += 1
if c == 128:
raise ValueError("too many unique items; "
"use a less restrictive alphabet for SuffixTree")
letter = chr(c)
letter2item[letter] = item
item2letter[item] = letter
arr_ascii = [''.join(item2letter[item] for item in a) for a in arr]
# populate substring dict (based on SuffixTree)
substring_dict = SubstringDict()
for i, s in enumerate(arr_ascii):
substring_dict[s] = i+1
# enumerate all substrings, save those that occur more than once
substr2indices = {}
indices2substr = defaultdict(list)
for str_ in arr_ascii:
for start in range(len(str_)):
for size in reversed(range(1, len(str_) - start + 1)):
substr = str_[start:start + size]
if substr not in substr2indices:
indices = substring_dict[substr] # O(n) SuffixTree
if len(indices) > 1:
substr2indices[substr] = indices
indices2substr[tuple(indices)].append(substr)
#### # inspect all lesser substrs
#### # it could diminish size of indices2substr[ind] list
#### # but it has no effect for input 100x100x100 (see above)
#### for i in reversed(range(len(substr))):
#### s = substr[:i]
#### if s in substr2indices: continue
#### ind = substring_dict[s]
#### if len(ind) > len(indices):
#### substr2indices[s] = ind
#### indices2substr[tuple(ind)].append(s)
#### indices = ind
#### else:
#### assert set(ind) == set(indices), (ind, indices)
#### substr2indices[s] = None
#### break # all sizes inspected, move to next `start`
for indices, substrs in indices2substr.iteritems():
# remove substrs that are substrs of other substrs
substrs = sorted(substrs, key=len) # sort by size
substrs = [p for i, p in enumerate(substrs)
if not any(p in q for q in substrs[i+1:])]
# convert letters to items and print
items = [map(letter2item.get, substr) for substr in substrs]
print >>stdout, "%s In Arrays %s" % (items, indices)
if __name__=="__main__":
# test
import doctest; doctest.testmod()
# measure performance
import timeit
t = timeit.Timer(stmt='main(stdout=s)',
setup='from __main__ import main; from cStringIO import StringIO as S; s = S()')
N = 1000
milliseconds = min(t.repeat(repeat=3, number=N))
print("%.3g milliseconds" % (1e3*milliseconds/N))
Il faut environ 30 secondes pour traiter 100 listes de 100 éléments chacune. SubstringDict dans le code ci-dessus peut être émulé par grep -F -f.
Ancienne solution:
En Python (enregistrez-le dans le fichier 'group_patterns.py'):
#!/usr/bin/env python
from collections import defaultdict
from itertools import groupby
def issubseq(p, q):
"""Return whether `p` is a subsequence of `q`."""
return any(p == q[i:i + len(p)] for i in range(len(q) - len(p) + 1))
arr = (("Do", "Re", "Mi", "Fa", "So", "La", "Ti",),
("Mi", "Fa", "Jim", "Bob", "So",),
("Jim", "Bob", "So", "La", "Ti",))
# store all patterns that occure at least twice
d = defaultdict(list) # a map: pattern -> indexes of arrays it's within
for i, a in enumerate(arr[:-1]):
for j, q in enumerate(arr[i+1:]):
for k in range(len(a)):
for size in range(1, len(a)+1-k):
p = a[k:k + size] # a pattern
if issubseq(p, q): # `p` occures at least twice
d[p] += [i+1, i+2+j]
# group patterns by arrays they are within
inarrays = lambda pair: sorted(set(pair[1]))
for key, group in groupby(sorted(d.iteritems(), key=inarrays), key=inarrays):
patterns = sorted((pair[0] for pair in group), key=len) # sort by size
# remove patterns that are subsequences of other patterns
patterns = [p for i, p in enumerate(patterns)
if not any(issubseq(p, q) for q in patterns[i+1:])]
print "%s In Arrays %s" % (patterns, key)
La commande suivante:
$ python group_patterns.py
imprime:
[('Mi', 'Fa')] In Arrays [1, 2]
[('So',)] In Arrays [1, 2, 3]
[('So', 'La', 'Ti')] In Arrays [1, 3]
[('Jim', 'Bob', 'So')] In Arrays [2, 3]
La solution est terriblement inefficace.
J'ai piraté le programme ci-dessous dans environ 10 minutes de Perl. Ce n'est pas parfait, il utilise une variable globale et affiche simplement le nombre de tous les éléments vus par le programme dans chaque liste, mais c'est une bonne approximation de ce que vous voulez faire, très facile à coder.
Voulez-vous réellement toutes les combinaisons de tous les sous-ensembles d'éléments communs à chaque tableau? Vous pouvez énumérer tous les éléments de manière plus intelligente si vous le souhaitez, mais si vous ne souhaitez que tous les éléments existant au moins une fois dans chaque tableau, vous pouvez utiliser la commande Unix & «Grep -v 0 &»; sur la sortie ci-dessous et cela vous montrerait l'intersection de tous les éléments communs à tous les tableaux. Votre question manque un peu de détail, je ne peux donc pas parfaitement mettre en œuvre quelque chose qui résout votre problème.
Si vous effectuez plus d'analyse de données que de programmation, le script peut s'avérer très utile pour poser des questions à partir de données textuelles comme celle-ci. Si vous ne savez pas comment coder dans un langage de script comme celui-ci, je passerais un mois ou deux à lire comment coder en Perl, Python ou Ruby. Ils peuvent être merveilleux pour des piratages ponctuels tels que celui-ci, surtout dans les cas où vous ne savez pas vraiment ce que vous voulez. Le coût en temps et en cerveaux de la rédaction d'un programme comme celui-ci est très bas, vous permettant ainsi (si vous êtes rapide) d'écrire et de le réécrire plusieurs fois tout en explorant la définition de votre question.
#!/usr/bin/perl -w
use strict;
my @Array1 = ( "Do", "Re", "Mi", "Fa", "So", "La", "Ti");
my @Array2 = ( "Mi", "Fa", "Jim", "Bob", "So" );
my @Array3 = ( "Jim", "Bob", "So", "La", "Ti" );
my %counts;
sub count_array {
my $array = shift;
my $name = shift;
foreach my $e (@$array) {
$counts{$e}{$name}++;
}
}
count_array( \@Array1, "Array1" );
count_array( \@Array2, "Array2" );
count_array( \@Array3, "Array3" );
my @names = qw/ Array1 Array2 Array3 /;
print join ' ', ('element',@names);
print "\n";
my @unique_names = keys %counts;
foreach my $unique_name (@unique_names) {
my @counts = map {
if ( exists $counts{$unique_name}{$_} ) {
$counts{$unique_name}{$_};
} else {
0;
}
}
@names;
print join ' ', ($unique_name,@counts);
print "\n";
}
La sortie du programme est:
element Array1 Array2 Array3
Ti 1 0 1
La 1 0 1
So 1 1 1
Mi 1 1 0
Fa 1 1 0
Do 1 0 0
Bob 0 1 1
Jim 0 1 1
Re 1 0 0
On dirait que vous souhaitez utiliser une fonction d'intersection sur des ensembles de données. Intersection sélectionne les éléments communs aux deux (ou plus) ensembles.
Le problème avec ce point de vue est que les ensembles ne peuvent pas contenir plus d’un élément, c’est-à-dire pas plus d’un Jim par ensemble, il ne peut pas reconnaître plusieurs éléments d’une ligne comptant pour un motif. Vous pouvez toutefois modifier une fonction de comparaison. regarder plus loin pour voir cela.
Il pourrait y avoir des fonctions comme intersecter qui fonctionne sur les sacs (ce qui revient à ressembler à des ensembles, mais tolère des éléments identiques).
Ces fonctions doivent être standard dans la plupart des langues ou assez faciles à écrire vous-même.
Je suis sûr qu'il y a BEAUCOUP une manière beaucoup plus élégante, mais ...
Etant donné qu'il ne s'agit pas d'un code de production, pourquoi ne pas simplement le pirater et convertir chaque tableau en une chaîne délimitée, puis rechercher dans chaque chaîne le motif de votre choix? c'est-à-dire
private void button1_Click(object sender, EventArgs e)
{
string[] array1 = { "do", "re", "mi", "fa", "so" };
string[] array2 = { "mi", "fa", "jim", "bob", "so" };
string[] pattern1 = { "mi", "fa" };
MessageBox.Show(FindPatternInArray(array1, pattern1).ToString());
MessageBox.Show(FindPatternInArray(array2, pattern1).ToString());
}
private bool FindPatternInArray(string[] AArray, string[] APattern)
{
return string.Join("~", AArray).IndexOf(string.Join("~", APattern)) >= 0;
}
Commencez par compter chaque élément. Vous créez une liste temporaire: & Quot; Do & Quot; = 1, & Quot; Mi & Quot; = 2, & Quot; So & Quot; = 3, etc. vous pouvez supprimer de la liste temporaire tous ceux qui correspondent = 1 (ex: & "; Faites &";). La liste temporaire contient la liste des éléments non uniques (enregistrez-la quelque part).
Maintenant, vous essayez de créer des listes de deux à partir de un dans la liste temporaire et d'un suivi dans les listes d'origine. " So " + " La " = 2, & Quot; Bob & Quot; + " So " = 2, etc. Supprimez ceux avec = 1. Vous avez les listes de couple qui apparaissent au moins deux fois (enregistrez-les quelque part).
Maintenant, essayez de créer des listes de 3 éléments en prenant quelques-uns de la liste temporaire et les éléments suivants dans les listes originales. (& "Mi &"; & "Fa &";) + & "So &"; = 1, (& "; Mi &"; & "Fa &";) + & "Jim &"; = 1, (& "So &"; & "La &";) + & "Ti &"; = 2 Supprimez ceux avec = 1. Vous avez les listes de 3 éléments qui apparaissent au moins deux fois (enregistrez-le).
Et vous continuez ainsi jusqu'à ce que la liste temporaire soit vide.
À la fin, vous prenez toutes les listes enregistrées et vous les fusionnez.
Cet algorithme n’est pas optimal (je pense que nous pouvons faire mieux avec des structures de données appropriées), mais il est facile à mettre en œuvre:)
Supposons qu'un mot de passe se compose d'une chaîne de neuf caractères de l'alphabet anglais (26 caractères). Si chaque mot de passe possible pouvait être testé en une milliseconde, combien de temps faudrait-il pour tester tous les mots de passe possibles?
