agrupando cadenas por similitud

Question

Tengo una matriz de cadenas, no muchas (tal vez unas pocas) pero a menudo largas (unos pocos cientos de caracteres).

Esas cuerdas son, por lo general, absurdas y diferentes unas de otras ... pero en un grupo de esas cuerdas, tal vez 5 de 300, hay una gran similitud. De hecho, son la misma cadena, lo que difiere es el formato, la puntuación y algunas palabras ...

¿Cómo puedo resolver ese grupo de cadenas?

Por cierto, estoy escribiendo en ruby, pero en todo caso un algoritmo en pseudocódigo estaría bien.

gracias

Answer 1

Hay muchas maneras de comparar cadenas de similitud.

Here is a site with various similarity metrics que puede usar.

Here is a Wikipedia article with various similarity metrics que puede usar.

Answer 2

Puede ser exagerado y posiblemente no exactamente lo que usted quiere lograr, pero es posible que pueda utilizar 'Ferret' para ayudar (la versión Ruby de Lucene - índice de texto completo/API de búsqueda) para clasifique la puntuación y el formato; también si las oraciones difieren por 'palabras de finalización' comunes (el, y es ...) pueden filtrarse.

A sus búsquedas se le asignarán ponderaciones, lo que da una idea de similitud.

http://www.davebalmain.com/ http://www.amazon.co.uk/Ferret-David-Balmain/dp/0596519400/ref=sr_1_2?ie=UTF8&s=books&qid=1264751909&sr=8-2

Answer 3

Puede utilizar el algoritmo de Levenshtein para esto. Here's una implementación en Ruby.

Answer 4

Suponiendo que usted no está preocupado por las faltas de ortografía u otros errores en cada palabra, se puede hacer lo siguiente:

construir un índice invertido, que es básicamente un resumen con clave de palabra, que apunta a una lista de punteros a las cadenas que contienen esa palabra (cómo manejas las ocurrencias duplicadas depende de ti). Para determinar las cadenas que son similares a una cadena de consulta dada, busque cada palabra de consulta en el índice, y para cada cadena fuente en las listas resultantes, cuente cuántas veces aparece la cadena fuente en cada lista. Las cadenas con los recuentos más altos son tus mejores candidatos para la similitud, ya que contienen la mayoría de las palabras en común.

Luego puede calcular la distancia de edición entre las dos cadenas, o cualquier otra métrica que desee. De esta forma evitará la complejidad O (n^2) de comparar cada cadena con cualquier otra cadena.