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




расстояние левенштейна для чайников (4)

Я пытаюсь сопоставить один поисковый запрос со словарем возможных совпадений, используя алгоритм расстояния Левенштейна. Алгоритм возвращает расстояние, выраженное в количестве операций, необходимых для преобразования строки поиска в совпадающую строку. Я хочу представить результаты в ранжированном процентном списке лучших "N" (скажем, 10) совпадений.

Так как строка поиска может быть длиннее или короче, чем отдельные строки словаря, что было бы подходящей логикой для выражения расстояния в процентах, которое качественно отражало бы, насколько близко «в процентах» каждый результат к строке запроса с % указывает на точное совпадение.

Я рассмотрел следующие варианты:

Q = query string
M = matched string
PM = Percentage Match
Option 1. PMi = (1 - Lev_distance(Q, Mi)/Strlen(Q)) * 100
Option 2. PMi = (1 - Lev_distance(Q, Mi)/max(Strlen(Q), strlen(Mi))) * 100

Вариант 1 имеет возможность отрицательного процента в случае, если расстояние больше, чем длина строки поиска, где строка соответствия длинна. Например, запрос «ABC» соответствует «ABC Corp.» приведет к отрицательному совпадению процентов.

Вариант 2, по-видимому, не дает согласованного процента в наборе Mi, поскольку при каждом расчете может использоваться другой знаменатель, и, следовательно, результирующие процентные значения не будут нормализованы.

Единственный другой способ, который я могу придумать, - это прекратить сравнение lev_distance с любой длиной строки, но вместо этого представить сравнительные расстояния верхних «N» совпадений в виде обратного процентиля (100-процентиля).

Какие-нибудь мысли? Есть ли лучшие подходы? Я должен что-то упустить, так как расстояние Левенштейна, вероятно, является наиболее распространенным алгоритмом для нечетких совпадений, и это должно быть очень распространенной проблемой.


Максимальное количество левенштейновских расстояний составляет [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% разным .

Я могу рекомендовать просто анализировать diff между каждой последовательностью и 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

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

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

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

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

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


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

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

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

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


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

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

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