Algorithme de comparaison de mots

Question

Je suis en train de créer un outil d'importation CSV pour le projet sur lequel je travaille. Le client doit pouvoir saisir les données dans Excel, les exporter au format CSV et les télécharger dans la base de données. Par exemple, j'ai cet enregistrement CSV:

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

Bien sûr, les sociétés sont conservées dans une table séparée et liées à une clé étrangère. Je dois donc trouver le bon identifiant de société avant de l'insérer. Je prévois de le faire en comparant les noms de société dans la base de données avec les noms de société dans le fichier CSV. la comparaison doit renvoyer 0 si les chaînes sont exactement les mêmes et renvoyer une valeur qui grossit à mesure que les chaînes se différencient, mais strcmp ne la coupe pas ici car:

" Acme Company " et "Acme Comapny". devrait avoir un très petit indice de différence, mais "Acme Company" et "Cmea Mpnyaco". devrait avoir un très grand indice de différence Ou "Acme Company" et "Acme Comp." devrait également avoir un petit indice de différence, même si le nombre de caractères est différent. En outre, "Acme Company". et " Company Acme " devrait renvoyer 0.

Ainsi, si le client crée un type lors de la saisie des données, je peux lui demander de choisir le nom qu'il souhaite probablement insérer.

Existe-t-il un algorithme connu pour le faire, ou peut-être pourrions-nous en inventer un :) ?

Answer 1

Vous voudrez peut-être consulter l'algorithme Distance de Levenshtein . Il évaluera la " distance " entre deux mots.

Ce fil SO sur la mise en œuvre d'un style Google "Voulez-vous dire ...?" Le système peut également fournir des idées.

Answer 2

Je ne sais pas dans quelle langue vous codez, mais s'il s'agit de PHP, vous devriez envisager les algorithmes suivants:

levenshtein () : renvoie le nombre minimal de caractères requis. remplacer, insérer ou supprimer pour transformer une chaîne en une autre.
soundex () : renvoie le nombre de quatre Caractère soundex d'un mot, qui doit être identique à celui de tout mot similaire.
metaphone () : similaire à soundex, et peut-être plus efficace pour vous. C'est plus précis que soundex () car il connaît les règles de base de la prononciation anglaise. Les clés générées par le métaphone sont de longueur variable.
similar_text () : similaire à levenshtein (), mais il peut renvoyer une valeur en pourcentage.

Answer 3

L’algorithme Levenshtein Distance a connu un certain succès. Il existe également Soundex .

Dans quelle langue implémentez-vous cela? nous pourrons peut-être citer des exemples spécifiques

Answer 4

J'ai en fait mis en place un système similaire. J'ai utilisé la distance de Levenshtein (comme d'autres affiches l'ont déjà suggéré), avec quelques modifications. Le problème de la distance de modification non modifiée (appliquée à des chaînes entières) est qu’elle est sensible à la réorganisation des mots, donc "Acme Digital Incorporated World Company". correspondra mal contre "Acme", société de la société Digital Incorporated World. et de telles réorganisations étaient assez courantes dans mes données.

Je l'ai modifié de manière à ce que, si la distance d'édition de chaînes entières soit trop grande, l'algorithme utilise des mots identiques les uns contre les autres pour trouver une correspondance parfaite mot à mot (coût quadratique, mais il Il y avait trop de mots, donc ça a marché).

Answer 5

J'ai pris SoundEx, Levenshtein, la similarité PHP et le double métaphone et je les ai empaquetés en C # dans un ensemble de méthodes d'extension sur String.

Tout l'article de blog ici .

Answer 6

Il existe plusieurs algorithmes pour le faire, et la plupart des bases de données en incluent même un par défaut. C'est en fait une préoccupation assez commune.

S'il ne s'agit que de mots anglais, SQL Server, par exemple, inclut SOUNDEX, qui peut être utilisé pour comparer le son résultant du mot.

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

Answer 7

Je l'implémente en PHP, et j'écris maintenant un morceau de code qui va diviser 2 chaînes de mots et comparer chacun des mots de la première chaîne avec les mots de la deuxième chaîne en utilisant levenshtein et accepter le lowes valeurs possibles. Je vais le poster quand j'aurai fini.

Merci beaucoup.

Mise à jour: Voici ce que j'ai proposé:

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