Строковое сходство → Левенштейн расстояние

Ответ 1

Я бы разделил этот термин на униграммы, битрамы и триграммы, затем вычислил сходство косинусов.

Ответ 2

Я думаю, что это можно легко решить, используя алгоритм Longest Common Substring/Subsequence на одной из строк (например, "conair" ), а другая строка добавлена ​​к себе один раз (например, "aircon" → "airconaircon" ).

Пример кода в C:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// Returns the length of the longest common substring (LCS)
// between two given strings.
//
// This recursive implementation can be replaced by a
// more performant dynamic programming implementation.
size_t llcs(const char* s1, const char* s2)
{
  size_t len[3];

  if (*s1 == '\0' || *s2 == '\0') return 0;

  len[0] = (*s1 == *s2) + llcs(s1 + 1, s2 + 1);
  len[1] = llcs(s1 + 1, s2);
  len[2] = llcs(s1, s2 + 1);

  if (len[0] < len[1]) len[0] = len[1];
  if (len[0] < len[2]) len[0] = len[2];

  return len[0];
}

// Returns similarity of two given strings in the range
// from 0.0 to 1.0 (1.0 for equal strings).
double similarity(const char* s1, const char* s2)
{
  size_t s1len = strlen(s1);
  size_t s2len = strlen(s2);
  double sim;

  if (s1len == 0 && s2len == 0)
  {
    // Two empty strings are equal
    sim = 1;
  }
  else
  {
    size_t len;
    // Append s1 to itself in s1s1 (e.g. "aircon" -> "airconaircon")
    char* s1s1 = malloc(s1len * 2 + 1);
    strcpy(s1s1, s1);
    strcpy(s1s1 + s1len, s1);

    // Find the length of the LCS between s1s1 and s2
    // (e.g. between "airconaircon" and "conair")
    len = llcs(s1s1, s2);
    // We need it not longer than s1 (e.g. "aircon")
    // since we're actually comparing s1 and s2
    if (len > s1len) len = s1len;

    len *= 2;

    // Prevent 100% similarity between a string and its
    // cyclically shifted version (e.g. "aircon" and "conair")
    if (len == s1len + s2len && strcmp(s1, s2) != 0) len--;

    // Get the final measure of the similarity
    sim = (double)len / (s1len + s2len);

    free(s1s1);
  }

  return sim;
}

int main(int argc, char** argv)
{
  if (argc == 3)
    printf("Similarity of \"%s\" and \"%s\" is %.2f%%\n",
           argv[1], argv[2], 100 * similarity(argv[1], argv[2]));
  else
    printf("Usage:\n  %s string1 string2\n",
           argv[0]);
  return 0;
}

Пример вывода:

Similarity of "123" and "123" is 100.00%
Similarity of "123" and "1234" is 85.71%
Similarity of "0123" and "123" is 85.71%
Similarity of "a" and "aa" is 66.67%
Similarity of "aa" and "a" is 66.67%
Similarity of "aaaaaaa" and "aaaaaa" is 92.31%
Similarity of "aaaaaa" and "aaaaaaa" is 92.31%
Similarity of "aircon" and "conair" is 91.67%
Similarity of "spit" and "pits" is 87.50%
Similarity of "pits" and "spit" is 87.50%
Similarity of "spits" and "pits" is 88.89%
Similarity of "pits" and "spits" is 88.89%

Ответ 3

Похоже, вы можете попытаться сделать расстояние Левенштейна с помощью слогов или фонем вместо букв.

Ответ 4

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

Сходство строк можно также найти с помощью метода Longest Common Subsequence, а затем вы можете увидеть Левенштейна на остальной части непревзойденного.

Если вы хотите сделать кластерный подход, следующий ответ, похоже, содержит некоторые детали, но, очевидно, его сложнее реализовать.

Ответ 5

Сортировка слов и поиск Левенштейна дадут 100% -ное соответствие для вашего примера, но оно также даст 100% -ное соответствие, например,

CONAIR
RCIAON

который может быть не таким, каким вы хотите.

Другим способом определения подобия будет поиск общих подстрок для 2 строк. Вы можете создать Дерево суффикса и узнать все распространенные подстроки и попытаться определить, насколько они похожи. Так что для вашего, например, дерево суффикса даст общие подстроки, такие как CON и AIR, который охватывает все слово (для ваших 2 строк) и таким образом завершает их как похожие.

Ответ 6

Взгляните на алгоритмы Needleman-Wunsch или Smith-Waterman. Они используются для обработки соответствия строк с помощью адаптированного расстояния редактирования для последовательностей ДНК, где могут возникать любые вставки, развороты, транспозоны на любую длину в любом месте. Говоря это, мне нужно добавить, что для достаточно длинной строки нет оптимального решения. И не забывайте, что стоимость редактирования зависит от контекста использования алгоритма (проблема семантики), в то время как любой алгоритм всегда является синтаксической машиной.

Ответ 7

попробуйте использовать другие методы сходства, такие как sorenson, jaccard и jaro_winkler

лично я являюсь огромным поклонником jaro winkler, так как он многократно выполнял мою цель.

from Levenshtein import jaro_winkler
In [2]: jaro_winkler("conair","aircon")
Out[2]: 0.8333333333333334