вторник, 4 февраля 2014 г.

Python вычисление расстояния Хемминга между двоичными числами

Расстоянием Хемминга d(a,b) между двумя двоичными словами a и b называют число не совпадающих позиций в них. Для строк, количество различающихся позиций для строк с одинаковой длинной. Расстояние Хэмминга уже довольно широко используется для различных задач, таких как поиск близких дубликатов, распознавание образов, классификация документов, исправление ошибок, обнаружения вирусов и т.д.
Рассчитывается расстояние для двоичных чисел как исключающее ИЛИ (XOR) между двумя этими числами сложенное поэлементно. Например:
117 = 0 1 1 1 0 1 0 1 
  17 = 0 0 0 1 0 0 0 1 
   H = 0+1+1+0+0+1+0+0 = 3 - расстояние Хемминга
код на Python
int(reduce(lambda x, y: int(x) + int(y), list(bin(a ^ b)[2:])))
или
str(bin(a^b)).count('1')

Комментариев нет:

Отправить комментарий