Approssimativo stringa di algoritmi per il matching

Question

Qui al lavoro, abbiamo spesso bisogno di trovare una stringa dalla lista di stringhe che è la corrispondenza più vicina a qualche altra stringa di input.Attualmente, stiamo usando Needleman-Wunsch algoritmo.L'algoritmo ritorna spesso un sacco di falsi positivi (se abbiamo impostato il minimo punteggio troppo basso), a volte non trova una corrispondenza quando dovrebbe (quando il minimo del punteggio è troppo alto) e, il più delle volte, abbiamo bisogno di controllare i risultati con le mani.Abbiamo pensato di provare altre alternative.

Avete esperienze con gli algoritmi?Sapete come gli algoritmi di confrontare l'uno all'altro?

Mi piacerebbe davvero apprezzare qualche consiglio.

PS:Siamo codifica in C#, ma non si deve preoccupare - mi sto chiedendo su algoritmi in generale.

---

Oh, mi dispiace, ho dimenticato di dire che.

No, non stiamo utilizzando, per la partita di dati duplicati.Abbiamo una lista di stringhe che stiamo cercando, che noi chiamiamo di ricerca-list.E poi abbiamo bisogno di elaborare testi da varie fonti (come i feed RSS, siti web, forum, etc.) - estrarre parti di questi testi (ci sono tutta una serie di regole, ma è irrilevante) e abbiamo bisogno di corrispondere a quelli contro la ricerca di-list.Se la stringa corrisponde a una delle stringhe di ricerca-elenco - abbiamo bisogno di fare qualche ulteriore elaborazione della cosa (che è anche irrilevante).

Non siamo in grado di eseguire il normale confronto, perché le stringhe estratte da fonti esterne, la maggior parte delle volte, alcune parole in più etc.

Comunque, non è per il rilevamento dei duplicati.

Answer 1

OK, Needleman-Wunsch(NW) è un classico end-to-end ("globale") allineatore dalla bioinformatica letteratura.È stato molto tempo fa come "align" e "align0" in FASTA pacchetto.La differenza era che la "0" versione non era come parziale evitare di fine gapping, che spesso ha permesso favorendo interni di alta qualità partite più facile.Smith-Waterman, ho il sospetto che sei consapevole, è un locale allineatore ed è la base di ESPLOSIONE.FASTA aveva un proprio locale allineatore così che era un po ' diverso.Tutti questi sono essenzialmente i metodi euristici per la stima della distanza di Levenshtein rilevanti per un punteggio metrica per le singole coppie di caratteri (in bioinformatica, spesso Dayhoff/"PAM", Henikoff&Henikoff, o altre matrici e di solito sostituito con qualcosa di più semplice e più ragionevolmente riflettente di sostituzione linguistica parola morfologia quando applicato alla lingua naturale).

Cerchiamo di non essere prezioso etichette:Distanza di Levenshtein, a cui si fa riferimento, in pratica, almeno, è fondamentalmente la distanza di modifiche e si dispone di una stima, perché non è possibile calcolare in genere, ed è molto costoso per calcolare esattamente anche interessanti casi particolari:l'acqua diventa profonda veloce, e così abbiamo metodi euristici di lungo e di buona fama.

Ora, come al tuo problema:diversi anni fa, ho dovuto controllare la precisione di brevi frammenti di DNA legge contro la sequenza di riferimento noto per essere corretto e mi si avvicinò con quello che ho chiamato "ancorato allineamenti".

L'idea è di prendere il vostro riferimento, set di corde e "digerire" trovando tutte le sedi in cui un dato N-carattere della sottostringa si verifica.Scegliere N in modo che la tabella si genera non è troppo grande, ma anche in modo che le sottostringhe di lunghezza N non sono troppo comuni.Per le piccole alfabeti come le basi del DNA, è possibile venire con un hash perfetta su stringhe di N caratteri e fare un tavolo e catena partite in una lista collegata da ogni bin.Le voci dell'elenco deve identificare la sequenza e la posizione di partenza della sottostringa che le mappe per il cestino in cui elenco si verificano.Queste sono le "ancore" nella lista di stringhe per essere ricercati in cui un NW di allineamento possono essere utili.

Durante l'elaborazione di una stringa di query, si prende il N caratteri a partire compensati K nella stringa di query, hash loro, guardate le loro bin, e se la lista di bin non è vuota, allora si passa attraverso tutto l'elenco di record ed eseguire allineamenti tra la stringa di query e la stringa di ricerca di riferimento nel record.Quando fa queste allineamenti, si riga la stringa di query e la stringa di ricerca a il punto di ancoraggio e di estrarre una sottostringa della stringa di ricerca, che è la stessa lunghezza della stringa di query e che contiene ancora lo stesso offset, K.

Se si sceglie un sufficiente ancoraggio lunghezza N, e una serie ragionevole di valori di offset K (che possono essere distribuiti attraverso la stringa di query o essere limitato a basso offset) si dovrebbe ottenere un sottoinsieme di possibili allineamenti e spesso ottenere più chiara vincitori.In genere si desidera utilizzare il meno fine-biased align0-come NW allineatore.

