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

Ответ 1

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

Ответ 2

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

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

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

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)

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

Ответ 3

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

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

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

Ответ 4

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

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

Ответ 5

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

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

Ответ 6

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

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

Ответ 7

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

Ответ 8

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

Вы можете создать какое-то значение, основанное на лексических свойствах строки. например Они бот имеют синий цвет и небо, и они находятся в одном и том же предложении и т.д. И т.д.... Но он не будет обрабатывать случаи, когда "Sky jean is blue" или какое-то другое нечетное шаровое английское строительство, которое использует те же слова, но вам нужно будет проанализировать английскую грамматику...

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

Ответ 9

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

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

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

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

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

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

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

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

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