J'écris un algorithme de correspondance de modèle de chaîne que je prévois d'implémenter avec des expressions régulières. Je veux que l'expression rationnelle puisse correspondre à n'importe quelle chaîne de l'ensemble de puissance d'une liste de caractères donnée.
Je m'attends à ce que l'expression régulière corresponde de la manière suivante:
Disons que nous avons une liste
s = ['a', 'c', 't', 'a'] .
Certaines chaînes qui correspondent seraient:
S → A | T | C A → aT | aC | a | aa | ɛ T → tA | tC | t | ɛ C → cA | cT | c | ɛ
De même, certaines chaînes qui ne correspondraient pas seraient:
aaa, tacca, iii, abcd, catk, ab
3 Réponses :
Une approche ici serait de trier à la fois la liste des caractères et la sous-chaîne entrante. Ensuite, construisez un modèle de regex dans l'ordre composé des lettres individuelles qui doivent correspondre.
aact a.*t
Pour examiner de plus près cette solution, voici la liste des caractères sous forme de chaîne, après tri , suivi du modèle d'expression régulière utilisé:
s = ['a','c','t','a']
s.sort()
str = ''.join(s)
substring = "at"
substring = '.*'.join(sorted(substring))
print(substring)
if re.match(substring, str):
print("yes")
a.*t
yes
Parce que la chaîne à comparer est maintenant triée et que les caractères de l'expression régulière sont dans l'ordre, nous pouvons simplement connecter les lettres par .*.
Je résoudrais cela sans regex. C'est facile à faire avec une boucle de remplacement:
from itertools import groupby
def get_powerset_tester(characters):
char_groups = [(c, sum(1 for _ in g)) for c, g in groupby(sorted(characters))]
def tester(target):
for c, num in char_groups:
target = target.replace(c, '', num)
return target == ''
return tester
tester = get_powerset_tester('acta')
for t in test_strings:
if tester(t):
print('match: ' + t)
else:
print('no match: ' + t)
imprime:
print(is_in_powerset('acta', 'taa'))
En tant que fonction:
def is_in_powerset(characters, target):
for c in characters:
target = target.replace(c, '', 1)
return target == ''
Bien sûr, cela fonctionnera également avec les chaînes directement:
match: cat match: act match: tac match: at match: aa match: t match: acta match: taca match: a no match: aaa no match: tacca no match: iii no match: abcd no match: catk no match: ab
Une version optimisée qui minimise le nombre de .replace ( ) appels:
s = ['a','c','t','a']
test_strings = ['cat', 'act', 'tac', 'at', 'aa', 't', 'acta', 'taca', 'a',
'aaa', 'tacca', 'iii', 'abcd', 'catk', 'ab']
for t in test_strings:
temp = t
for c in s:
temp = temp.replace(c, '', 1)
if temp == '':
print('match: ' + t)
else:
print('no match: ' + t)
Je l'exécute avec des «caractères» généralement 30 caractères ou plus et «cible» comme un ensemble d'environ 100 000 entrées, donc je ne sais pas si c'est optimal en termes de temps. Je vais essayer de voir si je peux le modifier ou l'éteindre de quelque manière que ce soit. Merci pour cette réponse simple mais puissante!
Trier les caractères en groupes des mêmes caractères: ['a', 'c', 't', 'a', 'c'] => [ 'aa', 'cc', 't'] . Ensuite, parcourez ces groupes et faites target.replace (grp [0], '', len (grp)) .
Cela étant dit, les opérations de base sur les chaînes sont presque garanties de surpasser une solution basée sur les expressions régulières.
@Swopnil itertools peut faire le regroupement facilement, voir la réponse modifiée .
Il semble que si vous recherchez l'inverse, ce problème devient très simple.
Toute entrée qui contient des caractères autres que a , c ou t n'est pas une correspondance.
Ensuite, sauf pour aa nous ne devrions jamais voir le même caractère répété. Cependant aa ne peut être qu'à la fin d'une chaîne.
Pour résoudre le aa , nous pouvons remplacer n'importe quel aa à la fin de la piqûre avec un seul a , car ils sont tous les deux grammaticalement identiques.
Nous pouvons alors rechercher simplement aa , cc et tt et échouent sur toutes les correspondances.
test_strings = {
'cat' => true,
'act' => true,
'tac' => true,
'at' => true,
'aa' => true,
't' => true,
'acta' => true,
'taca' => true,
'a' => true,
'aaa' => false,
'ataa' => true,
'aataa' => false,
'tacca' => false,
'iii' => false,
'abcd' => false,
'catk' => false,
'ab' => false,
'catcat' => true,
'cat' * 40000 => true,
'actact' => true,
}
test_strings.each do |t, v|
temp = t.dup
if !temp.match(/^[atc]*$/)
puts('No match: ' + t + ' ' + temp)
next;
end
temp.sub!(/aa$/, 'A');
if temp.match(/aA|aa|tt|cc/)
puts('no match: ' + t[0..80])
puts "Wrong" if v
else
puts('match: ' + t[0..80])
puts "Wrong" unless v
end
end
Dans le code ci-dessus, je remplace aa avec A , mais utiliser a fonctionnerait également.
Ou en Ruby
import re
test_strings = {
'cat' : True,
'act' : True,
'tac' : True,
'at' : True,
'aa' : True,
't' : True,
'acta' : True,
'taca' : True,
'a' : True,
'aaa' : False,
'ataa' : True,
'aataa' : False,
'tacca' : False,
'iii' : False,
'abcd' : False,
'catk' : False,
'ab' : False,
'catcat' : True,
'cat' * 40000 : True,
'actact' : True,
}
for t, v in test_strings.items():
if not re.search("^[atc]*$", t):
continue;
temp = re.sub("aa$", "A", t)
if re.search("^aa|aA|cc|tt", temp):
print('no match(%r): %s' % (v, t))
else:
print('match(%r): %s' % (v, t))
Ce CFG n'est pas correct. Par exemple, il correspond à
ac *. (Puisque l'ensemble est fini, il y a certainement un CFG et même une expression régulière. Mais sans récursion / étoile de Kleene.)