Расчет относительного расстояния Левенштейна - имеет смысл?

Question

Я использую оба Naitch-Mokotoff Soundexing, так и Damerau-levenshtein, чтобы узнать, если пользовательская запись и значение в приложении являются «одинаковыми».

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

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

Это действительный / проверенный подход? Или это просто глупо?

Answer 1

Предполагается ли левенштейн расстояние, которое должно использоваться в качестве абсолютного значения?

Похоже, это будет зависеть от ваших требований. (Уточнить: Расстояние Левенштейна является Абсолютное значение, но, как указано значение OP, необработанное значение может быть не так полезно, как для заданного приложения в качестве меры, которая принимает во внимание длину слова. Это потому, что мы действительно больше интересуются сходством, чем расстояние как можно.)

Я использую оба Naitch-Mokotoff Soundexing, так и Damerau-levenshtein, чтобы узнать, если пользовательская запись и значение в приложении являются «одинаковыми».

Похоже, вы пытаетесь определить, будь то пользователь предназначена Их запись будет такой же, как данное значение данных?

Вы делаете проверку заклинанием? или соответствовать неверному вводу в известном наборе значений? Каковы ваши приоритеты?

• Минимизируйте ложные позитивы (попробуйте убедиться, что все предложенные слова очень «похожи», а список предложений коротко)
• Минимизируйте ложные негативы (попробуйте убедиться, что строка, предназначенная, предназначенная для пользователя в списке предложений, даже если это делает список длинным)
• Максимизировать среднюю точность соответствия

Вы можете в конечном итоге использовать расстояние Левенштейна таким образом, чтобы определить, следует ли предложить ли слово в списке предложение; И еще один способ определить, как заказать список предложений.

Мне кажется, если я правильно выстроил вашу цель, что ясно-что вы хотите измерить сходство а не разница между двумя строками. Как таковой, вы могли бы использовать Дистанция Яро или Яро-Винклера, который учитывает длину строк и количество символов общего:

Дистанционное расстояние Джем из двух заданных струн S1 и S2

(m / |s1| + m / |s2| + (m - t) / m) / 3

куда:

• M - количество сопоставленных символов
• t - количество транспонинтов

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

Answer 2

Расстояние Левенштейна является относительным значением между двумя словами. Сравнение LD к длине не актуальна, например,

Кошка -> Scat = 1 (75% похожи ??)

Разница -> Отличия = 1 (90% похожих ??)

Обе эти слова имеют расстояния Льва 1 т. Е. Они отличаются одним символом, но по сравнению с их длинами, второй набор, кажется, «более» аналогичен.

Я использую Soundexing, чтобы ранжировать слова, которые имеют одно и то же расстояние Льва, например,

cat а также fat Оба имеют ЛД 1 относительно kat, но слово, скорее всего, будет кат, чем жир при использовании Soundex (при условии, что слово неверно пишется, а не неправильно напечатано!)

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