Мне нужно сравнить 2 строки и вычислить их сходство, чтобы отфильтровать список наиболее похожих строк.
Например. поиск "собака" вернет
Например. поиск "трещины" вернет
Я наткнулся на:
Знаете ли вы еще какие-нибудь алгоритмы подобия строк?
Похоже, вам нужно какое-то нечеткое соответствие. Вот реализация на Java некоторого набора показателей сходства http://web.archive.org/web/20081224234350/http://www.dcs.shef.ac.uk/~sam/stringmetrics.html. Вот более подробное объяснение строковых показателей http://www.cs.cmu.edu/~wcohen/postscript/ijcai-ws-2003.pdf это зависит от того, насколько нечеткой и быстрой должна быть ваша реализация.
Я бы порекомендовал расстояние Левенштейна. Он вычисляет минимальное количество операций, которые необходимо выполнить, чтобы преобразовать одну строку в другую. Меньшее количество изменений означает, что струны более похожи ...
Если основное внимание уделяется производительности, я бы реализовал алгоритм, основанный на структуре trie
(хорошо работает, чтобы найти слова в тексте или помочь исправить слово, но в вашем случае вы можете быстро найти все слова, содержащие данное слово, или, например, все, кроме одной буквы).
Сначала перейдите по ссылке в Википедии выше .Tries - это самый быстрый метод сортировки слов (n слов, поиск s, O (n) для создания trie, O (1) для поиска s (или, если вы предпочитаете, если a - средняя длина, O (an) для дерева и O (s) для поиска)).
Быстрая и простая реализация (для оптимизации) вашей проблемы (похожие слова) состоит из
Например, со словами car, vars.
Построение дерева (большая буква означает, что слово здесь заканчивается, а другая может продолжаться). > - это постиндекс (переход вперед), а < - предварительный индекс (переход назад). В другом примере нам, возможно, придется указать также начальную букву, она здесь не представлена для ясности.
Например, < и > в C ++ будут Mystruct *previous,*next, то есть от a > c < r, вы можете перейти непосредственно от a к c, и наоборот, также с a на R.
1. c < a < R
2. a > c < R
3. > v < r < S
4. R > a > c
5. > v < S
6. v < a < r < S
7. S > r > a > v
Если искать строго car, дерево дает вам доступ с 1., и вы найдете car (вы бы также нашли все, что начинается с car, но также что-нибудь с автомобилем внутри - этого нет в примере - но, например, vicar можно было бы найти в c > i > v < a < R).
Чтобы выполнить поиск с допуском неправильной / отсутствующей 1 буквы, вы выполняете итерацию от каждой буквы s и подсчитываете количество последовательных - или пропуская 1 букву - букв, которые вы получаете от s < / em> в дереве.
ищу car,
c: поиск в дереве файлов c < a и c < r (пропущенная буква в s). Чтобы принять неправильную букву в слове w, попробуйте на каждой итерации перескакивать на неправильную букву, чтобы увидеть, не отстает ли ar, это O (w). С двумя буквами, O (w ²) и т. Д., Но к дереву можно добавить еще один уровень индекса, чтобы учесть переход по буквам, в результате чего дерево сложный и жадный в отношении памяти.a, затем r: то же, что и выше, но также поиск в обратном направленииЭто просто для того, чтобы дать представление о принципе - в приведенном выше примере могут быть некоторые сбои (завтра я еще раз проверю).
Вы могли сделать это:
Foreach string in haystack Do
offset := -1;
matchedCharacters := 0;
Foreach char in needle Do
offset := PositionInString(string, char, offset+1);
If offset = -1 Then
Break;
End;
matchedCharacters := matchedCharacters + 1;
End;
If matchedCharacters > 0 Then
// (partial) match found
End;
End;
С помощью matchedCharacters вы можете определить «степень» соответствия. Если он равен длине иглы, все символы в игле также находятся в строке. Если вы также сохраняете смещение первого сопоставленного символа, вы также можете отсортировать результат по «плотности» сопоставленных символов, вычитая смещение первого сопоставленного символа из смещения последнего сопоставленного символа смещение ; чем меньше разница, тем плотнее совпадение.
PositionInString?
- person Moritz Schmitz v. Hülst; 16.06.2015
PositionInString - это функция, которая возвращает позицию индекса char в string, начиная с offset.
- person Gumbo; 16.06.2015
algorithm. Вот несколько ссылок: - person j_random_hacker schedule 01.09.2010