2009-12-17 19 views
14

Actualmente estoy trabajando en un proyecto que requiere que haga coincidir nuestra base de datos de Bandas y recintos con una serie de servicios externos.¿Cómo puedo determinar si dos nombres de bandas similares representan la misma banda?

Básicamente estoy buscando alguna dirección sobre el mejor método para determinar si dos nombres son iguales. Por ejemplo:

  • Nuestro nombre local de base de datos - "The Pig and Whistle"
  • servicio 1 - "Pig and Whistle"
  • servicio 2 - "El cerdo & silbato"
  • , etc, etc

Creo que las principales diferencias van a ser cosas como "falta" o "&" en lugar de "y", pero también podría haber cosas como ortografía y palabras ligeramente diferentes en orde diferente rs.

¿Qué algoritmos/técnicas se usan comúnmente en esta situación? ¿Necesito filtrar palabras irrelevantes o hacer algún tipo de revisión ortográfica?

¿Has visto algún ejemplo de algo similar en C#?

ACTUALIZACIÓN: En caso de que alguien está interesado en AC# ejemplo, hay un montón puede acceder haciendo a El (y probablemente el más fácil) manera google code search for Levenshtein distance

Respuesta

14

canónica de hacer esto es medir la Levenshtein distance entre las dos cuerdas. Si la distancia es pequeña en relación con el tamaño de la cuerda, probablemente sea la misma cuerda. Tenga en cuenta que si tiene que comparar muchas cadenas muy pequeñas, será más difícil determinar si son iguales o no. Funciona mejor con cadenas más largas.

Un enfoque más inteligente podría ser comparar la distancia Levenshtein entre las dos cadenas, pero para asignar una distancia de cero a las transformaciones más evidentes, al igual que "y"/"&", 'Snoop Dogg'/'Snoop', etc.

+0

Impresionante, ¿crees que todavía sería efectivo decir si eliminé palabras como "the", "and" y "&"? –

+1

Asignar una distancia de cero es equivalente a eliminarlos de la cadena, sí. También podría quitar el espacio en blanco/puntuación para evitar que los espacios adicionales lo afecten. Pero solo tenga cuidado de que esos no sean significativos para el nombre de la banda. Por ejemplo, "!!!" es el nombre de una banda (http: //en.wikipedia.org/wiki/ !!!). –

+1

Es posible que desee considerar la eliminación de palabras de parada de las cadenas de texto - (como "el" "un" "y" etc.) las bases de datos de palabras en inglés son bastante fáciles de encontrar. –

0

soundex también puede ser útil

+2

Si bien este enlace puede responder a la pregunta, es mejor incluir las partes esenciales de la respuesta aquí y proporcionar el enlace de referencia. Las respuestas de solo enlace pueden dejar de ser válidas si la página vinculada cambia. –

+1

@BryanCrosby: en general está de acuerdo, pero repetir el algoritmo de soundex fundamental aquí es una pérdida de espacio. Incluso si el enlace subyacente desaparece, el nombre del algoritmo debería ser suficiente. A menos que Google también desaparezca;) –

0

en la bioinformática que utilizamos este para comparar las secuencias de ADN o de proteínas todo el tiempo.

Hay muchos algoritmos, es probable que desee consultar las alineaciones globales .

En este sentido, el Needleman-Wunsch algorithm es probablemente lo que buscas.

Si tiene series recurrentes particularmente largas para comparar, también podría considerar búsquedas heurísticas como BLAST.

1

Hice algo como esto hace un tiempo, utilicé la base de datos Discogs (que es de dominio público), que también rastrea los alias de los artistas;

Puede:

  • utilizar un (campo namevariations) API call.
  • Descargue monthly data dumps (*_artists.xml.gz) & impórtelo en su base de datos. Esto contiene la misma información, pero obviamente es mucho más rápido.

Una ventaja de esto sobre la solución Levenshtein distance) es que obtendrá muchas menos coincidencias falsas.
Por ejemplo, Ryan AdamsBryan Adams y tienen una puntuación de 2, que es bastante bueno (menos es mejor partidos, Pig and Whistle y Pig & Whistle tiene un récord de 3), sin embargo, son obviamente diferentes personas.

Si bien podría hacer un algoritmo más inteligente (que también mira la longitud de la cadena, por ejemplo), usar el alias DB es mucho más simple & menos error-teléfono; Después de implementar esto, pude eliminar completamente la solución que se sugirió en la otra respuesta. & tenía mejores coincidencias.

Cuestiones relacionadas