Подобный строковый алгоритм

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

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

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

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))

Этот метод уходит корнями в теорию информации.

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

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

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

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

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

У меня была аналогичная проблема, мне нужно было получить процент символов в строке, которые были похожи. ему нужны были точные последовательности, поэтому, например, «привет, сэр» и «сэр, привет» при сравнении нужно было дать мне пять одинаковых символов, в данном случае это были бы два «привет». Затем он берет длину самой длинной из двух струн и дает мне процент от того, насколько они похожи. это код, который я придумал

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));
}

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

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

Трудность будет заключаться в семантическом сопоставлении строк.

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

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

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

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

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

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

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

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

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

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

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