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

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

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

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

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

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

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

Ответ 1

В качестве отправной точки вы можете проверить алгоритм Levenshtein Distance. Он будет оценивать "расстояние" между двумя словами.

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

Ответ 2

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

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

Ответ 3

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

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

Ответ 4

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

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

Ответ 5

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

Вся запись в блоге здесь.

Ответ 6

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

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

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

Ответ 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;
}