Левенштейн расстояние с скремблированием персонажей?

Question

Я ищу строку сравнения meta ala Levenshtein, которая также будет работать, когда символы в строке будут скремблированы. Кто-нибудь знает такую ​​метрику? Было бы замечательно, если бы был модуль Python, который мог бы вычислить такую ​​метрику. Спасибо!

Answer 1

Вы можете попробовать библиотеку difflib или есть также внешняя библиотека под названием pylevenshtein.

Answer 2

Подсчитайте количество символов каждого типа (используя HashMap или его эквивалент), затем вычтите результирующие значения и возьмите абсолютное значение каждого вычитания. Добавьте все вместе, затем разделите на 2 (потому что вы дважды подсчитали каждую разницу).

Пример:

banana 
batman 

a - 3 , 2 -> |1| -> 1 
b - 1 , 1 -> |0| -> 0 
m - 0 , 1 -> |-1| -> 1 
n - 2 , 1 -> |1| -> 1 
t - 0 , 1 -> |-1| -> 1 

Поэтому у вас есть 1+1+1+1 = 4 -> 4/2 = 2

Проверить: В banana измените один n к t и один a к m (2 изменения) и у вас есть письма в batman

Если строки имеют разную длину, вычислите разницу в длине строки, вычтите, что номер из вашего счета разницы (выше). Затем разделите на 2, затем добавьте это число назад.

Пример:

nab 
banana 

total difference count: 3 
3 - 3 = 0 -> 0/2 = 0 -> 0 + 3 = 3 

Кроме того, я бы не использовать Левенштейна вообще здесь, потому что много трудности с этой проблемой является позиционирование, что вы не заботитесь о.

Answer 3

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

Редактировать: Этот алгоритм уже существует и называется Damerau–Levenshtein distance. Поиск по этому алгоритму даст вам Python package, который вы можете использовать напрямую.