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

Question

Я использую как Daitch-Mokotoff soundexing, так и Damerau-Levenshtein, чтобы узнать, совпадают ли пользовательская запись и значение в приложении.значение?Если у меня есть слово из 20 букв, расстояние 4 не так уж плохо.Если слово состоит из 4 букв ...

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

Answer 1

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

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

Я использую оба Daitch-Mokotoff Зондирование и Дамерау-Левенштейн выяснить, если пользовательская запись и значение в приложении «одинаковые».

Похоже, вы пытаетесь определить, намеревался ли пользователь , чтобы его запись совпадала с заданным значением данных?

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

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

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

Мне кажется, если я правильно понял вашу цель, то, что вы хотите измерить, это сходство , а не разница между двумя строками. Таким образом, вы можете использовать расстояние Jaro или Jaro-Winkler , которое учитывает длину строк и общее количество символов:

расстояние Jaro dj двух заданных строки s1 и s2 это

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

где:

• m - количество совпадающих символов
• t - количество транспозиций

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

Answer 2

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

cat -> scat = 1 (75% похоже ??)

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

Оба эти слова имеют lev-расстояния 1, то есть они отличаются на один символ, но при сравнении с их длиной второй набор будет выглядеть более похожим.

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

cat и fat оба имеют LD равный 1 относительно kat, но слово более вероятнобыть kat чем fat при использовании soundex (при условии, что слово написано неправильно, а не неправильно набрано!)

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