Аналог Строкового алгоритма
Я ищу алгоритм или, по крайней мере, теорию работы о том, как найти похожий текст в двух или более разных строках...
Очень похоже на вопрос, заданный здесь: Алгоритм поиска статей с похожим текстом, разница в том, что мои текстовые строки всегда будут состоять из нескольких слов.
Например, у меня есть строка: "В чистое голубое небо", и я сравниваю следующие две строки: "Цвет небесно-голубой" и "В голубом ясном небе".
Я ищу алгоритм, который можно использовать, чтобы сопоставить текст в двух и решить, насколько близко они совпадают. В моем случае орфография и пунктуация будут важны. Я не хочу, чтобы они влияли на способность находить настоящий текст. В приведенном выше примере, если эталон цвета хранится как "небесно-голубой", я хочу, чтобы он все еще мог совпадать. Тем не менее, 3-я строка должна быть ЛУЧШЕЕ совпадение со второй и т. Д.
Я уверен, что такие места, как Google, вероятно, используют что-то похожее с функцией "Вы имели в виду:"...
* РЕДАКТИРОВАТЬ *
Разговаривая с другом, он работал с парнем, который написал статью на эту тему. Я думал, что мог бы поделиться этим со всеми, кто читает это, так как в нем описаны некоторые действительно хорошие методы и процессы...
Вот ссылка на его статью, надеюсь, она будет полезна тем, кто читает этот вопрос, и по теме подобных строковых алгоритмов.
9 ответов
Я не могу отметить два ответа здесь, поэтому я собираюсь ответить и отметить свой собственный. Расстояние Левенштейна, по-видимому, является правильным методом в большинстве случаев для этого. Но стоит упомянуть j_random_hackers ответь также. Я использовал реализацию LZMA для проверки его теории, и это оказалось хорошим решением. В своем первоначальном вопросе я искал метод для коротких строк (от 2 до 200 символов), где будет работать алгоритм расстояния Левенштейна. Но в этом вопросе не упоминалась необходимость сравнивать две (большие) строки (в данном случае это текстовые файлы среднего размера) и выполнять быструю проверку, чтобы увидеть, насколько они похожи. Я считаю, что этот метод сжатия будет работать хорошо, но мне еще предстоит изучить его, чтобы определить, в какой момент один из них становится лучше другого с точки зрения размера данных выборки и скорости / стоимости рассматриваемой операции. Я думаю, что многие ответы на этот вопрос полезны и заслуживают упоминания для тех, кто хочет решить подобное испытание, как я здесь. Спасибо всем за ваши великолепные ответы, и я надеюсь, что они могут быть использованы и для других.
Расстояние Левенштейна не будет полностью работать, потому что вы хотите разрешить перестановки. Я думаю, что ваша лучшая ставка будет в том, чтобы найти лучшую перестановку с расстоянием Левенштейна как стоимость для каждого слова.
Чтобы найти стоимость перестановки, вроде как проблема сортировки блинов. Таким образом, вы можете переставлять каждую комбинацию слов (отфильтровывая точные совпадения), с каждой комбинацией другой строки, пытаясь свести к минимуму комбинацию расстояния перестановки и расстояния Левенштейна в каждой паре слов.
редактировать: теперь, когда у меня есть секунда, я могу опубликовать краткий пример (все "лучшие" догадки находятся на проверке и фактически не работают алгоритмы):
original strings | best rearrangement w/ lev distance per word
Into the clear blue sky | Into the c_lear blue sky
The color is sky blue | is__ the colo_r blue sky
R_dist = dist( 3 1 2 5 4 ) --> 3 1 2 *4 5* --> *2 1 3* 4 5 --> *1 2* 3 4 5 = 3
L_dist = (2D+S) + (I+D+S) (Total Subsitutions: 2, deletions: 3, insertion: 1)
(обратите внимание, что все броски включают все элементы в диапазоне, и я использую диапазоны, где Xi - Xj = +/- 1)
Другой пример
original strings | best rearrangement w/ lev distance per word
Into the clear blue sky | Into the clear blue sky
In the blue clear sky | In__ the clear blue sky
R_dist = dist( 1 2 4 3 5 ) --> 1 2 *3 4* 5 = 1
L_dist = (2D) (Total Subsitutions: 0, deletions: 2, insertion: 0)
И показать все возможные комбинации трех...
The color is sky blue | The colo_r is sky blue
In the blue clear sky | the c_lear in sky blue
R_dist = dist( 2 4 1 3 5 ) --> *2 3 1 4* 5 --> *1 3 2* 4 5 --> 1 *2 3* 4 5 = 3
L_dist = (D+I+S) + (S) (Total Subsitutions: 2, deletions: 1, insertion: 1)
В любом случае, если вы сделаете функцию стоимости, вторым выбором будет самая низкая стоимость, чего вы и ожидали!
Одним из способов определения меры "общего сходства без учета порядка" является использование некоторого расстояния на основе сжатия. В основном, как большинство алгоритмов сжатия (например, gzip) работа заключается в сканировании вдоль строки в поисках сегментов строки, которые появились ранее - каждый раз, когда такой сегмент обнаруживается, он заменяется парой (смещение, длина), идентифицирующей более ранний сегмент для использования. Вы можете использовать показатели того, насколько хорошо две строки сжимаются, чтобы обнаружить сходство между ними.
Предположим, у вас есть функция string comp(string s) который возвращает сжатую версию s, Затем вы можете использовать следующее выражение как "показатель сходства" между двумя строками s а также t:
len(comp(s)) + len(comp(t)) - len(comp(s . t))
где . принимается за конкатенацию. Идея в том, что вы измеряете, насколько дальше вы можете сжать t глядя на s первый. Если s == t, затем len(comp(s . t)) будет чуть больше, чем len(comp(s)) и вы получите высокий балл, а если они совершенно разные, len(comp(s . t)) будет очень близко len(comp(s) + comp(t)) и вы получите оценку около нуля. Промежуточные уровни сходства дают промежуточные баллы.
На самом деле следующая формула еще лучше, поскольку она симметрична (то есть оценка не меняется в зависимости от того, какая строка s и который t):
2 * (len(comp(s)) + len(comp(t))) - len(comp(s . t)) - len(comp(t . s))
Эта техника имеет свои корни в теории информации.
Преимущества: хорошие алгоритмы сжатия уже доступны, поэтому вам не нужно много писать, и они работают за линейное время (или почти), поэтому они быстры. Напротив, решения, включающие все перестановки слов, растут сверх экспоненциально по количеству слов (хотя, по общему признанию, это не может быть проблемой в вашем случае, поскольку вы говорите, что знаете, что будет только несколько слов).
Возможно, вы захотите взглянуть на алгоритмы, используемые биологами для сравнения последовательностей ДНК, поскольку они должны справляться со многими одинаковыми вещами (куски могут отсутствовать, или были вставлены, или просто перемещены в другую позицию в строке.
Алгоритм Смита-Уотермана был бы одним из примеров, который, вероятно, работал бы довольно хорошо, хотя он может быть слишком медленным для вашего использования. Мог бы дать вам отправную точку, хотя.
Одним из способов (хотя это, возможно, лучше подходит для алгоритма типа проверки орфографии) является "расстояние редактирования", т. Е. Вычисление количества изменений, необходимых для преобразования одной строки в другую. Общая техника найдена здесь:
У меня была похожая проблема, мне нужно было получить процент символов в строке, которые были похожи. ему нужны были точные последовательности, поэтому, например, "hello sir" и "sir hello" при сравнении необходимо дать мне пять одинаковых символов, в данном случае это будут два "hello". тогда он взял бы длину самой длинной из двух строк и дал бы мне процент того, насколько они похожи. это код, который я придумал
int compare(string a, string b){
return(a.size() > b.size() ? bigger(a,b) : bigger(b,a));
}
int bigger(string a, string b){
int maxcount = 0, currentcount = 0;//used to see which set of concurrent characters were biggest
for(int i = 0; i < a.size(); ++i){
for(int j = 0; j < b.size(); ++j){
if(a[i+j] == b[j]){
++currentcount;
}
else{
if(currentcount > maxcount){
maxcount = currentcount;
}//end if
currentcount = 0;
}//end else
}//end inner for loop
}//end outer for loop
return ((int)(((float)maxcount/((float)a.size()))*100));
}
Есть другой способ. Распознавание образов с использованием свертки. Изображение А проходит через преобразование Фурье. Изображение Б тоже. Теперь наложение F(A) на F(B), а затем преобразование этого обратно дает черное изображение с несколькими белыми пятнами. Эти пятна указывают, где A сильно соответствует B. Общая сумма пятен будет указывать на общее сходство. Не уверен, как вы запустите FFT на строках, но я уверен, что это сработает.
Сложность состоит в том, чтобы согласовать строки семантически.
Вы можете генерировать какое-то значение на основе лексических свойств строки. Например, у них есть синее и небесное боты, и они в одном предложении, и т. д. и т. д. Но они не будут обрабатывать случаи, когда "Жан небесный - синий", или какая-то другая странная английская конструкция, использующая те же слова, но вам нужно разобрать английскую грамматику...
Чтобы сделать что-то помимо лексического сходства, вам нужно взглянуть на обработку естественного языка, и не будет единого алгоритма, который бы решал вашу проблему.
Возможный подход:
Создайте словарь со строковым ключом "word1|word2" для всех комбинаций слов в ссылочной строке. Одна комбинация может встречаться несколько раз, поэтому значением словаря должен быть список чисел, каждое из которых представляет расстояние между словами в строке ссылки.
Когда вы сделаете это, здесь будет дублирование: для каждой записи словаря "word1|word2" будет запись "word2|word1" с тем же списком значений расстояний, но с отрицанием.
Для каждой комбинации слов в строке сравнения (слова 1 и 2, слова 1 и 3, слова 2 и 3 и т. Д.) Проверьте две клавиши (word1|word2 и word2|word1) в строке ссылки и найдите ближайший значение расстояния в текущей строке. Добавьте абсолютное значение разницы между текущим расстоянием и ближайшим расстоянием до счетчика.
Если ближайшее ссылочное расстояние между словами находится в противоположном направлении (word2|word1) в качестве строки сравнения, вы можете захотеть навесить его меньше, чем если бы ближайшее значение было в одном и том же направлении в обеих строках.
Когда вы закончите, разделите сумму на квадрат числа слов в строке сравнения.
Это должно обеспечить некоторое десятичное значение, представляющее, насколько близко каждое слово / фраза соответствует некоторому слову / фразе в исходной строке.
Конечно, если исходная строка длиннее, это не будет учитываться, поэтому может потребоваться вычислить эти оба направления (используя одно в качестве ориентира, а затем другое) и усреднить их.
У меня нет абсолютно никакого кода для этого, и я, вероятно, только что изобрел очень грубое колесо. YMMV.