Алгоритмы сходства строк?

Question

Мне нужно сравнить 2 строки и вычислить их сходство, чтобы отфильтровать список наиболее похожих строк.

Например.поиск "собака" вернул бы

1. собака
2. собачья
3. болото
4. туман
5. туман

Например.поиск "крэка" вернул бы

1. крэк
2. wisecrack
3. стойку
4. домкрат
5. кряк

Я сталкивался:

• QuickSilver
• LiquidMetal

Знаете ли выеще каких-либо алгоритмов подобия строк?

Answer 1

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

Answer 2

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

Answer 3

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

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

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

• Создайте три со списком слов, имеявсе буквы, проиндексированные спереди и сзади (см. пример ниже)
• Для поиска 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., и вы найдете машину (вы также нашли бы все, начиная с car , но также и что-либо с автомобилем внутри - это не в примере - но викарий , например, был бы найден из c > i > v < a < R).

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

ищет car,

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

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

Answer 4

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

Answer 5

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

<b>Foreach</b> <i>string</i> <b>in</b> <i>haystack</i> <b>Do</b>
    <i>offset</i> := -1;
    <i>matchedCharacters</i> := 0;
    <b>Foreach</b> <i>char</i> <b>in</b> <i>needle</i> <b>Do</b>
        <i>offset</i> := PositionInString(<i>string</i>, <i>char</i>, <i>offset</i>+1);
        <b>If</b> <i>offset</i> = -1 <b>Then</b>
            <b>Break</b>;
        <b>End</b>;
        <i>matchedCharacters</i> := <i>matchedCharacters</i> + 1;
    <b>End</b>;
    <b>If</b> <i>matchedCharacters</i> > 0 <b>Then</b>
       // (partial) match found
    <b>End</b>;
<b>End</b>;

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