problèmes Python regex avec string assorti

Question

Désolé à l'avance pour un long post

EDIT--

modifié de la solution de Norman pour imprimer et retourner si nous trouvons une solution exacte, sinon imprimer tous les correspondances approximatives. Il ne reçoit actuellement que 83/85 correspondances pour un exemple spécifique de recherche d'etnse sur le fichier de dictionnaire fourni ci-dessous sur le troisième lien pastebin.

def doMatching(file, origPattern): 
    entireFile = file.read() 
    patterns = [] 
    startIndices = [] 

    begin = time.time() 

    # get all of the patterns associated with the given phrase 
    for pattern in generateFuzzyPatterns(origPattern): 
     patterns.append(pattern) 
     for m in re.finditer(pattern, entireFile): 
      startIndices.append((m.start(), m.end(), m.group())) 
     # if the first pattern(exact match) is valid, then just print the results and we're done 
     if len(startIndices) != 0 and startIndices[0][2] == origPattern: 
      print("\nThere is an exact match at: [{}:{}] for {}").format(*startIndices[0]) 
      return 

    print('Used {} patterns:').format(len(patterns)) 
    for i, p in enumerate(patterns, 1): 
     print('- [{}] {}').format(i, p) 

    # list for all non-overlapping starting indices 
    nonOverlapping = [] 
    # hold the last matches ending position 
    lastEnd = 0 
    # find non-overlapping matches by comparing each matches starting index to the previous matches ending index 
    # if the starting index > previous items ending index they aren't overlapping 
    for start in sorted(startIndices): 
     print(start) 
     if start[0] >= lastEnd: 
      # startIndicex[start][0] gets the ending index from the current matches tuple 
      lastEnd = start[1] 
      nonOverlapping.append(start) 

    print() 
    print('Found {} matches:').format(len(startIndices)) 
    # i is the key <starting index> assigned to the value of the indices (<ending index>, <string at those indices> 
    for start in sorted(startIndices): 
     # *startIndices[i] means to unpack the tuple associated to the key i's value to be used by format as 2 inputs 
     # for explanation, see: http://stackoverflow.com/questions/2921847/what-does-the-star-operator-mean-in-python 
     print('- [{}:{}] {}').format(*start) 

    print() 
    print('Found {} non-overlapping matches:').format(len(nonOverlapping)) 
    for ov in nonOverlapping: 
     print('- [{}:{}] {}').format(*ov) 

    end = time.time() 
    print(end-begin) 

def generateFuzzyPatterns(origPattern): 
    # Escape individual symbols. 
    origPattern = [re.escape(c) for c in origPattern] 

    # Find exact matches. 
    pattern = ''.join(origPattern) 
    yield pattern 

    # Find matches with changes. (replace) 
    for i in range(len(origPattern)): 
     t = origPattern[:] 
     # replace with a wildcard for each index 
     t[i] = '.' 
     pattern = ''.join(t) 
     yield pattern 

    # Find matches with deletions. (omitted) 
    for i in range(len(origPattern)): 
     t = origPattern[:] 
     # remove a char for each index 
     t[i] = '' 
     pattern = ''.join(t) 
     yield pattern 

    # Find matches with insertions. 
    for i in range(len(origPattern) + 1): 
     t = origPattern[:] 
     # insert a wildcard between adjacent chars for each index 
     t.insert(i, '.') 
     pattern = ''.join(t) 
     yield pattern 

    # Find two adjacent characters being swapped. 
    for i in range(len(origPattern) - 1): 
     t = origPattern[:] 
     if t[i] != t[i + 1]: 
      t[i], t[i + 1] = t[i + 1], t[i] 
      pattern = ''.join(t) 
      yield pattern 

ORIGINAL: http://pastebin.com/bAXeYZcD - la fonction réelle

http://pastebin.com/YSfD00Ju - les données à utiliser, devrait être 8 matchs pour 'articles' mais seulement obtient 6

http://pastebin.com/S9u50ig0 - données à utiliser, devrait obtenir 85 correspond à 'etnse' mais obtient seulement 77

J'ai laissé tout le code original dans la fonction parce que je ne suis pas sûr exactement ce qui cause le problème.

Vous pouvez rechercher 'Board: isFull()' sur n'importe quoi pour obtenir l'erreur indiquée ci-dessous.

exemples:

supposent que vous avez nommé la deuxième pastebin « Somefile.txt » dans un dossier nommé fichiers dans le même répertoire que le fichier .py.

file = open('./files/someFile.txt', 'r') 
doMatching(file, "ware") 

OU

file = open('./files/someFile.txt', 'r') 
doMatching(file, "Board:isFull()") 

OU

supposons que vous avez nommé la troisième pastebin 'dictionary.txt' dans un dossier fichiers nommés dans le même répertoire que le fichier .py.

file = open('./files/dictionary.txt', 'r') 
doMatching(file, "etnse") 

--edit

Les paramètres fonctionnent comme si les fonctions:

fichier

est l'emplacement d'un fichier.

origPattern est une expression.

La fonction est fondamentalement supposée être une recherche floue. Il est supposé prendre le modèle et chercher dans un fichier pour trouver des correspondances exactes ou avec un écart de 1 caractère. c'est-à-dire: 1 caractère manquant, 1 caractère supplémentaire, 1 caractère remplacé ou 1 caractère échangé avec un caractère adjacent.

