Расстояние Хэмминга — различия между версиями
Proshev (обсуждение | вклад) |
(Привет с матмеха :)) |
||
| Строка 6: | Строка 6: | ||
==Пример== | ==Пример== | ||
| − | * | + | *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 |
==Свойства== | ==Свойства== | ||
Версия 19:21, 25 июня 2012
| Определение: |
| Расстояние Хэмминга (Hamming distance) — число позиций, в которых различаются соответствующие символы двух строк одинаковой длины. |
В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых k-ичных алфавитов и служит метрикой различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.
Пример
- d(1011101, 1001001)=2
- d(1538124, 1523156)=4
- d(hill, holl)=1
Свойства
Расстояние Хэмминга обладает свойствами метрики, так как удовлетворяет ее определению.
- (Если расстояние от до равно нулю, то и совпадают ())
- (Объект удален от объекта так же, как объект удален от объекта )
- (Расстояние от до всегда меньше или равно расстоянию от до через точку . Это свойство обычно называют неравенством треугольника за его естественную геометрическую аналогию: сумма двух сторон треугольника всегда больше третьей стороны.)
Доказательство неравенства треугольника
| Утверждение: |
| Пусть слова и отличаются в некоторых позициях. Тогда какое бы слово мы ни взяли, оно будет отличаться в каждой из этих позиций по крайне мере от одного из слов и . Следовательно, суммируя в правой части и , мы обязательно учтем все позиции, в которых различались слова и . Т.е. получается, что . |
