algorithm - uipath - fulltext chile

¿Cómo comparo frases para 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.

Oye, espera - hagámoslo para las páginas web, y luego podemos tener un ... watchamacallit ... - un "motor de búsqueda", y luego podemos vender anuncios, y luego ...

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

Answer 1

@Hanno deberías probar el algoritmo de distancia Levenshtein. Dada una cadena de entrada s y una lista de cadenas, itera para cada cadena u en t y devuelve la que tiene la distancia mínima de Levenshtein.

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

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

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). Por supuesto, las palabras irrelevantes deben ignorarse y es posible que deseemos consultar la consulta de palabras ''fuertes'' como ''ASP.Net'' para limitar el alcance de la búsqueda. http://en.wikipedia.org/wiki/Index_(search_engine)#Inverted_indices''> Los índices invertidos se usan comúnmente para encontrar preguntas con palabras que nos interesan.

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

Answer 3

Para aumentar la idea de la bolsa de palabras:

Hay algunas formas en que también puede prestar atención a n-grams, 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 la de la información mutua , que le permite (algorítmicamente) juzgar si una frase es realmente una frase específica (como la "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.

Answer 4

Un enfoque es el llamado modelo de bolsa de palabras.

Como habrás adivinado, primero cuentas cuántas veces aparecen las palabras en el texto (generalmente llamado 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 puedes tomar tus bolsas de palabras y convertirlas en vectores. Por ejemplo, si su documento contiene dos referencias para aardvarks y nada más, se vería así:

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

Después de esto, puede contar el "ángulo" entre los dos vectores con un producto de puntos . 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. Que la Wikipedia te acompañe .