Floue Expressions Régulières

Question

Dans mon travail, j'ai, avec d'excellents résultats utilisé approximative de la chaîne des algorithmes d'appariement tel que la distance de damerau–Levenshtein pour rendre mon code moins vulnérables aux fautes d'orthographe.

Maintenant, j'ai besoin de faire correspondre les chaînes contre les expressions régulières simples tels TV Schedule for \d\d (Jan|Feb|Mar|...). Cela signifie que la chaîne de caractères TV Schedule for 10 Jan doit retourner 0 en T Schedule for 10. Jan doit retourner 2.

Cela pourrait être fait en générant toutes les chaînes dans la regex (dans ce cas 100x12) et de trouver la meilleure correspondance, mais ce n'est pas de la couture pratique.

Avez-vous des idées sur la façon de le faire efficacement?

Answer 1

J'ai trouvé le TRE de la bibliothèque, de la sorcière coutures pour être en mesure de faire exactement la correspondance floue des expressions régulières. Exemple: http://hackerboss.com/approximate-regex-matching-in-python/ Il prend uniquement en charge de l'insertion, de suppression et de substitution si. Pas de transposition. Mais je suppose que ça fonctionne bien.

J'ai essayé de l'accompagnement agrep outil avec la regexp sur le fichier suivant:

TV Schedule for 10Jan
TVSchedule for Jan 10
T Schedule for 10 Jan 2010
TV Schedule for 10 March
Tv plan for March

et a obtenu

$ agrep -s -E 100 '^TV Schedule for \d\d (Jan|Feb|Mar)$' filename
1:TV Schedule for 10Jan
8:TVSchedule for Jan 10
7:T Schedule for 10 Jan 2010
3:TV Schedule for 10 March
15:Tv plan for March

Merci beaucoup pour tous vos propose.

Answer 2

Je viens d'utiliser l' regex module: 'Alternative expression régulière module, pour remplacer re.' Il fournit la familiarité de l' re mais inclut des options pour la correspondance floue, ainsi que plusieurs autres améliorations re.

Pour les binaires pour Windows, voir cette ressource.

Answer 3

Ici est une ressource sur la question que vous vous posez. C'est un peu un teaser pour une entreprise. Plus utile peut-être de ce livre. J'ai vu une mise en œuvre inspiré par le papier qui pourrait faire une recherche floue, biaisées pour les spéciaux de la langue (par exemple l'arabe vs anglais), sur un vaste ensemble de données.

En général, vous ne serez pas en mesure de faire ce que vous m'avez demandé. Vous pouvez faire une recherche regexp floue par le remplacement de caractères avec des classes d'équivalence, ou vous pouvez rechercher une base de données pour près de matchs définie par la distance de Levenshtein. En essayant de développer la (n)DFA derrière une regexp pour inclure près-correspond à la distance qui allait rapidement devenir incroyablement complexe.

Answer 4

Avez-vous songé à l'aide d'un analyseur lexical?

Je ne l'ai jamais utilisé un, donc je ne peux pas être d'un grand secours, mais il semble comme il convient!