algorithm - damerau - levenshtein distance theory

Algoritmo de comparación de palabras

Question

Estoy haciendo una herramienta de importación de CSV para el proyecto en el que estoy trabajando. El cliente debe poder ingresar los datos en Excel, exportarlos como CSV y cargarlos a la base de datos. Por ejemplo, tengo este registro CSV:

   1,   John Doe,     ACME Comapny   (the typo is on purpose)

Por supuesto, las compañías se guardan en una tabla separada y se vinculan con una clave externa, por lo que necesito descubrir la identificación correcta de la compañía antes de insertarla. Planeo hacer esto comparando los nombres de las compañías en la base de datos con los nombres de las compañías en el CSV. la comparación debería devolver 0 si las cadenas son exactamente iguales, y devolver algún valor que se agrande a medida que las cadenas se vuelven más diferentes, pero strcmp no lo corta aquí porque:

"Acme Company" y "Acme Comapny" deberían tener un índice de diferencia muy pequeño, pero "Acme Company" y "Cmea Mpnyaco" deberían tener un índice de diferencia muy grande o "Acme Company" y "Acme Comp". también debería tener un índice de diferencia pequeño, aunque el recuento de caracteres sea diferente. Además, "Acme Company" y "Company Acme" deberían devolver 0.

Entonces, si el cliente hace un tipo al ingresar datos, podría pedirle que elija el nombre que más deseaba insertar.

¿Hay algún algoritmo conocido para hacer esto o quizás podamos inventar uno :)?

Answer 1

De hecho, he implementado un sistema similar. Utilicé la distancia de Levenshtein (como otros carteles ya sugeridos), con algunas modificaciones. El problema con la distancia de edición no modificada (aplicada a cadenas enteras) es que es sensible al reordenamiento de palabras, por lo que "Acme Digital Incorporated World Company" se comparará pobremente con "Digital Incorporated World Company Acme" y dichos reordenamientos fueron bastante comunes en mis datos.

Lo modifiqué de modo que si la distancia de edición de las cuerdas enteras era demasiado grande, el algoritmo volvía a emparejar palabras entre sí para encontrar una buena coincidencia palabra por palabra (costo cuadrático, pero había un límite si había demasiados palabras, así que funcionó bien).

Answer 2

Hay múltiples algoritmos para hacer justamente eso, y la mayoría de las bases de datos incluso incluyen una por defecto. En realidad, es una preocupación bastante común.

Si solo se trata de palabras en inglés, SQL Server, por ejemplo, incluye SOUNDEX que se puede usar para comparar el sonido resultante de la palabra.

http://msdn.microsoft.com/en-us/library/aa259235%28SQL.80%29.aspx

Answer 3

He tenido cierto éxito con el algoritmo Levenshtein Distance , también hay Soundex .

¿En qué idioma estás implementando esto? podemos ser capaces de señalar ejemplos específicos

Answer 4

Lo estoy implementando en PHP, y ahora estoy escribiendo un fragmento de código que dividirá 2 cadenas en palabras y comparará cada una de las palabras de la primera cadena con las palabras de la segunda cadena usando levenshtein y aceptará los valores posibles bajos . Lo publicaré cuando haya terminado.

Muchas gracias.

Actualización: Esto es lo que se me ocurrió:

function myLevenshtein( $str1, $str2 )
{
  // prepare the words
  $words1 = explode( " ",  preg_replace( "//s+/", " ", trim($str1) ) );
  $words2 = explode( " ",  preg_replace( "//s+/", " ", trim($str2) ) );

  $found = array(); // array that keeps the best matched words so we don''t check them again
  $score = 0;       // total score
  // In my case, strings that have different amount of words can be good matches too
  // For example, Acme Company and International Acme Company Ltd. are the same thing
  // I will just add the wordcount differencre to the total score, and weigh it more later if needed
  $wordDiff = count( $words1 ) - count( $words2 );
  foreach( $words1 as $word1 )
  {
    $minlevWord = "";
    $minlev = 1000;
    $return = 0;
    foreach( $words2 as $word2 )
    {
      $return = 1;
      if( in_array( $word2, $found ) )
        continue;
      $lev = levenshtein( $word1, $word2 );
      if( $lev < $minlev )
      {
        $minlev = $lev;
        $minlevWord = $word2;
      }
    }
    if( !$return )
      break;
    $score += $minlev;
    array_push( $found, $minlevWord );
  }

  return $score + $wordDiff;
}

Answer 5

No sé en qué idioma está codificando, pero si es PHP, debe considerar los siguientes algoritmos:

levenshtein () : devuelve la cantidad mínima de caracteres que tiene que reemplazar, insertar o eliminar para transformar una cadena en otra.
soundex () : devuelve la clave soundex de cuatro caracteres de una palabra, que debe ser la misma que la de cualquier palabra que suene similar.
metaphone () : similar a soundex, y posiblemente más efectivo para ti. Es más preciso que soundex () ya que conoce las reglas básicas de pronunciación en inglés. Las teclas generadas por metafonía son de longitud variable.
similar_text () : Similar a levenshtein (), pero puede devolver un valor porcentual en su lugar.

Answer 6

Tomé SoundEx, Levenshtein, similitud PHP y doble metaphone y los empaqué en C # en un conjunto de métodos de extensión en String.

Toda la publicación del blog aquí .

Answer 7

Es posible que desee verificar el algoritmo Levenshtein Distance como punto de partida. Clasificará la "distancia" entre dos palabras.

Este hilo SO al implementar un estilo de Google "¿Quieres decir ...?" el sistema también puede proporcionar algunas ideas.