Алгоритм сравнения слов

Question

Я делаю инструмент импорта CSV для проекта, над которым я работаю. Клиент должен иметь возможность вводить данные в Excel, экспортировать их в формате CSV и загружать их в базу данных. Например, у меня есть эта запись CSV:

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

Конечно, компании хранятся в отдельной таблице и связаны с внешним ключом, поэтому мне нужно найти правильный идентификатор компании перед вставкой. Я планирую сделать это путем сравнения названий компаний в базе данных с названиями компаний в CSV. сравнение должно возвращать 0, если строки в точности совпадают, и возвращать какое-то значение, которое увеличивается по мере того, как строки становятся более разными, но strcmp здесь не обрезает это, потому что:

" Acme Company " и " Acme Comapny " должен иметь очень маленький индекс разницы, но " компания Acme " и " Cmea Mpnyaco " должен иметь очень большой индекс разницы Или & Quot; Acme Company & Quot; и " Acme Comp. " также должен иметь небольшой индекс разницы, хотя количество символов отличается. Кроме того, & Quot; Acme Company & Quot; и " Company Acme " должен вернуть 0.

Поэтому, если клиент вводит тип при вводе данных, я мог бы предложить ему выбрать имя, которое он, скорее всего, хотел бы вставить.

Есть ли известный алгоритм для этого или, может быть, мы можем его изобрести :)

Answer 1

Возможно, вы захотите проверить алгоритм Левенштейновского расстояния в качестве отправной точки. Будет оцениваться & Quot; расстояние & Quot; между двумя словами.

Этот поток SO о реализации стиля Google " Вы имеете в виду ...? " Система может также предоставить некоторые идеи.

Answer 2

Я не знаю, на каком языке вы кодируете, но если это PHP, вы должны рассмотреть следующие алгоритмы:

levenshtein () . Возвращает минимальное количество символов, которое необходимо заменить, вставить или удалить, чтобы преобразовать одну строку в другую.
soundex () . Возвращает четыре символ soundex ключ слова, который должен совпадать с ключом для любого похожего слова.
metaphone () : аналогично soundex, и, возможно, более эффективным для вас. Это более точно, чем soundex (), поскольку оно знает основные правила английского произношения. Ключи, сгенерированные метафоном, имеют переменную длину.
Similar_text () : аналогично levenshtein (), но вместо этого он может возвращать процентное значение.

Answer 3

У меня был некоторый успех с Левенштейновским расстоянием , также есть Soundex .

На каком языке вы это реализуете? мы можем указать конкретные примеры

Answer 4

Я фактически внедрил подобную систему. Я использовал расстояние Левенштейна (как уже предлагали другие постеры) с некоторыми изменениями. Проблема с неизмененным расстоянием редактирования (применительно к целым строкам) заключается в том, что он чувствителен к переупорядочению слов, поэтому & Quot; Acme Digital Incorporated World Company & Quot; будет плохо совпадать с " Digital Incorporated World Company Acme " и такие изменения были довольно распространены в моих данных.

Я изменил его так, чтобы, если расстояние редактирования целых строк было слишком большим, алгоритм прибегал к сопоставлению слов друг с другом, чтобы найти хорошее совпадение слов (квадратичная стоимость, но при наличии было слишком много слов, поэтому все работало нормально).

Answer 5

Я взял SoundEx, Levenshtein, PHP-подобие и двойной метафон и упаковал их в C # в один набор методов расширения для String.

Весь пост здесь .

Answer 6

Для этого есть несколько алгоритмов, и большинство баз данных даже включают один по умолчанию. На самом деле это довольно распространенная проблема.

Если речь идет только об английских словах, SQL Server, например, включает SOUNDEX, который можно использовать для сравнения полученного звучания слова.

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

Answer 7

Я реализую это на PHP, и сейчас я пишу фрагмент кода, который разбивает 2 строки на слова и сравнивает каждое из слов первой строки со словами второй строки, используя levenshtein, и принимает понижает возможные значения. Я опубликую это, когда я закончу.

Большое спасибо.

Обновление: вот что я придумала:

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