Алгоритмы подобия строк?

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

Вы можете сделать это:

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 вы можете определить «степень» совпадения. Если она равна длине иглы, все символы в игле также находятся в строке. Если вы также сохраняете смещение первого совпадающего символа, вы также можете отсортировать результат по «плотности» совпадающих символов, вычитая смещение первого совпавшего символа из смещения последнего совпавшего символа смещение. ]; чем меньше разница, тем плотнее совпадение.

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

Пожалуйста, перейдите по ссылке в Википедии выше. Tries — самый быстрый метод сортировки слов (n слов, поиск s, O(n) для создания дерева, O(1 ) для поиска s (или, если хотите, если a — это средняя длина, O(an) для дерева и O(s) для поиска)).

Быстрая и простая реализация (подлежит оптимизации) вашей задачи (похожие слова) состоит из

• Создания trie со списком слов, где все буквы пронумерованы спереди и сзади (см. пример ниже)
• Чтобы найти s, выполните итерацию от s[0] , чтобы найти слово в дереве, затем s[1] и т. д...
• В дереве , если количество найденных букв равно len(s)-k выводится слово, где k — допуск (пропущена 1 буква, 2.. .).
• Алгоритм может быть распространен на слова в списке (см. ниже)

Например, со словами 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

Строго ища автомобиль, дерево дает вам доступ из 1., и вы находите автомобиль (вы бы также нашли все, что начинается с автомобиль, но также что-либо с автомобилем внутри - этого нет в примере - но, например, vicar можно было бы найти из c > i > v < a < R).

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

ищем car,

• c: поиск в дереве c < a и c < r (отсутствует буква в s). Чтобы принять неправильную букву в слове w, попробуйте перепрыгнуть на каждой итерации неправильную букву, чтобы увидеть, не отстает ли ar, это O(w) . С двумя буквами, O(w²) и т. д.но к дереву можно добавить еще один уровень индекса, чтобы учесть переход по буквам, что сделает дерево сложным и жадным в отношении памяти.
• a, затем r: то же самое, что и выше, но также поиск в обратном направлении

Это просто для того, чтобы дать представление о принципе — в приведенном выше примере могут быть некоторые глюки (I' завтра еще раз проверю).