Approssimativa string matching con una matrice lettera confusione?

Question

Sto cercando di modellare un sistema di riconoscimento fonetica che deve casi isolare di parole (stringhe di telefoni) su un lungo flusso di telefoni che non hanno spazi tra ogni parola. Il flusso di telefoni potrebbe essere stata poco riconosciuta, con la lettera sostituzioni / inserzioni / delezioni, quindi dovrò fare approssimativa string matching.

Tuttavia, voglio l'abbinamento a essere foneticamente-motivato, per esempio "M" e "n" sono foneticamente simili, quindi il costo di sostituzione di "m" per "n" deve essere piccolo, rispetto a dire, "m" e "k". Quindi, se io sto cercando [mein] "principale", sarebbe partita la sequenza di lettere [meim] "mutilare" con, diciamo, costo 0,1, mentre sarebbe abbinare la sequenza di lettere [Meik] "make" con, diciamo , costato 0.7. Analogamente, vi sono costi differenti per l'inserimento o l'eliminazione di ogni lettera. Posso fornire una matrice di confusione che, per ogni coppia di lettere (x, y), dà il costo di sostituire x con y, dove xey sono qualsiasi lettera o la stringa vuota.

So che ci sono strumenti disponibili che fanno ricerca per approssimazione quali agrep, ma per quanto ne so, non prendono una matrice di confusione come input. Cioè, il costo di qualsiasi inserimento / sostituzione / eliminazione = 1. La mia domanda è, ci sono strumenti open-source già disponibili che possono fare una ricerca per approssimazione con matrici confusione, e se no, qual è un algoritmo bene che posso realizzare per realizzare questo?

EDIT: tanto per essere chiari, sto cercando di isolare le istanze approssimative di una parola come [mein] da una stringa più lunga, per esempio [Aiammeinlimeiking ...]. Idealmente, l'algoritmo / strumento dovrebbe riferire casi come [mein] con costo 0.0 (corrispondenza esatta), [Meik] con costo 0,7 (quasi concordanza), ecc, per tutte le partite approssimative stringa con un costo inferiore a una certa soglia.

Answer 1

io non sono a conoscenza di eventuali sistemi di riconoscimento fonetici che matrici uso confusione. So di Soundex , e partita Valutazione .

Credo che la href="http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm" rel="nofollow noreferrer"> K-nearest algoritmo prossimo potrebbe essere utile per il tipo di approssimazioni che ti interessa.

Answer 2

di Peter Kleiweg Rug / L04 (per la dialettologia computazionale) include un'implementazione di Levenshtein distanza che consente di specificare non uniforme inserimento, cancellazione, e dei costi di sostituzione.