Pour la plupart, cela fonctionne, mais je rencontre quelques problèmes.

D'abord, quand j'essaie d'utiliser quelque chose comme 'Board: isFull()' pour origPattern je reçois le texte suivant:

raise error, v # invalid expression 
sre_constants.error: unbalanced parenthesis 

ci-dessus est de la bibliothèque re

J'ai essayé d'utiliser re.escape() mais ça ne change rien.Deuxièmement, quand j'essaie d'autres choses comme 'Fun()', il dit qu'il a une correspondance à un index qui ne contient même pas de ça; c'est juste une ligne de '*'

Troisièmement, quand il trouve des correspondances, il ne trouve pas toujours toutes les correspondances. Par exemple, il y a un fichier qui devrait trouver 85 correspondances, mais il ne contient que 77, et un autre avec 8, mais il n'en contient que 6. Cependant, ils sont simplement alphabétiques, donc c'est probablement un problème avec la façon dont je faire des recherches ou quelque chose.

Toute aide est appréciée.

Je ne peux pas utiliser fuzzyfinder

Answer 1

J'ai trouvé des problèmes dans le code:

1. re.escape() semble pas fonctionner parce que son résultat n'est pas affecté.
   A faire origPattern = re.escape(origPattern).
2. Lorsque le motif est correctement échappé, veillez à ne pas interrompre l'échappement lors de la manipulation du motif. Exemple: re.escape('Fun()') donne la chaîne Fun\(\). Les deux sous-chaînes \( qui s'y trouvent ne doivent jamais être séparées: ne jamais supprimer, remplacer ou échanger un \ sans que le caractère échappe.
   Mauvaises manipulations: Fun(\) (retrait), Fu\n(\) (échange), Fun\.{0,2}\).
   Bonnes manipulations: Fun\) (retrait), Fu\(n\) (échange), Fun.{0,2}\).
3. Vous trouvez trop peu de résultats, car vous essayez seulement de trouver des résultats approximatifs s'il n'y a pas de résultats exacts. (Voir la ligne if indices.__len__() != 0:.) Vous devez toujours les chercher.
4. Les boucles insérant '.{0,2}' produisent un motif trop, par ex. 'ware.{0,2}' pour ware. Sauf si vous avez l'intention de le faire, ce motif trouvera wareXY qui a deux insertions. Les modèles avec .{0,2} ne fonctionnent pas comme décrit; ils permettent un changement et une insertion.
5. Je ne suis pas sûr du code impliquant difflib.Differ. Je ne comprends pas, mais je suppose qu'il ne devrait pas y avoir d'instructions break.
6. Même si vous utilisez un set pour stocker des index, des correspondances de différentes expressions régulières peuvent toujours se chevaucher.
7. Vous n'utilisez pas les limites de mots (\b) dans vos expressions régulières, mais pour un langage naturel qui aurait du sens.
8. Pas un bug, mais: Pourquoi appelez-vous les méthodes magiques explicitement?
   (Par exemple, au lieu de indices.__len__() != 0len(indices) != 0.)

Je réécris votre code afin de répondre à toutes les questions que j'ai vu:

def doMatching(file, origPattern): 
    entireFile = file.read() 
    patterns = [] 
    startIndices = {} 

    for pattern in generateFuzzyPatterns(origPattern): 
     patterns.append(pattern) 
     startIndices.update((m.start(), (m.end(), m.group())) for m in re.finditer(pattern, entireFile)) 

    print('Used {} patterns:'.format(len(patterns))) 
    for i, p in enumerate(patterns, 1): 
     print('- [{}] {}'.format(i, p)) 

    nonOverlapping = [] 
    lastEnd = 0 
    for start in sorted(startIndices): 
     if start >= lastEnd: 
      lastEnd = startIndices[start][0] 
      nonOverlapping.append(start) 

    print() 
    print('Found {} matches:'.format(len(startIndices))) 
    for i in sorted(startIndices): 
     print('- [{}:{}] {}'.format(i, *startIndices[i])) 

    print() 
    print('Found {} non-overlapping matches:'.format(len(nonOverlapping))) 
    for i in nonOverlapping: 
     print('- [{}:{}] {}'.format(i, *startIndices[i])) 


def generateFuzzyPatterns(origPattern): 
    # Escape individual symbols. 
    origPattern = [re.escape(c) for c in origPattern] 

    # Find exact matches. 
    pattern = ''.join(origPattern) 
    yield pattern 

    # Find matches with changes. 
    for i in range(len(origPattern)): 
     t = origPattern[:] 
     t[i] = '.' 
     pattern = ''.join(t) 
     yield pattern 

    # Find matches with deletions. 
    for i in range(len(origPattern)): 
     t = origPattern[:] 
     t[i] = '' 
     pattern = ''.join(t) 
     yield pattern 

    # Find matches with insertions. 
    for i in range(len(origPattern) + 1): 
     t = origPattern[:] 
     t.insert(i, '.') 
     pattern = ''.join(t) 
     yield pattern 

    # Find two adjacent characters being swapped. 
    for i in range(len(origPattern) - 1): 
     t = origPattern[:] 
     if t[i] != t[i + 1]: 
      t[i], t[i + 1] = t[i + 1], t[i] 
      pattern = ''.join(t) 
      yield pattern