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

Из Википедије, слободне енциклопедије
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 може такође да се посматра и као Хамингова тежина за ab уз одговарајући избор оператора −.

Кад су у питању бинарне ниске 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). Овај документ је у јавном власништву.
  1. ^ Hamming, Richard W. (1950), "Error detecting and error correcting codes", Bell System Technical Journal 26 (2): 147–160, MR0035935, http://www.caip.rutgers.edu/~bushnell/dsdwebsite/hamming.pdf .
  2. ^ Pilcher, C. D.; Wong, J. K.; Pillai, S. K. (March 2008), "Inferring HIV transmission dynamics from phylogenetic sequence relationships", PLoS Med. 5 (3): e69, doi:10.1371/journal.pmed.0050069, PMID 18351799.
  3. ^ Wegner, Peter (1960), "A technique for counting ones in a binary computer", Communications of the ACM 3 (5): 322, doi:10.1145/367236.367286.

Спољашње везе[уреди]