algorithm language-agnostic nlp machine-learning

algorithm - ¿Cómo me acerco a "¿Querías decir?" Sin usar Google?



language-agnostic nlp (7)

Estoy enterado de los duplicados de esta pregunta:

Estas preguntas están interesadas en cómo funciona realmente el algoritmo. Mi pregunta es más parecida a la siguiente: supongamos que Google no existía o que tal vez esta característica no existía y no contamos con la participación del usuario. ¿Cómo se puede implementar una versión aproximada de este algoritmo?

¿Por qué es esto interesante?

De acuerdo. Intenta escribir " qualfy " en Google y te dice:

¿Querías decir? Calificar

Lo suficientemente justo. Utiliza Statistical Machine Learning en datos recopilados de miles de millones de usuarios para hacer esto. Pero ahora intenta escribir esto: " Trytoreconnectyou " en Google y te dice:

¿Querías decir? Intenta reconectarte

Ahora esta es la parte más interesante. ¿Cómo determina Google esto? Tener un diccionario a mano y adivinar las palabras más probables de nuevo con la entrada del usuario? ¿Y cómo diferencia entre una palabra mal escrita y una oración?

Ahora, considerando que la mayoría de los programadores no tienen acceso a la información de miles de millones de usuarios, estoy buscando la mejor forma aproximada de implementar este algoritmo y qué recursos están disponibles (conjuntos de datos, bibliotecas, etc.). ¿Alguna sugerencia?

@Legend: considere usar una de las variaciones del algoritmo de Soundex . Tiene algunos defectos conocidos, pero funciona decentemente bien en la mayoría de las aplicaciones que necesitan aproximarse a las palabras mal escritas.

Editar (2011-03-16):

De repente recordé otro algoritmo tipo Soundex con el que me había topado hace un par de años. En este artículo del Dr. Dobb , Lawrence Philips analiza las mejoras de su algoritmo Metaphone, denominado Double Metaphone.

here puede encontrar una implementación de Python de este algoritmo y más implementaciones en el mismo sitio.

Una vez más, estos algoritmos no serán los mismos que usa Google, pero para palabras en inglés deberían acercarse mucho más. También puede consultar la página de wikipedia de Algoritmos fonéticos para obtener una lista de otros algoritmos similares.

Conjuntos de datos / herramientas que pueden ser útiles:

Puede usar WordNet como un diccionario de términos simple, y puede aumentar eso con términos frecuentes extraídos de un corpus.

Puede utilizar el enlace Peter Norvig mencionado anteriormente como primer intento, pero con un diccionario grande, esta no será una buena solución.

En cambio, sugiero que uses algo como hashing sensible a la localidad (LSH). Esto se usa comúnmente para detectar documentos duplicados, pero funcionará igual de bien para la corrección ortográfica. Necesitará una lista de términos y cadenas de términos extraídos de sus datos que cree que las personas pueden buscar; deberá elegir una longitud de corte para las cadenas. Alternativamente, si tiene algunos datos de lo que la gente realmente busca, puede usar eso. Para cada cadena de términos generas un vector (probablemente los bráctems o trigramas de carácter harían el truco) y lo almacenarías en LSH.

Dada cualquier consulta, puede usar una búsqueda de un vecino más cercano en el LSH descrito por Charikar para encontrar al vecino más cercano fuera de su conjunto de posibles coincidencias.

Nota: se eliminaron los enlaces porque soy un nuevo usuario, lo siento.

De la boca del caballo: norvig.com/spell-correct.html

Lo interesante aquí es cómo no necesitas un montón de registros de consulta para aproximar el algoritmo. Puede usar un corpus de texto en su mayoría correcto (como un montón de libros del Proyecto Gutenberg).

Impresionante tutroail uno cómo su trabajo se puede encontrar aquí http://alias-i.com/lingpipe-3.9.3/demos/tutorial/querySpellChecker/read-me.html .

En pocas palabras, se trata de cambiar la modificación de la consulta (en el nivel de carácter o palabra) para aumentar la cobertura en los documentos de búsqueda. Por ejemplo, "aple" lleva a documentos de 2 mln, pero "apple" lleva a 60 mln y la modificación es de solo un carácter, por lo tanto, es obvio que te refieres a la manzana.

Suponiendo que tiene un diccionario de palabras (todas las palabras que aparecen en el diccionario en el peor de los casos, todas las frases que aparecen en los datos de su sistema en el mejor de los casos) y que conoce la frecuencia relativa de las distintas palabras, usted debería ser capaz de adivinar razonablemente a qué se refería el usuario mediante una combinación de la similitud de la palabra y el número de visitas para la palabra similar. Los pesos obviamente requieren un poco de prueba y error, pero generalmente el usuario estará más interesado en un resultado popular que está un poco más alejado lingüísticamente de la cadena que ingresaron que en una palabra válida que es lingüísticamente más cercana, pero solo tiene uno o dos éxitos en tu sistema.

El segundo caso debería ser un poco más directo. Encuentra todas las palabras válidas que comienzan la cadena ("T" no es válida, "Tr" no es válida, "Prueba" es una palabra, "Tryt" no es una palabra, etc.) y para cada palabra válida, repite el Algoritmo para la cadena restante. Esto debería ser bastante rápido suponiendo que su diccionario está indexado. Si encuentra un resultado en el que puede descomponer la cadena larga en un conjunto de palabras válidas sin caracteres restantes, eso es lo que recomienda. Por supuesto, si eres Google, probablemente modifiques el algoritmo para buscar subcadenas que estén razonablemente cerca de los errores de palabras reales y tienes algo de lógica para manejar casos donde una cadena se puede leer de múltiples maneras con un corrector ortográfico lo suficientemente flojo (posiblemente usando la cantidad de resultados para romper el empate).

Creo que esto se puede hacer usando un spellchecker junto con N-grams .

Para Trytoreconnectyou , primero verificamos con 1 gramo (todas las palabras del diccionario) y encontramos una coincidencia más cercana que es bastante terrible. Así que probamos 2 gramos (que se puede construir eliminando espacios de frases de longitud 2), y luego 3 gramos, y así sucesivamente. Cuando intentamos un 4-gramo, encontramos que hay una frase que está a 0 distancia de nuestro término de búsqueda. Como no podemos hacer nada mejor que eso, devolvemos esa respuesta como sugerencia.

Sé que esto es muy ineficiente, pero la publicación de Peter Norvig sugiere claramente que Google usa correctores de hechizos para generar sus sugerencias. Dado que Google tiene capacidades de paralelización masiva, pueden realizar esta tarea muy rápidamente.