espressioni regolari Fuzzy

Question

Nel mio lavoro ho con grandi risultati utilizzati algoritmi approssimati corrispondenza stringa, come Damerau-Levenshtein distanza per fare il mio codice meno vulnerabili a errori di ortografia.

ora ho bisogno di abbinare stringhe contro semplici espressioni regolari tali TV Schedule for \d\d (Jan|Feb|Mar|...). Ciò significa che la stringa TV Schedule for 10 Jan deve restituire 0 mentre T Schedule for 10. Jan dovrebbe restituire 2.

Ciò potrebbe essere fatto mediante la generazione di tutte le stringhe nella regex (in questo caso 100x12) e trovare la migliore corrispondenza, ma questo non cucitura pratico.

Avete qualche idea su come farlo in modo efficace?

Answer 1

ho trovato il TRE library, cuciture streghe di essere in grado di fare esattamente corrispondenza sfocata di espressioni regolari. Esempio: http://hackerboss.com/approximate-regex-matching-in-python/ Supporta solo l'inserimento, la cancellazione e la sostituzione. Nessuna trasposizione Ma immagino che funzioni bene.

ho provato lo strumento agrep accompagna con l'espressione regolare sul seguente file:

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

e ottenuto

$ 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 

Grazie mille per tutto il vostro propone.

Answer 2

Avete considerato l'utilizzo di lexer?

non ho mai effettivamente utilizzato uno, quindi non posso essere di grande aiuto, ma suona come si adatta!

Answer 3

Here è una risorsa sulla questione si sta chiedendo. È un po 'un teaser per un'azienda. Più utile potrebbe essere this paper. Ho visto un'implementazione ispirata al documento che potrebbe eseguire una ricerca fuzzy, distorta per un linguaggio speciale (ad esempio arabo o inglese) su un set di dati di grandi dimensioni.

In generale, non sarai in grado di fare ciò che hai chiesto. È possibile rendere sfocata la ricerca di espressioni regolari sostituendo i caratteri con classi di equivalenza, oppure è possibile cercare un database per le partite vicine definite dalla distanza di Levenshtein. Cercando di espandere il (n) DFA dietro una espressione regolare per includere le corrispondenze ravvicinate in base alla distanza diventerebbe rapidamente incredibilmente complesso.

Answer 4

mi basta usare il regex module: 'modulo di espressione regolare alternativa, per sostituire re.' Fornisce la familiarità di re ma include opzioni per la corrispondenza fuzzy, oltre a numerosi altri miglioramenti su re.

Per i file binari di Windows, vedere this resource.

Answer 5

Vedere anche: Python regex (newer version, Oct '14 (cercare "fuzzy" all'interno del documento).

Se non sei un ragazzo Python (né io sono), il tuo codice è could compile in C (exe/dll). Allora saresti in grado di usare la tua DLL anche dal buon vecchio vb6 (e simili).

Altre biblioteche tra cui scegliere:

• TRE/agrep ('classico, buono, vecchio e veloce) (cercare 'agrep performace'), ma è necessario scrivere regex compatibile con POSIX (ricerca per 'espressioni regolari info posix') Ovviamente, tutte le librerie/esempi che usano TRE hanno questa limitazione (cercare 'hackerboss approssimata regex matching in python'). Per enormi quantità di dati: cerca "Un'implementazione CUDA rapida dell'algoritmo agrep".
• Frej (Java) - alcuni (più) limitazione (per esempio, senza guardare avanti/guardare dietro)
• fuzzy wuzzy (Python-based) - la pena di guardare, non testato ...

ricerca anche per:

• 'Comparison_of_regular_expression_engines'
• 'strumenti' Regular-Expressions.info
01.235.

(dispiace di non essere in grado di inviare i collegamenti reali)

Answer 6

ho iniziato a implementare uno strumento Java chiamato Prex per approssimativa corrispondenza dell'espressione regolare. Lo strumento determina quanto una stringa s da corrispondenza un'espressione regolare r, cioè come inserzioni, delezioni e sostituzioni in s sono almeno richiesti (costo minimo) tale che la stringa risultante s' è accettabile da r. Se sei interessato, puoi controllare il codice da https://github.com/julianthome/prex. Sarei molto felice di ricevere un feedback. Nota che l'approccio è ancora un po 'lento, ma al momento sto incorporando alcune euristiche per migliorare le sue prestazioni.