Расстояние Хэмминга — различия между версиями
Whiplash (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
| (не показано 5 промежуточных версий 5 участников) | |||
| Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | '''Расстояние Хэмминга (Hamming distance | + | '''Расстояние Хэмминга''' (англ. ''Hamming distance'') {{---}} число позиций, в которых различаются соответствующие символы двух строк одинаковой длины. }} |
В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых k-ичных алфавитов и служит [[Метрическое пространство#def1 | метрикой]] различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности. | В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых k-ичных алфавитов и служит [[Метрическое пространство#def1 | метрикой]] различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности. | ||
| − | |||
==Пример== | ==Пример== | ||
| − | * | + | *d(10<font color="blue">1</font>1<font color="blue">1</font>01, 10<font color="red">0</font>1<font color="red">0</font>01)=2 |
| − | * | + | *d(15<font color="blue">38</font>1<font color="blue">24</font>, 15<font color="red">23</font>1<font color="red">56</font>)=4 |
| − | * | + | *d(h<font color="blue">i</font>ll, h<font color="red">o</font>ll)=1 |
==Свойства== | ==Свойства== | ||
| Строка 15: | Строка 14: | ||
#<tex>~d(x, y) = 0 \iff x = y</tex> ''(Если расстояние от <tex>x</tex> до <tex>y</tex> равно нулю, то <tex>x</tex> и <tex>y</tex> совпадают (<tex>x = y</tex>))'' | #<tex>~d(x, y) = 0 \iff x = y</tex> ''(Если расстояние от <tex>x</tex> до <tex>y</tex> равно нулю, то <tex>x</tex> и <tex>y</tex> совпадают (<tex>x = y</tex>))'' | ||
#<tex>~d(x,y)=d(y,x)</tex> ''(Объект <tex>x</tex> удален от объекта <tex>y</tex> так же, как объект <tex>y</tex> удален от объекта <tex>x</tex>)'' | #<tex>~d(x,y)=d(y,x)</tex> ''(Объект <tex>x</tex> удален от объекта <tex>y</tex> так же, как объект <tex>y</tex> удален от объекта <tex>x</tex>)'' | ||
| − | #<tex>~d(x,y) \ | + | #<tex>~d(x,y) \leqslant d(x,z) + d(z,y)</tex> ''(Расстояние от <tex>x</tex> до <tex>y</tex> всегда меньше или равно расстоянию от <tex>x</tex> до <tex>y</tex> через точку <tex>z</tex>. Это свойство обычно называют неравенством треугольника за его естественную геометрическую аналогию: сумма двух сторон треугольника всегда больше третьей стороны.)'' |
== Доказательство неравенства треугольника == | == Доказательство неравенства треугольника == | ||
{{Утверждение | {{Утверждение | ||
| − | |statement=<tex>~d(x,y) \ | + | |statement=<tex>~d(x,y) \leqslant d(x,z) + d(z,y)</tex> |
| − | |proof= | + | |proof= |
| − | Пусть слова <tex>x</tex> и <tex>y</tex> отличаются в некоторых позициях. Тогда какое бы слово <tex>z</tex> мы ни взяли, оно будет отличаться в каждой из этих позиций по крайне мере от одного из слов <tex>x</tex> и <tex>y</tex>. Следовательно, суммируя в правой части <tex>d(x, z)</tex> и <tex>d(z, y)</tex>, мы обязательно учтем все позиции, в которых различались слова <tex>x</tex> и <tex>y</tex>. Т.е. получается, что <tex>~d(x,y) \ | + | Пусть слова <tex>x</tex> и <tex>y</tex> отличаются в некоторых позициях. Тогда какое бы слово <tex>z</tex> мы ни взяли, оно будет отличаться в каждой из этих позиций по крайне мере от одного из слов <tex>x</tex> и <tex>y</tex>. Следовательно, суммируя в правой части <tex>d(x, z)</tex> и <tex>d(z, y)</tex>, мы обязательно учтем все позиции, в которых различались слова <tex>x</tex> и <tex>y</tex>. Т.е. получается, что <tex>~d(x,y) \leqslant d(x,z) + d(z,y)</tex>. |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
}} | }} | ||
| − | |||
== См. также == | == См. также == | ||
*[[Избыточное кодирование, код Хэмминга]] | *[[Избыточное кодирование, код Хэмминга]] | ||
| − | == | + | == Источники информации == |
*[http://ru.wikipedia.org/wiki/Расстояние_Хэмминга Расстояние Хэмминга — Википедия] | *[http://ru.wikipedia.org/wiki/Расстояние_Хэмминга Расстояние Хэмминга — Википедия] | ||
*[http://en.wikipedia.org/wiki/Hamming_distance Hamming distance - Wikipedia] | *[http://en.wikipedia.org/wiki/Hamming_distance Hamming distance - Wikipedia] | ||
*[http://inf.1september.ru/article.php?ID=200701701 Математические основы информатики] | *[http://inf.1september.ru/article.php?ID=200701701 Математические основы информатики] | ||
| + | |||
| + | [[Категория: Дискретная математика и алгоритмы]] | ||
[[Категория: Алгоритмы сжатия]] | [[Категория: Алгоритмы сжатия]] | ||
Текущая версия на 19:05, 4 сентября 2022
| Определение: |
| Расстояние Хэмминга (англ. Hamming distance) — число позиций, в которых различаются соответствующие символы двух строк одинаковой длины. |
В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых k-ичных алфавитов и служит метрикой различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.
Пример
- d(1011101, 1001001)=2
- d(1538124, 1523156)=4
- d(hill, holl)=1
Свойства
Расстояние Хэмминга обладает свойствами метрики, так как удовлетворяет ее определению.
- (Если расстояние от до равно нулю, то и совпадают ())
- (Объект удален от объекта так же, как объект удален от объекта )
- (Расстояние от до всегда меньше или равно расстоянию от до через точку . Это свойство обычно называют неравенством треугольника за его естественную геометрическую аналогию: сумма двух сторон треугольника всегда больше третьей стороны.)
Доказательство неравенства треугольника
| Утверждение: |
| Пусть слова и отличаются в некоторых позициях. Тогда какое бы слово мы ни взяли, оно будет отличаться в каждой из этих позиций по крайне мере от одного из слов и . Следовательно, суммируя в правой части и , мы обязательно учтем все позиции, в которых различались слова и . Т.е. получается, что . |
