espressioni regolari Fuzzy

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.espressioni regolari Fuzzy

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?

fonte

2010-02-28 Thomas Ahle

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.

fonte

2010-03-04 10:54:24

Avete considerato l'utilizzo di lexer?

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

fonte

2010-02-28 16:18:47

Penso che i lexer siano più per la tokenizzazione che per la corrispondenza. Se inizio a dividere la mia stringa, non sarò in grado di riconoscere i personaggi spostati da un token all'altro. –

Potrebbe essere necessario definire il problema come problema di lexing/parsing, piuttosto che come semplice espressione regolare. Quindi potresti usare la distanza di Levenshtein sui singoli token. – Avi

Vedo. Ma il link lessico che hai inviato cuciture è abbastanza deterministico. E se invece di 'TV Schedule for 10 Jan' ottengo' TV Schedule for Jan 10'? Questo dovrebbe avere una distanza di 2, dal momento che sono stati trasposti due personaggi. Forse il lexer potrebbe identificare sottostringhe simili a numeri o mesi, ma poi "Programma TV per Jan 10" o "Programma TV per il 10 gennaio 2010" darebbe dei problemi .. –

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.

fonte

2010-02-28 16:33:06 bmargulies

Il primo si articola in una corrispondenza approssimativa standard delle stringhe? La seconda sembra essere in ricerche sfocate in un dizionario. Questo potrebbe probabilmente essere usato pensando alla regex come a un "dizionario fictionary"? –

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.

fonte

2013-04-12 15:46:39

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

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

fonte

2014-10-26 23:23:53

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.

fonte

2016-09-18 12:36:36 Julian

risposta

Problemi correlati