la coincidencia de cadenas aproximada con una matriz de confusión carta?

Question

Estoy tratando de modelar un reconocedor de fonética que tiene que aislar los casos de las palabras (cadenas de teléfonos) de un gran chorro de teléfonos que no tienen espacios entre cada palabra. La corriente de los teléfonos puede haber sido poco reconocido, con sustituciones de letras / inserciones / deleciones, así que voy a tener que ver la coincidencia de cadenas aproximada.

Sin embargo, quiero que el juego para ser fonéticamente motivado-, por ejemplo "M" y "n" son fonéticamente similares, por lo que el costo de sustitución de "m" para "n" debe ser pequeña, en comparación con decir, "m" y "k". Por lo tanto, si yo estoy buscando [mein] "principal", coincidiría con la secuencia de letras [meim] "aguas calientes" con, por ejemplo, el costo de 0,1, mientras que coincidiría con la secuencia de letras [meik] "marca" con, digamos , costará 0,7. Del mismo modo, existen diferentes costos para insertar o eliminar cada letra. Puedo suministrar una matriz de confusión que, para cada par de letras (x, y), da el costo de la sustitución de x con y, donde X e Y son cualquier letra o la cadena vacía.

Sé que hay herramientas disponibles que hacen correspondencia aproximada como agrep, pero por lo que puedo decir, que no tomo una matriz de confusión como entrada. Es decir, el costo de cualquier de inserción / sustitución / eliminación = 1. Mi pregunta es, ¿hay herramientas de código abierto ya disponibles que pueden hacer correspondencia aproximada con matrices de confusión, y si no, lo que es un algoritmo bien que pueda poner en práctica para lograr esto?

EDIT: sólo para que quede claro, yo estoy tratando de aislar los casos aproximados de una palabra como [mein] a partir de una cadena más larga, por ejemplo, [Aiammeinlimeiking ...]. Idealmente, el algoritmo / herramienta debe reportar casos como [mein] con costo 0,0 (coincidencia exacta), [meik] con costo 0,7 (cerca de fósforo), etc, para todos los partidos de cadena aproximadas con un coste por debajo de un umbral dado.

Answer 1

No estoy al tanto de cualquier reconocedores fonéticos que las matrices de confusión uso. Sé de Soundex , y rating partido .

Creo que el href="http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm" rel="nofollow noreferrer"> K-vecino más cercano algoritmo podría ser útil para el tipo de aproximaciones que le interesa.

Answer 2

Alfombra / L04 (para la dialectología computacional) incluye una implementación de levenshtein distancia que le permite especificar no uniforme de inserción, supresión, y los costes de sustitución.