Я использую инструмент 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.
Итак, если клиент вводит тип при вводе данных, я могу предложить ему выбрать имя, которое он, скорее всего, захочет вставить.
Есть ли известный алгоритм для этого, или, может быть, мы можем его выдумать:)
В качестве отправной точки вы можете проверить алгоритм Levenshtein Distance. Он будет оценивать "расстояние" между двумя словами.
Этот поток SO по внедрению стиля Google "Вы имеете в виду...?" система может также предоставить некоторые идеи.
Я не знаю, на каком языке вы кодируетесь, но если это PHP, вы должны учитывать следующие алгоритмы:
levenshtein(): возвращает минимальное количество символов, которые вы должны заменить, вставить или удалить, чтобы преобразовать один строка в другую.
soundex(): возвращает четырехзначную звуковую клавишу слова, которая должна быть такой же, как клавиша для любое подобное звучание.
metaphone(): похоже на soundex и, возможно, более эффективен для вас. Это более точно, чем soundex(), поскольку он знает основные правила английского произношения. Генерируемые метафоном ключи имеют переменную длину.
Similar_text(): Подобно levenshtein(), но вместо этого он может возвращать процентное значение.
У меня был некоторый успех с алгоритмом Levenshtein Distance, есть также Soundex.
На каком языке вы это реализуете? мы можем указать на конкретные примеры
Я действительно реализовал подобную систему. Я использовал расстояние Левенштейна (как и другие предложенные плакаты) с некоторыми изменениями. Проблема с немодифицированным расстоянием редактирования (применяется ко всем строкам) заключается в том, что он чувствителен к переупорядочению слов, поэтому "Acme Digital Incorporated World Company" плохо будет соответствовать "Digital Incorporated World Company Acme", и такие переупорядочивания были довольно распространены в моих данных.
Я изменил его так, чтобы, если расстояние редактирования целых строк было слишком велико, алгоритм отпал к совпадению слов друг с другом, чтобы найти хорошее совпадение слов (квадратичная стоимость, но было обрезание, если было слишком много слов, поэтому он работал нормально).
Я взял SoundEx, Levenshtein, сходство PHP и двойной метафон и упаковал их в С# в одном наборе методов расширения на String.
Существует несколько алгоритмов для этого, и большинство баз данных даже по умолчанию имеют один. На самом деле это довольно общая проблема.
Если речь идет только о английских словах, SQL Server, например, включает SOUNDEX, который можно использовать для сравнения полученного результирующего звука слова.
http://msdn.microsoft.com/en-us/library/aa259235%28SQL.80%29.aspx
Я реализую его в 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;
}