Строковые алгоритмы подобия?

Ответ 1

Кажется, вам нужно какое-то нечеткое совпадение. Вот java-реализация некоторого набора показателей подобия http://www.dcs.shef.ac.uk/~sam/stringmetrics.html. Вот подробное объяснение строковых метрик http://www.cs.cmu.edu/~wcohen/postscript/ijcai-ws-2003.pdf, это зависит от того, насколько нечеткой и насколько быстро ваша реализация должна быть.

Ответ 2

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

Ответ 3

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

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

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

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

Пример: со словами car, vars.

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

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

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

ищет car,

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

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

Ответ 4

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

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;

С помощью сопоставленных символов вы можете определить "степень" матча. Если он равен длине иглы, все символы в игле также находятся в строке. Если вы также сохраняете смещение первого совпадающего символа, вы также можете сортировать результат по "плотности" совпадающих символов путем вычитания смещения первого совпадающего символа из смещения последнего совпадающего смещения символа; чем ниже разница, тем плотное совпадение.

Ответ 5

class Program
{ 

static 
 int ComputeLevenshteinDistance(string source, string target){
if ((source == null) || (target == null)) return 0;
if ((source.Length == 0) || (target.Length == 0)) return 0;
if (source == target) return source.Length;

int sourceWordCount = source.Length;
int targetWordCount = target.Length;

int[,] distance = new int[sourceWordCount + 1, targetWordCount + 1];

// Step 2
for (int i = 0; i <= sourceWordCount; distance[i, 0] = i++);
for (int j = 0; j <= targetWordCount; distance[0, j] = j++);

for (int i = 1; i <= sourceWordCount; i++)
{
    for (int j = 1; j <= targetWordCount; j++)
    {
        // Step 3
        int cost = (target[j - 1] == source[i - 1]) ? 0 : 1;

        // Step 4
        distance[i, j] = Math.Min(Math.Min(distance[i - 1, j] + 1, distance[i, j - 1] + 1), distance[i - 1, j - 1] + cost);
    }
}

return distance[sourceWordCount, targetWordCount]; 
}

 static void Main(string[] args){ Console.WriteLine(ComputeLevenshteinDistance ("Stackoverflow","StuckOverflow"));
Console.ReadKey();
}
}