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 disco CSV:

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

Por supuesto, las empresas se mantienen en una tabla independiente y vinculada con una clave externa, por lo que necesitan para descubrir la correcta identificación de la compañía antes de insertar. 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ía 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.

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

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

Answer 1

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

This SO thread en la implementación de un estilo de Google "¿Quiere decir ...?" el sistema también puede proporcionar algunas ideas.

Answer 2

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

¿En qué idioma está implementando esto? es posible que podamos señalar ejemplos específicos

Answer 3

Existen 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 4

No sé qué idioma está en la codificación, pero si es PHP, usted debe considerar los siguientes algoritmos:

levenshtein(): Devuelve el número mínimo de caracteres que tiene que reemplazar , inserte o elimine para transformar una cadena en otra.
soundex(): Devuelve la clave soundex de cuatro caracteres de una palabra, que debe ser la misma que la clave para cualquier palabra similar.
metaphone(): Similar a soundex, y posiblemente más efectivo para usted. 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 5

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 cadenas 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 corte si había demasiadas palabras, así que funcionó bien).

Answer 6

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 utilizando levenshtein y aceptar los valores posibles lowes. Lo publicaré cuando haya terminado.

Muchas gracias.

Actualización: Esto es lo que he llegado con:

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 7

que he tomado SoundEx, Levenshtein, similitud PHP, y el doble metaphone y les empaquetada en C# en un conjunto de métodos de extensión en cadena .

Entire blog post here.