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

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

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

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

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-процентный ранг).

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

Ответ 1

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

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

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

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

Ответ 2

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

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 и определить, допустима ли строка. Таким образом, вы можете использовать любые расширенные методы levenshtein, например расстояние Дамерау-Левенштейна, которые учитывают орфографическую ошибку, например. test → tset, только как 1 операция, что весьма полезно при проверке ввода пользователя, когда эти ошибки встречаются очень часто.

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

Ответ 3

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

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

Ответ 4

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

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

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

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

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

Ответ 5

Как насчет этого:

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

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