Расстояние Хэмминга — различия между версиями
Whiplash (обсуждение | вклад) |
Whiplash (обсуждение | вклад) |
||
Строка 15: | Строка 15: | ||
#<tex>~d(x, y) = 0 \iff x = y</tex> ''(Если расстояние от '''x''' до '''y''' равно нулю, то '''x''' и '''y''' совпадают ('''x''' равно '''y'''))'' | #<tex>~d(x, y) = 0 \iff x = y</tex> ''(Если расстояние от '''x''' до '''y''' равно нулю, то '''x''' и '''y''' совпадают ('''x''' равно '''y'''))'' | ||
#<tex>~d(x,y)=d(y,x)</tex> ''(Объект '''x''' удален от объекта '''y''' так же, как объект '''y''' удален от объекта '''x''')'' | #<tex>~d(x,y)=d(y,x)</tex> ''(Объект '''x''' удален от объекта '''y''' так же, как объект '''y''' удален от объекта '''x''')'' | ||
− | #<tex>~d(x,z) \le d(x,y) + d(y,z)</tex> ''(Это свойство обычно называют неравенством треугольника за его естественную геометрическую аналогию: сумма двух сторон треугольника всегда больше третьей стороны.)'' | + | #<tex>~d(x,z) \le d(x,y) + d(y,z)</tex> ''(Расстояние от '''x''' до '''z''' всегда меньше или равно расстоянию от '''x''' до '''z''' через точку '''y''' (равенство достигается только в том случае, если точка '''y''' принадлежит отрезку '''xz'''). Это свойство обычно называют неравенством треугольника за его естественную геометрическую аналогию: сумма двух сторон треугольника всегда больше третьей стороны.)'' |
== Доказательство неравенства треугольника == | == Доказательство неравенства треугольника == |
Версия 00:53, 26 октября 2011
Определение: |
Расстояние Хэмминга (Hamming distance) — число позиций, в которых соответствующие цифры двух двоичных слов одинаковой длины различны. |
В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых k-ичных алфавитов и служит метрикой различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.
Пример
Свойства
Расстояние Хэмминга обладает свойствами метрики, так как удовлетворяет ее определению.
- (Если расстояние от x до y равно нулю, то x и y совпадают (x равно y))
- (Объект x удален от объекта y так же, как объект y удален от объекта x)
- (Расстояние от x до z всегда меньше или равно расстоянию от x до z через точку y (равенство достигается только в том случае, если точка y принадлежит отрезку xz). Это свойство обычно называют неравенством треугольника за его естественную геометрическую аналогию: сумма двух сторон треугольника всегда больше третьей стороны.)
Доказательство неравенства треугольника
Утверждение: |
Пусть слова x и y отличаются в некоторой позиции t. Тогда какое бы слово z мы ни взяли, оно в этой позиции будет отличаться по крайней мере от одного из слов x и y. Следовательно, суммируя в правой части | и , мы обязательно учтем все позиции, в которых различались слова x и y.