Хемингово растојање

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

3-битна бинарна коцка за налажење Хеминговог растојања	Два примера растојања: 100->011 има растојање 3 (црвена путања); 010->111 има растојање 2 (плава путања)
4-бинарна хиперкоцка за налажење Хеминговог растојања
Два примера растојања: 0100->1001 има растојање 3 (црвена путања); 0110->1110 има растојање 1 (плава путања)

Примери

Хемингово растојање између:

"тачка" и "бачва" је 2.
1011101 и 1001001 је 2.
2173896 и 2233796 је 3.

Специјална својства

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

Кад су у питању бинарне ниске a и b Хемингово растојање је једнако броју јединица у a XOR b. Метрички простор бинарних ниски дужине n, са Хеминговим растојањем је познат као Хемингова коцка; она је као метрички простор еквивалентна скупу чворова у графу у облику хиперкоцке. Бинарне ниске дужине n могу да се посматрају и као вектор у $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). Овај документ је у јавном власништву.

^ (PDF). 26 (2): 147—160 https://web.archive.org/web/20060525060427/http://www.caip.rutgers.edu/~bushnell/dsdwebsite/hamming.pdf. Архивирано из оригинала (PDF) 25. 05. 2006. г. Приступљено 14. 05. 2010. Недостаје или је празан параметар |title= (помоћ), MR0035935, http://www.caip.rutgers.edu/~bushnell/dsdwebsite/hamming.pdf Архивирано на сајту Wayback Machine (25. мај 2006) .
^ Pilcher, C. D.; Wong, J. K.; Pillai, S. K. (2008). „Inferring HIV transmission dynamics from phylogenetic sequence relationships”. PLOS Medicine. 5 (3): e69. PMC 2267810  . PMID 18351799. doi:10.1371/journal.pmed.0050069  .
^ Wegner, Peter (1960). „A technique for counting ones in a binary computer”. Communications of the ACM. 3 (5): 322. S2CID 31683715. doi:10.1145/367236.367286. .

Спољашње везе

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

[1] (PDF). 26 (2): 147—160 https://web.archive.org/web/20060525060427/http://www.caip.rutgers.edu/~bushnell/dsdwebsite/hamming.pdf. Архивирано из оригинала (PDF) 25. 05. 2006. г. Приступљено 14. 05. 2010. Недостаје или је празан параметар |title= (помоћ), MR0035935, http://www.caip.rutgers.edu/~bushnell/dsdwebsite/hamming.pdf Архивирано на сајту Wayback Machine (25. мај 2006) .

[pmid18351799-2] Pilcher, C. D.; Wong, J. K.; Pillai, S. K. (2008). „Inferring HIV transmission dynamics from phylogenetic sequence relationships”. PLOS Medicine. 5 (3): e69. PMC 2267810  . PMID 18351799. doi:10.1371/journal.pmed.0050069  .

[3] Wegner, Peter (1960). „A technique for counting ones in a binary computer”. Communications of the ACM. 3 (5): 322. S2CID 31683715. doi:10.1145/367236.367286. .

[1]

[2]

[3]