¿Cómo comparo frases de similitud?

Question

Al ingresar una pregunta, stackoverflow le presenta una lista de preguntas que probablemente cubra el mismo tema. También he visto funciones similares en otros sitios o en otros programas (sistemas de archivos de ayuda, por ejemplo), pero nunca he programado algo como esto yo mismo. Ahora tengo curiosidad por saber qué tipo de algoritmo usaría para eso.

El primer enfoque que me viene a la mente es dividir la frase en palabras y buscar frases que contengan estas palabras. Antes de hacer eso, probablemente desee descartar palabras insignificantes (como 'the', 'a', 'does', etc.), y luego querrá clasificar los resultados.

Hey, espera - vamos a hacer eso para las páginas web, y entonces podremos tener una ... ... watchamacallit - un "motor de búsqueda", y luego podemos vender anuncios, y luego ...

No, en serio, ¿cuáles son las formas más comunes de resolver este problema?

Answer 1

Un enfoque es el llamado modelo de bolsa de palabras.

Como ya has adivinado, primero debes contar cuántas veces aparecen palabras en el texto (generalmente llamadas documento en la jerga NLP). Luego tiras las llamadas palabras stop, como "the", "a", "or", etc.

Te quedan palabras y recuentos de palabras. Haga esto por un tiempo y obtendrá un conjunto completo de palabras que aparecerán en sus documentos. A continuación, puede crear un índice para estas palabras: "aardvark" es 1, "apple" es 2, ..., "z-index" es 70092.

Ahora puede tomar sus bolsas de palabra y convertirlas en vectores. Por ejemplo, si el documento contiene dos referencias para los cerdos hormigueros y nada más, que se vería así:

[2 0 0 ... 70k zeroes ... 0]. 

Después de esto se puede contar con el "ángulo" entre los dos vectores con a dot product. Cuanto menor es el ángulo, más cerca están los documentos.

Esta es una versión simple y hay otras técnicas más avanzadas. Puede el Wikipedia be with you.

Answer 2

Desde mi (bastante pequeña) experiencia desarrollando motores de búsqueda de texto completo: busco preguntas que contengan algunas palabras de la consulta (en su caso, la consulta es su pregunta). Claro, las palabras irrelevantes deben ignorarse y es posible que deseemos verificar la consulta de palabras 'fuertes' como 'ASP.Net' para limitar el alcance de la búsqueda. índices http://en.wikipedia.org/wiki/Index_(search_engine)#Inverted_indices'>Inverted se utilizan comúnmente para encontrar preguntas con las palabras que nos interesan.

Después de encontrar las preguntas con las palabras de la consulta, podríamos desea calcular la distancia entre las palabras que nos interesan en las preguntas, por lo que la pregunta con el texto "similitud de frases" ocupa un lugar más alto que la pregunta con el texto "Discutir similitud, escucha frases siguientes ...".

Answer 3

@Hanno deberías probar el algoritmo de distancia de Levenshtein. Dada una cadena de entrada s y una lista de cadenas de t iterar para cada cadena u en t y devolver la una con la distancia mínima Levenshtein.

http://en.wikipedia.org/wiki/Levenshtein_distance

Véase un ejemplo de implementación de Java en http://www.javalobby.org/java/forums/t15908.html

Answer 4

Para aumentar la idea de bolsa de palabras:

Hay algunas maneras que usted puede también prestar atención a los n-gramas, cadenas de dos o más palabras mantenidas en orden. Es posible que desee hacer esto porque una búsqueda de "complejidad espacial" es mucho más que una búsqueda de elementos con "espacio" Y "complejidad" en ellos, ya que el significado de esta frase es más que la suma de sus partes; es decir, si obtienes un resultado que habla sobre la complejidad del espacio exterior y el universo, probablemente esto no sea lo que realmente significaba la búsqueda de "complejidad espacial". Una idea clave del procesamiento del lenguaje natural aquí es mutual information, que le permite (algorítmicamente) juzgar si una frase es realmente una frase específica (como "complejidad del espacio") o simplemente palabras que son casualmente adyacentes . Matemáticamente, la idea principal es preguntar, de manera probabilística, si estas palabras aparecen una al lado de la otra más a menudo de lo que usted adivinaría solo por sus frecuencias. Si ve una frase con un alto puntaje de información mutua en su consulta de búsqueda (o durante la indexación), puede obtener mejores resultados tratando de mantener estas palabras en secuencia.