java - metrica - Algoritmos de similitud de texto

distancias de levenshtein

Question

Estoy haciendo un proyecto Java donde tengo que hacer un programa de similitud de texto. Quiero tomar 2 documentos de texto, luego compararlos entre sí y obtener la similitud de los mismos. Cuán similares son entre sí.

Más adelante, pondré una base de datos que puede encontrar los sinónimos de las palabras e ir a través del texto para ver si uno de los escritores de documentos de texto acaba de cambiar las palabras a otros sinónimos, mientras que el texto es exactamente el mismo. Lo mismo con los paragrafs en movimiento hacia arriba o hacia abajo. Sí, como era un programa de plagarismo ...

Quiero saber de ustedes qué tipo de algoritmos recomendarían.

He encontrado la similitud de Levenstein y Cosine mirando aquí y otros lugares. Ambos parecen ser mencionados mucho. La distancia de Hamming es otra de las que me habló mi maestro.

Tengo algunas preguntas relacionadas con esas ya que realmente no estoy obteniendo Wikipedia. ¿Podría alguien explicarme esas cosas a mí?

Levenstein : este algoritmo cambió por sub, agrega y elimina la palabra y observa qué tan cerca está de la otra palabra en el documento de texto. Pero, ¿cómo se puede usar eso en un archivo de texto completo? Puedo ver cómo se puede usar en una palabra, pero no en una oración o en un documento de texto completo de una a otra.

Coseno : es la medida de similitud entre dos vectores al medir el coseno del ángulo entre ellos. ¿Qué no entiendo aquí cómo dos textos pueden convertirse en 2 vectores y qué hay de las palabras / oraciones en ellos?

Hamming : Esta distancia parece funcionar mejor que Levenstein, pero es solo en cadenas iguales. ¿Por qué es importante cuando 2 documentos e incluso las oraciones en ellos no son dos cadenas de igual longitud?

Wikipedia debería tener sentido pero no lo es. Lo siento si las preguntas suenan demasiado estúpidas, pero me cuelgan y creo que hay personas aquí que son bastante capaces de explicarlo, por lo que incluso los nuevos principiantes en este campo pueden entenderlo.

Gracias por tu tiempo.

Answer 1

Considere el ejemplo en wikipedia para la distancia de Levenshtein:

For example, the Levenshtein distance between "kitten" and "sitting" is 3, since the following three edits change one into the other, and there is no way to do it with fewer than three edits:

   1. kitten → sitten (substitution of ''s'' for ''k'')
   2. sitten → sittin (substitution of ''i'' for ''e'')
   3. sittin → sitting (insertion of ''g'' at the end).

Ahora, reemplace "gatito" con "texto del primer papel", y "sentado" con "texto del segundo papel".

Paper[] papers = getPapers();
for(int i = 0; i < papers.length - 1; i++) {
    for(int j = i + 1; j < papers.length; j++) {
        Paper first = papers[i];
        Paper second = papers[j];
        int dist = compareSimilarities(first.text,second.text);
        System.out.println(first.name + "''s paper compares to " + second.name + "''s paper with a similarity score of " + dist);
    }
}

Compara esos resultados y fija a los niños con las puntuaciones de distancia más bajas.

En su método compareSimilarities , puede usar cualquiera o todos los algoritmos de comparación. Otro que podría incorporar a la fórmula es "subcadena común más larga" (que es un buen método para encontrar plagio).

Answer 2

La idea básica de comparar la similitud entre dos documentos, que es un tema en la recuperación de información, es extraer algunas huellas digitales y juzgar si comparten alguna información basada en la huella digital.

Solo algunos consejos, el Winnowing: Algoritmos locales para huellas digitales de documentos puede ser una opción y un buen punto de partida para su problema.

Answer 3

Levenstein: en teoría, podría usarlo para un archivo de texto completo, pero en realidad no es muy adecuado para la tarea. Realmente está pensado para palabras sueltas o (como máximo) una frase corta.

Coseno: Comience simplemente contando las palabras únicas en cada documento. Las respuestas a una pregunta anterior cubren el cálculo una vez que lo haya hecho.

Nunca he usado la distancia de Hamming para este propósito, así que no puedo decir mucho al respecto.

Yo agregaría TFIDF (Frecuencia de término * Frecuencia de documento invertida) a la lista. Es bastante similar a la distancia Cosine, pero 1) tiende a hacer un mejor trabajo en documentos más cortos, y 2) hace un mejor trabajo teniendo en cuenta qué palabras son extremadamente comunes en todo el corpus en lugar de solo las que son comunes a dos documentos particulares.

Una nota final: para que cualquiera de estos produzca resultados útiles, casi necesita eliminar las palabras de parada antes de tratar de calcular el grado de similitud (aunque TFIDF parece hacerlo mejor que los demás si omite esto). Al menos en mi experiencia, también es extremadamente útil para eliminar las palabras (eliminar sufijos). Cuando lo hice, utilicé el algoritmo stemmer de Porter.

Para sus propósitos, probablemente desee usar lo que he denominado un tesauro invertido, que le permite buscar una palabra, y para cada palabra sustituir ese significado por una sola palabra canónica. Intenté esto en un proyecto y no lo encontré tan útil como se esperaba, pero parece que para su proyecto probablemente sería mucho más útil.