Можно ли использовать расстояние Хэмминга с небинарной структурой?

Известно, что расстояние Хэмминга применяется для вычисления разницы между двумя двоичными строками. Можно ли применить его для вычисления разницы между небинарными структурами?


algorithm hamming-distance
person Nasser    schedule 20.02.2017    source источник
comment
Вы всегда можете преобразовать недвоичное в двоичное   -  person Piotr Kamoda    schedule 20.02.2017
comment
Также это алгоритм обобщения Хэмминга, называемый Левенштейном   -  person Piotr Kamoda    schedule 20.02.2017
comment
Это зависит от конкретной проблемы. Если вы можете определить и указать, как вычислить разницу между двумя объектами, то вы, очевидно, сможете вычислить расстояние Хэмминга между ними.   -  person Yuriy Ivaskevych    schedule 20.02.2017

Ответы (1)


arrow_upward
0
arrow_downward

Расстояние Хэмминга двух строк одинаковой длины — это сумма расстояний между каждой парой соответствующих битов (т. е. L1), где последнее расстояние равно 0 для идентичных битов и 1 для неидентичных битов (т. е. дискретная метрика). Если вы хотите применить расстояние Хэмминга к алфавитам, которые не являются двоичными, вы можете заменить дискретную метрику другой метрикой по вашему выбору, например, Расстояние по Ли – это расстояние между двумя числами на окружности. Если строки имеют разную длину, вам нужно изменить что-то вроде расстояния Левенштейна, но даже в этом случае вы можете выбрать любую стоимость удаления/вставки/замены, которую вы хотите.

person David Eisenstat    schedule 20.02.2017