У теори?и информаци?а , Хемингово расто?а?е изме?у две ниске (речи) ?еднаких дужина ?е ?еднако бро?у места на ко?има се одговара?у?и симболи тих ниски не поклапа?у. Другим речима, Хемингово расто?а?е представ?а минималан бро? замена ко?е ?е неопходно спровести да би се ?една ниска претворила удругу, или бро? грешака ко?е су трансформисале ?едну ниску у другу.

Примери [ уреди | уреди извор ]

Хемингово расто?а?е изме?у:

• " т ач к а " и " б ач в а " ?е 2.
• 10 1 1 1 01 и 10 0 1 0 01 ?е 2.
• 2 17 3 8 96 и 2 23 3 7 96 ?е 3.

Специ?ална сво?ства [ уреди | уреди извор ]

За фиксну дужину n , Хемингово расто?а?е ?е метрика на векторском простору речи те дужине, ?ер очигледно испу?ава сво?ства ненегативности, важи да ?е H(x, y) = 0 акко x = y, испу?ава сво?ство симетри?е, и лако се може показати потпуном индукци?ом да задово?ава и сво?ство не?еднакости троугла . Хемингово расто?а?е изме?у речи a и b може тако?е да се посматра и као Хемингова тежина за a ? b уз одговара?у?и избор оператора ?.

Кад су у пита?у бинарне ниске a и b Хемингово расто?а?е ?е ?еднако бро?у ?единица у a XOR b . Метрички простор бинарних ниски дужине n , са Хеминговим расто?а?ем ?е познат као Хемингова коцка ; она ?е као метрички простор еквивалентна скупу чворова у графу у облику хиперкоцке. Бинарне ниске дужине n могу да се посматра?у и као вектор у ${\displaystyle R^{n}}$ где се сваки симбол посматра као реална координата; на ова? начин, ниске да?у чворове n -димензионе хиперкоцке , а Хемингово расто?а?е изме?у две ниске ?е еквивалентно Менхетн расто?а?у изме?у чворова.

Истори?а и примене [ уреди | уреди извор ]

Хемингово расто?а?е ?е названо по Ричарду Хемингу , ко?и га ?е увео у свом раду о Хеминговом коду , Кодира?а за открива?е и корекци?у грешака из 1950. године. ^[1] Користи се у телекомуникаци?ама где бро? заме?ених битова у бинарно? речи фиксне дужине представ?а процену грешке, и стога се понекад назива сигнално расто?а?е . Анализа Хемингове тежине се користи у више дисциплина ук?учу?у?и теори?у информаци?а , теори?у кодира?а , и криптографи?у . Ме?утим, за упоре?ива?е ниски различитих дужина, или ниски где се не очеку?у само замене симбола ве? и ?ихово умета?е или бриса?е, од ве?е користи су софистицирани?е метрике, попут Левеншта?новог расто?а?а . За q -арне ниске над азбуком величине q  ≥ 2 Хемингово расто?а?е се приме?у?е у случа?у ортогоналне модулаци?е , док се Ли?ево расто?а?е користи за фазну модулаци?у. Ако ?е q  = 2 или q  = 3 ова два расто?а?а се поклапа?у.

Хемингово расто?а?е се тако?е користи у систематици, као мера генетског расто?а?а. ^[2]

На мрежи (попут шаховске табле), тачке на Ли?евом расто?а?у 1 граде фон Но?манову околину око те тачке.

Пример алгоритма [ уреди | уреди извор ]

Па?тон функци?а hamming_distance() рачуна Хемингово расто?а?е изме?у две ниске (или других итерабилних об?еката) ?еднаке дужине, тако што направи низ нула и ?единица ко?е означава?у поклапа?а или непоклапа?а изме?у одговара?у?их позици?а у две ниске, и затим сабере елементе тог низа.

def
 hamming_distance
(
s1
,
 s2
):

    assert
 len
(
s1
)
 ==
 len
(
s2
)

    return
 sum
(
ch1
 !=
 ch2
 for
 ch1
,
 ch2
 in
 zip
(
s1
,
 s2
))

Следе?а C функци?а рачуна Хемингово расто?а?е два цела бро?а (посматрана у бинарном облику, то ?ест као низ битова). Време извршава?а ове процедуре ?е пропорционално Хеминговом расто?а?у два бро?а а не бро?у битова у улазу. Рачуна се битовска ексклузивна дис?ункци?а два задата бро?а, а затим се налази Хемингова тежина резултата (бро? битова различитих од нуле) кориш?е?ем алгоритма ^[3] ко?и узастопно проналази и брише бит различит од нуле на?нижег реда.

unsigned
 hamdist
(
unsigned
 x
,
 unsigned
 y
)

{

  unsigned
 dist
 =
 0
,
 val
 =
 x
 ^
 y
;


  // Count the number of set bits

  while
(
val
)

  {

    ++
dist
;
 
    val
 &=
 val
 -
 1
;

  }


  return
 dist
;

}

Види ?ош [ уреди | уреди извор ]

• Дамерау-Левеншта?ново расто?а?е
• Жакардов индекс
• Сличност (математика)
• Серенсенов индекс сличности

Напомене [ уреди | уреди извор ]

• Ова? чланак ук?учу?е матери?ал из документа Федерални стандард 1037C ( Federal Standard 1037C ), Администраци?е за опште службе ( General Services Administration ). Ова? документ ?е у ?авном власништву.

Спо?аш?е везе [ уреди | уреди извор ]

• Пример Хеминговог расто?а?а (?език: енглески)
• Алат за прав?е?е Хеминговог кода (?език: енглески)