Расстояние Хэмминга — различия между версиями
Whiplash (обсуждение | вклад) |
Whiplash (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | '''Расстояние Хэмминга''' — число позиций, в которых соответствующие цифры двух двоичных слов одинаковой длины различны. В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых k-ичных алфавитов и служит [[Метрическое пространство#def1 | метрикой]] различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности. | + | {{Определение |
| + | |definition= | ||
| + | '''Расстояние Хэмминга''' — число позиций, в которых соответствующие цифры двух двоичных слов одинаковой длины различны. В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых k-ичных алфавитов и служит [[Метрическое пространство#def1 | метрикой]] различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.}} | ||
| Строка 16: | Строка 18: | ||
Объект '''x''' удален от объекта '''y''' так же, как объект '''y''' удален от объекта '''x'''. | Объект '''x''' удален от объекта '''y''' так же, как объект '''y''' удален от объекта '''x'''. | ||
| − | + | ||
'''3)''' <tex>~d(x,z) \le d(x,y) + d(y,z)</tex> | '''3)''' <tex>~d(x,z) \le d(x,y) + d(y,z)</tex> | ||
| Строка 23: | Строка 25: | ||
'''Доказательство:''' | '''Доказательство:''' | ||
Пусть слова '''x''' и '''y''' отличаются в некоторой позиции '''t'''. Тогда какое бы слово '''z''' мы ни взяли, оно в этой позиции будет отличаться по крайней мере от одного из слов '''x''' и '''y'''. Следовательно, суммируя в правой части <tex>~d(x, z)</tex> и <tex>~d(z, y)</tex>, мы обязательно учтем все позиции, в которых различались слова '''x''' и '''y'''. | Пусть слова '''x''' и '''y''' отличаются в некоторой позиции '''t'''. Тогда какое бы слово '''z''' мы ни взяли, оно в этой позиции будет отличаться по крайней мере от одного из слов '''x''' и '''y'''. Следовательно, суммируя в правой части <tex>~d(x, z)</tex> и <tex>~d(z, y)</tex>, мы обязательно учтем все позиции, в которых различались слова '''x''' и '''y'''. | ||
| − | |||
Математики договорились любую функцию, обладающую указанными тремя свойствами, называть расстоянием. | Математики договорились любую функцию, обладающую указанными тремя свойствами, называть расстоянием. | ||
Версия 22:42, 22 октября 2011
| Определение: |
| Расстояние Хэмминга — число позиций, в которых соответствующие цифры двух двоичных слов одинаковой длины различны. В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых k-ичных алфавитов и служит метрикой различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности. |
Пример
Свойства
Расстояние Хэмминга обладает свойствами метрики, удовлетворяя следующим условиям:
1)
2)
Объект x удален от объекта y так же, как объект y удален от объекта x.
3)
Третье свойство говорит, что дорога через третий объект с всегда длиннее, нежели прямой путь. Его обычно называют неравенством треугольника за его естественную геометрическую аналогию: сумма двух сторон треугольника всегда больше третьей стороны.
Доказательство: Пусть слова x и y отличаются в некоторой позиции t. Тогда какое бы слово z мы ни взяли, оно в этой позиции будет отличаться по крайней мере от одного из слов x и y. Следовательно, суммируя в правой части и , мы обязательно учтем все позиции, в которых различались слова x и y.
Математики договорились любую функцию, обладающую указанными тремя свойствами, называть расстоянием.
