Процентный рейтинг совпадений с использованием сопоставления расстояний Левенштейна

У меня была аналогичная проблема, и эта ветка помогла мне найти решение. Надеюсь, это поможет и другим.

int levDis = Lev_distance(Q, Mi)
int bigger = max(strlen(Q), strlen(Mi))
double pct = (bigger - levDis) / bigger

Он должен возвращать 100%, если обе строки абсолютно одинаковы, и 0%, если они совершенно разные.

(извините, если мой английский не так хорош)

Мой подход к этой проблеме заключался в вычислении максимально разрешенных операций, что и есть расстояние Левенштейна. Я использовал следующую формулу:

percent = 0.75; // at least 75% of string must match
maxOperationsFirst = s1.length() - s1.length() * percent;
maxOperationsSecond = s2.length() - s2.length() * percent;
maxOperations = round(min(maxOperationsFirst, maxOperationsSecond));

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

Когда у вас есть максимальное количество операций, вы можете сравнить его с результатом levenshtein и определить, подходит ли строка. Таким образом, вы можете использовать любые расширенные методы Левенштейна, например, Расстояние Дамерау – Левенштейна, которые учитывают орфографические ошибки, например test -> tset, только как 1 операция, что весьма полезно при проверке ввода пользователя, когда такие орфографические ошибки встречаются очень часто.

Надеюсь, это поможет вам понять, как решить эту проблему.

(1 - (levNum / Math.max(s.length,t.length) ) ) *100

должно быть правильно

По сути, это вариант 2, упомянутый в моем вопросе. Однако позвольте мне продемонстрировать проблему с таким подходом.

Q = "ABC Corp" (len = 8)
M1 = "ABC"
M2 = "ABC Corporati"
M3 = "ABC Corp"

Я выбрал M1 и M2 так, чтобы их расстояния Lev были одинаковыми (по 5). Используя вариант 2, процент совпадений будет

M1 = (1 - 5/8)*100  = 37.5%
M2 = (1 - 5/13)*100 = 61.5%
M3 = 100%

Как вы можете видеть, если я представлю совпадения в таком порядке, существует огромная разница в рангах между M1 и M2, даже несмотря на то, что у них одинаковое расстояние левов. Вы видите проблему?

Что насчет этого:

100 - ( ((2*Lev_distance(Q, Mi)) / (Q.length + Mi.length)) * 100 )

Это дает одинаковое расстояние на (Q, M1) и (Q,M2)

Максимальное количество дистанций Левенштейна [l1, l2].max. Я думаю, это правда. Но делить по нему не стоит.

gem install levenshtein diff-lcs

Diff::LCS.lcs "abc", "qwer"
=> []
Levenshtein.distance("abc", "qwer").to_f / [3, 4].max
=> 1.0

Diff::LCS.lcs "abc", "cdef"
=> ["c"]
Levenshtein.distance("abc", "cdef").to_f / [3, 4].max
=> 1.0

Diff::LCS.lcs "1234", "34567890"
=> ["3", "4"]
Levenshtein.distance("1234", "34567890").to_f / [4, 8].max
=> 1.0

Левенштейн не выглядит надежным способом сравнения строк в процентах. Я не хочу рассматривать похожие строки как 100% разные.

Я могу порекомендовать просто проанализировать разницу между каждой последовательностью и LCS.

def get_similarity(sequence_1, sequence_2)
  lcs_length = Diff::LCS::Internals.lcs(sequence_1, sequence_2).compact.length
  lcs_length.to_f * 2 / (sequence_1.length + sequence_2.length)
end

Max = Lev_distance(Q,''); //max operations to transform query string to empty string
PM = (Max - Lev_distance(Q, Mi)) / Max * 100%;

Думаю, этого хватит. Верно для крайних значений (в точности хватает одинаковых и совершенно разных строк) и правдоподобно

Я думаю, что более простой подход может быть:

from nltk import edit_distance

str1 = 'abc'
str2 = 'abd'
edit_dist  = edit_distance(str1,str2)
len_total = len(str1)+len(str2)
pct_edit_dist = ((len_total-edit_dist)/len_total)*100
print(pct_edit_dist)

pct_edit_dist будет 100 при полном соответствии и 0 при отсутствии совпадения.