Алгоритм сравнения слов - PullRequest
Новая
       40

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

14 голосов
/ 23 января 2009

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

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

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

«Акме Компани» и «Акме Компани» должны иметь очень небольшую разницу, но «Акме Компани» и «Cmea Mpnyaco» должны иметь очень большую разницу в показателях Или «Акме Компани» и «Акме Комп.» также должен иметь небольшой индекс разницы, хотя количество символов отличается. Также «Акме Компани» и «Компания Акме» должны вернуть 0.

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

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

Ответы [ 7 ]

17 голосов
/ 23 января 2009

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

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

9 голосов
/ 23 января 2009

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

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

2 голосов
/ 26 января 2009

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

Весь блог здесь .

2 голосов
/ 23 января 2009

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

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

2 голосов
/ 23 января 2009

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

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

0 голосов
/ 23 января 2009

Я реализую его на 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;
}
0 голосов
/ 23 января 2009

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

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

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

...