¿Errores de tipografía del mundo real?

Question

¿Dónde puedo encontrar estadísticas de erratas del mundo real?

Estoy tratando de hacer coincidir el texto de entrada de las personas con los objetos internos, y la gente tiende a cometer errores ortográficos.
Hay 2 tipos de errores:

1. typos - "Helllo" en lugar de "Hola"/"Satudray" en lugar de "Sábado", etc.
2. Spelling - "Shikago" en lugar de "Chicago"

utilizo Damerau-Levenshtein distance para los errores tipográficos y Double Metaphone para la ortografía (implementaciones Python here y here).

Quiero centrarme en Damerau-Levenshtein (o simplemente edit-distance). Las implementaciones de libros de texto siempre usan '1' para el peso de eliminaciones, sustituciones de inserciones y transposiciones. Si bien esto es simple y permite buenos algoritmos, no coincide con "realidad"/"probabilidades del mundo real".

Ejemplos:

• estoy seguro de que la probabilidad de "Helllo" ("Hola") es mayor que "Helzlo", sin embargo, son ambos 1 editar distancia.
• "Gello" está más cerca que "Qello" a "Hola" en un teclado QWERTY.
• Transcripciones en Unicode: ¿Cuál es la distancia "real" entre "München" y "Munchen"?

¿Cuáles deberían ser los pesos del "mundo real" para las eliminaciones, inserciones, sustituciones y transposiciones?

Incluso Norvig's very cool spell corrector usa la distancia de edición no ponderada.

Por cierto, estoy seguro de que los pesos deben ser funciones y no flotadores simples (por los ejemplos anteriores) ...

puedo ajustar el algoritmo, pero donde puedo "aprender" estos pesos? No tengo acceso a Google-scale data ...

¿Debería adivinarlos?

EDITAR - tratando de responder a las preguntas de los usuarios:

• Mi actual algoritmo no ponderado falla a menudo cuando se enfrentan a los errores tipográficos, por las razones anteriores. "Regresar el jueves": cada "persona real" puede decir con facilidad que el jueves es más probable que el martes, ¡pero están a una distancia de 1 edición! (Sí, registro y mido mi rendimiento).
• Estoy desarrollando un motor de búsqueda de viajes NLP, por lo que mi diccionario contiene ~ 25K destinos (se espera que crezca a 100K), Expresiones de tiempo ~ 200 (esperado 1K), Expresiones de personas ~ 100 (esperado 300), Expresiones de dinero ~ 100 (esperado 500), "palabras lógicas de pegamento" ("desde", "hermoso", "apartamento") ~ 2K (esperado 10K) y así sucesivamente ...
• El uso de la distancia de edición es diferente para cada uno de los anteriores grupos de palabras. Intento "autocorregir cuando sea obvio", p. Ej. 1 edita la distancia desde solo 1 palabra más en el diccionario.Tengo muchas otras reglas ajustadas a mano, p. Ej. Doble corrección de Metaphone que no está a más de 2 horas de distancia de una palabra de diccionario con una longitud> 4 ... La lista de reglas continúa creciendo a medida que aprendo de la información del mundo real.
• "¿Cuántos pares de entradas de diccionario están dentro de su umbral?": Bueno, eso depende del "sistema de ponderación elegante" y de la entrada del mundo real (futuro), ¿no es así? De todos modos, tengo pruebas unitarias extensas para que cada cambio que haga en el sistema solo lo haga mejor (basado en entradas pasadas, por supuesto). La mayoría de las palabras con letras inferiores a 6 están dentro de una distancia de edición de una palabra que está a una distancia de edición de otra entrada del diccionario.
• Hoy cuando hay 2 entradas de diccionario a la misma distancia de la entrada trato de aplicar varias estadísticas para adivinar mejor lo que el usuario quería decir (por ejemplo, París, es más probable que aparezcan en mi búsqueda que Pārīz, Irán).
• El costo de elegir una palabra incorrecta es devolver resultados semialeatorios (a menudo ridículos) al usuario final y potencialmente perder un cliente. El costo de no comprender es un poco menos costoso: se le pedirá al usuario que reformule.
• ¿Vale la pena el costo de la complejidad? Sí, estoy seguro de que así es. No creería la cantidad de errores tipográficos que la gente lanza al sistema y espera que lo entienda, y podría usar el impulso en Precision and Recall.

Answer 1

Posible fuente de estadísticas de typo del mundo real estaría en el Historial de edición completo de Wikipedia.

