2011-03-10 22 views
23

Soy consciente de los duplicados de esta pregunta:¿Cómo se aproxima "Quiso decir?" sin usar Google?

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?

Ok. Pruebe a escribir "qualfy" en Google y le dice:

¿Se refiere a:calificar suficiente

Feria. Utiliza Statistical Machine Learning en datos recopilados de miles de millones de usuarios para hacer esto. Pero ahora intente introducir esto: "Trytoreconnectyou" en Google y le dice:

¿Se refiere a:intentar volver a conectar Usted

Ahora bien, 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 las entradas 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?

+0

@Benjamin: ¿También puedo tener una lista de conjuntos de datos que pueden aprovecharse? No soy de este dominio, por lo que cualquier ayuda adicional será una bendición. – Legend

+7

¿Has leído las respuestas a los enlaces que publicaste? La segunda respuesta al primer enlace apunta a http://norvig.com/spell-correct.html que es más o menos exactamente lo que estás buscando. – Gabe

+0

posible duplicado de [¿Cómo se entiende Google? ¿Algoritmo?] (Http://stackoverflow.com/questions/307291/how-does-the-google-did-you-mean-algorithm-work) – Gabe

Respuesta

9

Asumiendo 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 del sistema de la mejor caso) y que conoces la frecuencia relativa de las distintas palabras, debes ser capaz de adivinar razonablemente a qué se refería el usuario a través de alguna combinación del similarity of the word 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).

+1

Esta búsqueda de diccionario se puede resolver con un trie. – Bytemain

+0

He estado buscando un algoritmo de distancia de palabras para * yonks *. Gracias. – AJFarmar

3

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

Para Trytoreconnectyou, primero verificamos con todos los gramos (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 here 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.

+1

Google lo hace rápido no porque fuerza bruta todas las combinaciones, sino porque la búsqueda heurística atrae la complejidad a sub-liniar. – yura

2

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 negocia 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.

7

De la boca del caballo: How to Write a Spelling Corrector

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

1

@Legend: considere usar una de las variaciones del Soundex algorithm. 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):

pronto recordé otro algoritmo Soundex similar que había correr a través de un par de años atrás. En this Dr. Dobb's article, Lawrence Philips analiza las mejoras de su algoritmo Metaphone, apodado Double Metaphone.

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

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

2

conjuntos de datos/herramientas que pueden ser útiles:

Puede utilizar WordNet como un simple diccionario de términos, y se puede impulsar que 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 su lugar, le sugiero que utilice algo así 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 bigrams o trigramas del personaje harían el truco) y lo almacenarías en LSH.

Dada toda consulta, puede utilizar una búsqueda de vecinos cercanos aproximados en el LSH descrito en Charikar para encontrar el vecino más cercano de su conjunto de posibles coincidencias.

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

Cuestiones relacionadas