Questo metodo cerca di aumentare NW e un po ' per limitare l'ingresso e questo è un guadagno in termini di prestazioni, perché si fa meno allineamenti e sono più spesso tra sequenze simili.Un'altra buona cosa da fare con il vostro NW allineatore è quello di permettere di rinunciare dopo una certa quantità o la durata del gapping si verifica per tagliare i costi, soprattutto se sai di non andare a vedere o di essere interessati in mediocre qualità partite.

Infine, questo metodo è stato utilizzato su un sistema di piccole alfabeti, con K riservata ai primi 100 posizioni nella stringa di query e con le stringhe di ricerca, molto più grande della query (il DNA legge sono stati di circa 1000 basi e le stringhe di ricerca sono stati dell'ordine di 10000, quindi stavo cercando approssimativa sottostringa partite giustificato da una stima della distanza di modifiche in particolare).L'adeguamento della metodologia di linguaggio naturale richiederà un po ' attenta riflessione:si perde sull'alfabeto dimensioni, ma si guadagna se la query stringhe e le stringhe di ricerca sono di lunghezza simile.

In ogni modo, consentire a più di ancoraggio da diversi estremità della stringa di query per essere utilizzato contemporaneamente potrebbe essere utile per una maggiore filtraggio dei dati alimentati a NW.Se si esegue questa operazione, essere pronti a trasmettergli la sovrapposizione di stringhe contenenti ciascuno una delle due ancore per l'allineatore e quindi conciliare gli allineamenti...o, eventualmente, di modificare ulteriormente NW sottolineare talmente semplice mantenere aggiornati i tuoi ancore in gran parte intatta durante un allineamento utilizzando pena di modifica durante l'algoritmo di esecuzione.

Spero che questo sia utile o almeno interessante.

Answer 2

Relative al Levenstein distanza:si potrebbe desiderare di normalizzare dividendo il risultato con la lunghezza della stringa più lunga, in modo che si ottiene sempre un numero compreso tra 0 e 1, e in modo che è possibile confrontare la distanza di coppia di stringhe in modo significativo (l'espressione L(A, B) > L(A, C) - per esempio - non ha senso a meno che non si normalizza la distanza).

Answer 3

Algoritmi alternativi per guardare sono agrep (Wikipedia voce agrep), FASTA e BLAST biologico sequenza di algoritmi per il matching.Questi sono casi particolari di approssimativo stringa corrispondente, anche in Stony Brook algoritmo repositry.Se è possibile specificare i modi in cui le stringhe differiscono l'uno dall'altro, probabilmente si potrebbe concentrarsi su un su misura algoritmo.Per esempio, aspell utilizza qualche variante di "soundslike" (soundex metaphone) distanza in combinazione con una "tastiera" a distanza di ospitare male sillabari e male typers simili.

Answer 4

Stiamo usando la Distanza di Levenshtein metodo per controllare i duplicati clienti nel nostro database.Funziona abbastanza bene.

Answer 5

Utilizzare FM Indice con Backtracking, simile a quello in Papillon fuzzy allineatore

Answer 6

Al fine di ridurre al minimo disallineamenti dovuti a lievi variazioni o errori di ortografia, ho usato il Metaphone algoritmo, quindi distanza di Levenshtein (scala da 0 a 100 percentuale match) sul Metaphone codifiche per una misura di vicinanza.Che sembra aver funzionato abbastanza bene.

Answer 7

Per espandere su Cd-la risposta dell'Uomo, sembra che tu stia affrontando una normalizzazione problema.Non è evidente come gestire i punteggi tra gli allineamenti con diverse lunghezze.

Dato che si sono interessati, si possono ottenere valori di p per il vostro allineamento.Se si utilizza Needleman-Wunsch, è possibile ottenere questi valori di p utilizzando Karlin-Altschul statistiche http://www.ncbi.nlm.nih.gov/BLAST/tutorial/Altschul-1.html

BLAST sarà in grado di allineamento locale e di valutare il loro utilizzo di queste statistiche.Se siete preoccupati per la velocità, questo sarebbe un ottimo strumento da utilizzare.

Un'altra opzione è quella di utilizzare HMMER.HMMER utilizza il Profilo Nascosto di Markov Modelli per allineare sequenze.Personalmente, credo che questo è uno dei più potenti approccio, poiché essa fornisce anche informazioni sulla posizione. http://hmmer.janelia.org/

Answer 8

Ho usato per lavorare con alcuni dei peggiori dati si potrà mai trovare.Una media di circa 5000 righe di dati (equivalente a centinaia di migliaia di dollari) necessari matching è stato faticoso totalmente.La mia prima esperienza con la corrispondenza fuzzy è un algoritmo di Mr Excel scritte in VBA.Aveva alcuni problemi con la coerenza che le cose mi aspettavo di essere zero per cento non erano tha e le cose che sono state a circa il 60% sembrava più del 90 per cento.Così, mi sono trasferito a Levenshtein e poi Damerau-di Levenshtein.Questo è stato un grande miglioramento, ma piuttosto lento in Excel.Poi ho saltato a Jaro-Winkler ma rapidamente eliminato subito dopo.Infine, nel 2016, ho scritto il mio (sulla base di n-grammi) e perfezionato nei prossimi 2 anni.Oggi è un add-on chiamato Flookup;si può ottenere su Google Fogli e vedere come si regge.