http://download.wikimedia.org/

También, usted puede estar interesado en RegExTypoFix

del AWB

http://en.wikipedia.org/wiki/Wikipedia:AWB/T

Answer 2

Le aconsejo que consulte el trigram alogrithm. En mi opinión, funciona mejor para encontrar errores tipográficos y luego editar el algoritmo de distancia. También debería funcionar más rápido y si mantiene el diccionario en la base de datos de postgres, puede utilizar el índice.

Usted puede encontrar stackoverflow útil topic sobre Google "¿Se refiere a"

Answer 3

Algunas preguntas para usted, para ayudar a determinar si usted debe pedir su "¿dónde puedo encontrar los pesos del mundo real" pregunta: ¿

¿Ha medido realmente la efectividad de la implementación de ponderación uniforme? ¿Cómo?

¿Cuántos "objetos internos" diferentes tiene, es decir, cuál es el tamaño de su diccionario?

¿Cómo está usando la distancia de edición, p. John/Joan, Marmaduke/Marmeduke, Featherstonehaugh/Featherstonhaugh: ¿es ese "todo 1 error" o es 25%/11.1%/5.9% de diferencia? ¿Qué umbral estás usando?

¿Cuántos pares de entradas de diccionario se encuentran dentro de su umbral (por ejemplo, John vs Joan, Joan vs Juan, etc.)? Si introdujo un sistema de ponderación sofisticado, ¿cuántos pares de entradas de diccionario migrarían (a) desde el interior del umbral al exterior (b) y viceversa?

¿Qué hacer si Juan y Juan están en su diccionario y el usuario escribe Joan?

¿Cuáles son las penalidades/costos de (1) elegir la palabra equivocada del diccionario (no la que el usuario quiso decir) (2) no reconocer la entrada del usuario?

¿La introducción de un sistema de ponderación complicado en realidad reduce las probabilidades de los dos tipos de error anteriores por un margen suficiente para que la complicación y la velocidad más lenta valen la pena?

Por cierto, ¿cómo sabes qué teclado estaba usando el usuario?

Actualización:

"" "Mi actual algoritmo no ponderado falla a menudo cuando se enfrentan a los errores tipográficos por las razones anteriores. 'Retorno de la Tursday': cada 'persona real' puede decir fácilmente jueves es más probable que los Martes , sin embargo, ambos están a 1-edición-distancia de distancia. (Sí, registro y mido mi rendimiento). "" "

Sí, jueves -> jueves por omisión de una" h ", pero martes -> jueves por sustituyendo "r" en lugar de "e". E y R están uno junto al otro en los teclados qwERTY y azERty. Cada "persona real" puede fácilmente suponer que el jueves es más probable que el martes. Incluso si las estadísticas y las suposiciones apuntan a que el jueves es más probable que el martes (tal vez omitir h costará 0.5 y e-> r costará 0.75), ¿la diferencia (quizás 0.25) será lo suficientemente significativa como para elegir siempre el jueves? Puede/su sistema preguntará "¿Querías decir martes?" ¿o lo hará/seguirá adelante el jueves?

Answer 4

Si la investigación es de su interés, creo que continuar con ese algoritmo, tratando de encontrar pesos decentes sería fructífero.

No puedo ayudarte con las estadísticas de tipografía, pero creo que también deberías jugar con difflib de python. Específicamente, el método de proporción() de SequenceMatcher. Utiliza un algoritmo que la afirmación de documentos http://docs.python.org/library/difflib.html es adecuada para que coincida con "aspecto correcto" y puede ser útil para aumentar o probar lo que está haciendo.

Para los programadores de python que solo buscan errores tipográficos es un buen lugar para comenzar. Uno de mis compañeros de trabajo ha usado la distancia de edición de Levenshtein y la proporción de SequenceMatcher() y obtuvo resultados mucho mejores a partir de la relación().

Answer 5

Probability Scoring for Spelling Correction por Church y Gale podría ayudar. En ese documento, los autores modelan los errores tipográficos como un canal ruidoso entre el autor y la computadora. El apéndice tiene tablas de errores tipográficos vistos en un corpus de publicaciones de Associated Press. Hay una mesa para cada uno de los siguientes tipos de errores tipográficos:

• deleción
• inserción
• sustitución
• transposición

Por ejemplo, el examen de la tabla de inserción, podemos ver que l incorrectamente insertado después de l 128 veces (el número más alto en esa columna). Usando estas tablas, puedes generar las probabilidades que estás buscando.