Аналог Строкового алгоритма

Question

Я ищу алгоритм или, по крайней мере, теорию работы о том, как найти похожий текст в двух или более разных строках ...

Очень похоже на вопрос, заданный здесь: Алгоритм поиска статей с похожим текстом , разница в том, что в моих текстовых строках будет всего несколько слов.

Как сказать, у меня есть строка: "В чистое голубое небо" и я делаю сравнение со следующими двумя строками: «Цвет небесно-голубой» и "В голубом ясном небе"

Я ищу алгоритм, который можно использовать, чтобы сопоставить текст в двух и решить, насколько близко они совпадают. В моем случае орфография и пунктуация будут важны. Я не хочу, чтобы они влияли на способность находить настоящий текст. В приведенном выше примере, если эталон цвета хранится как «небесно-голубой», я хочу, чтобы он все еще мог совпадать. Однако указанная третья строка должна соответствовать ЛУЧШЕМУ варианту второй и т. Д.

Я уверен, что в таких местах, как Google, возможно, используется что-то похожее с функцией "Вы имели в виду:" ...

* РЕДАКТИРОВАТЬ *
Разговаривая с другом, он работал с парнем, который написал статью на эту тему. Я подумал, что мог бы поделиться этим со всеми, кто читает это, поскольку в нем описаны действительно хорошие методы и процессы ...

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

Answer 1

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

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

редактирование: Теперь, когда у меня есть секунда, я могу опубликовать краткий пример (все «лучшие» догадки находятся на проверке и фактически не работают с алгоритмами):

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)

В любом случае, если вы сделаете функцию стоимости, вторым выбором будет минимальная стоимость, как вы и ожидали!

Answer 2

Один из способов определения меры «общего сходства без учета порядка» состоит в использовании некоторого вида расстояния на основе сжатия . По сути, большинство алгоритмов сжатия (например, 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))

Эта техника имеет свои корни в теории информации.

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

Answer 3

Возможно, вы захотите взглянуть на алгоритмы, используемые биологами для сравнения последовательностей ДНК, поскольку они должны справляться со многими одинаковыми вещами (куски могут отсутствовать, или были вставлены, или просто перемещены в другую позицию в строка.

Алгоритм Смита-Уотермана будет одним из примеров, который, вероятно, будет работать довольно хорошо, хотя он может быть слишком медленным для вашего использования. Мог бы дать вам отправную точку, хотя.

Answer 4

Одним из способов (хотя это, возможно, лучше подходит для алгоритма типа проверки орфографии) является «расстояние редактирования», т. Е. Вычисление количества изменений, необходимых для преобразования одной строки в другую. Общая техника найдена здесь:

http://en.wikipedia.org/wiki/Levenshtein_distance

Answer 5

У меня была похожая проблема, мне нужно было получить процент символов в строке, которые были похожи. ему нужны были точные последовательности, поэтому, например, «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));
}

Answer 6

Я не могу отметить два ответа здесь, поэтому я собираюсь ответить и отметить свой собственный. Расстояние Левенштейна, по-видимому, является правильным методом в большинстве случаев для этого. Но стоит упомянуть и ответ j_random_hackers. Я использовал реализацию LZMA, чтобы проверить его теорию, и она оказалась разумным решением. В своем первоначальном вопросе я искал метод для коротких строк (от 2 до 200 символов), где будет работать алгоритм расстояния Левенштейна. Но в этом вопросе не упоминалась необходимость сравнивать две (большие) строки (в данном случае это текстовые файлы среднего размера) и выполнять быструю проверку, чтобы увидеть, насколько они похожи. Я считаю, что этот метод сжатия будет работать хорошо, но мне еще предстоит изучить его, чтобы определить, в какой момент один из них становится лучше другого с точки зрения размера данных выборки и скорости / стоимости рассматриваемой операции. Я думаю, что многие ответы на этот вопрос полезны и заслуживают упоминания для тех, кто хочет решить подобное испытание, как я здесь. Спасибо всем за ваши великолепные ответы, и я надеюсь, что они могут быть использованы и для других.

Answer 7

Есть другой способ. Распознавание образов с использованием свертки. Изображение А проходит через преобразование Фурье. Изображение Б тоже. Теперь наложение F (A) на F (B), а затем преобразование обратно дает черное изображение с несколькими белыми пятнами. Эти пятна указывают, где A сильно соответствует B. Общая сумма пятен будет указывать на общее сходство. Не уверен, как бы вы запустили FFT для строк, но я уверен, что это сработает.

Answer 8

Сложность заключается в семантическом сопоставлении строк.

Вы можете сгенерировать какое-то значение на основе лексических свойств строки. например У них есть синий цвет и небо, и они в одном предложении, и т. Д. И т. Д. Но он не будет обрабатывать случаи, когда «Жан небесный - синий», или какая-то другая странная английская конструкция, использующая те же слова, вам нужно разобрать грамматику английского ...

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

Answer 9

Возможный подход:

Создайте словарь со строковым ключом «word1 | word2» для всех комбинаций слов в строке reference . Одна комбинация может встречаться несколько раз, поэтому значение словаря должно представлять собой список чисел, каждое из которых представляет расстояние между словами в строке ссылки.

Когда вы это сделаете, здесь будет дублирование: для каждой словарной статьи «word1 | word2» будет словарная «word2 | word1» с тем же списком значений расстояний, но с отрицанием.

Для каждой комбинации слов в строке сравнения (слова 1 и 2, слова 1 и 3, слова 2 и 3 и т. Д.) Проверьте две клавиши (word1 | word2 и word2 | word1) ) в справочной строке и найдите ближайшее значение расстояния в текущей строке. Добавьте абсолютное значение разницы между текущим расстоянием и ближайшим расстоянием к счетчику.

Если ближайшее опорное расстояние между словами в противоположном направлении (word2 | word1) в качестве строки сравнения, вы можете нагрузить его меньше, чем если бы ближе значение было в том же направлении, в обеих строках.

Когда вы закончите, разделите сумму на квадрат числа слов в строке сравнения.

Это должно обеспечить некоторое десятичное значение, представляющее, насколько близко каждое слово / фраза соответствует некоторому слову / фразе в исходной строке.

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

У меня нет абсолютно никакого кода для этого, и я, вероятно, только что изобрел очень грубое колесо. YMMV.