Algoritmo de comparación de palabras

Question

Estoy haciendo una herramienta de importación CSV para el proyecto en el que estoy trabajando. El cliente debe poder ingresar los datos en Excel, exportarlos como CSV y subirlos 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 aumenta a medida que las cadenas se vuelven más diferentes, pero strcmp no lo corta aquí porque:

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

Entonces, si el cliente escribe un tipo mientras ingresa datos, podría pedirle que elija el nombre que probablemente desea insertar.

¿Existe un algoritmo conocido para hacer esto, o tal vez podamos inventar uno :) ?

Answer 1

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

Este hilo SO sobre la implementación de un estilo de Google "¿Quieres decir ...?" el sistema también puede proporcionar algunas ideas.

Answer 2

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

levenshtein () : Devuelve el número mínimo de caracteres que debe reemplazar, insertar o eliminar para transformar una cadena en otra.
soundex () : Devuelve el cuatro- clave de sonido 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 la pronunciación en inglés. Las teclas generadas por el megáfono son de longitud variable.
similar_text () : similar a levenshtein (), pero puede devolver un valor porcentual en su lugar.

Answer 3

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

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

Answer 4

Realmente he implementado un sistema similar. Utilicé la distancia de Levenshtein (como otros carteles ya sugirieron), 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". coincidirá mal con "Digital Incorporated World Company Acme" y tales reordenamientos fueron bastante comunes en mis datos.

Lo modifiqué para que si la distancia de edición de cadenas enteras fuera demasiado grande, el algoritmo recurriera a palabras coincidentes entre sí para encontrar una buena coincidencia de palabra a palabra (costo cuadrático, pero había un límite si existía eran demasiadas palabras, así que funcionó bien).

Answer 5

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

Publicación de blog completa aquí .

Answer 6

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

Si se trata solo 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 7

Lo estoy implementando en PHP, y ahora estoy escribiendo un 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 acepto el baja posibles valores. Lo publicaré cuando termine.

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;
}