Hemingovo rastojanje

U teoriji informacija, Hemingovo rastojanje između dve niske (reči) jednakih dužina je jednako broju mesta na kojima se odgovarajući simboli tih niski ne poklapaju. Drugim rečima, Hemingovo rastojanje predstavlja minimalan broj zamena koje je neophodno sprovesti da bi se jedna niska pretvorila udrugu, ili broj grešaka koje su transformisale jednu nisku u drugu.

3-bitna binarna kocka za nalaženje Hemingovog rastojanja	Dva primera rastojanja: 100->011 ima rastojanje 3 (crvena putanja); 010->111 ima rastojanje 2 (plava putanja)
4-binarna hiperkocka za nalaženje Hemingovog rastojanja
Dva primera rastojanja: 0100->1001 ima rastojanje 3 (crvena putanja); 0110->1110 ima rastojanje 1 (plava putanja)

Primeri

Hemingovo rastojanje između:

• "tačka" i "bačva" je 2.
• 1011101 i 1001001 je 2.
• 2173896 i 2233796 je 3.

Specijalna svojstva

Za fiksnu dužinu n, Hemingovo rastojanje je metrika na vektorskom prostoru reči te dužine, jer očigledno ispunjava svojstva nenegativnosti, važi da je H(x, y) = 0 akko x = y, ispunjava svojstvo simetrije, i lako se može pokazati potpunom indukcijom da zadovoljava i svojstvo nejednakosti trougla. Hemingovo rastojanje između reči a i b može takođe da se posmatra i kao Hemingova težina za a−b uz odgovarajući izbor operatora −.

Kad su u pitanju binarne niske a i b Hemingovo rastojanje je jednako broju jedinica u a XOR b. Metrički prostor binarnih niski dužine n, sa Hemingovim rastojanjem je poznat kao Hemingova kocka; ona je kao metrički prostor ekvivalentna skupu čvorova u grafu u obliku hiperkocke. Binarne niske dužine n mogu da se posmatraju i kao vektor u $R^{n}$ gde se svaki simbol posmatra kao realna koordinata; na ovaj način, niske daju čvorove n-dimenzione hiperkocke, a Hemingovo rastojanje između dve niske je ekvivalentno Menhetn rastojanju između čvorova.

Istorija i primene

Hemingovo rastojanje je nazvano po Ričardu Hemingu, koji ga je uveo u svom radu o Hemingovom kodu, Kodiranja za otkrivanje i korekciju grešaka iz 1950. godine. Koristi se u telekomunikacijama gde broj zamenjenih bitova u binarnoj reči fiksne dužine predstavlja procenu greške, i stoga se ponekad naziva signalno rastojanje. Analiza Hemingove težine se koristi u više disciplina uključujući teoriju informacija, teoriju kodiranja, i kriptografiju. Međutim, za upoređivanje niski različitih dužina, ili niski gde se ne očekuju samo zamene simbola već i njihovo umetanje ili brisanje, od veće koristi su sofisticiranije metrike, poput Levenštajnovog rastojanja. Za q-arne niske nad azbukom veličine q ≥ 2 Hemingovo rastojanje se primenjuje u slučaju ortogonalne modulacije, dok se Lijevo rastojanje koristi za faznu modulaciju. Ako je q = 2 ili q = 3 ova dva rastojanja se poklapaju.

Hemingovo rastojanje se takođe koristi u sistematici, kao mera genetskog rastojanja.

Na mreži (poput šahovske table), tačke na Lijevom rastojanju 1 grade fon Nojmanovu okolinu oko te tačke.

Primer algoritma

Pajton funkcija hamming_distance() računa Hemingovo rastojanje između dve niske (ili drugih iterabilnih objekata) jednake dužine, tako što napravi niz nula i jedinica koje označavaju poklapanja ili nepoklapanja između odgovarajućih pozicija u dve niske, i zatim sabere elemente tog niza.

def hamming_distance(s1, s2):
    assert len(s1) == len(s2)
    return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2))

Sledeća C funkcija računa Hemingovo rastojanje dva cela broja (posmatrana u binarnom obliku, to jest kao niz bitova). Vreme izvršavanja ove procedure je proporcionalno Hemingovom rastojanju dva broja a ne broju bitova u ulazu. Računa se bitovska ekskluzivna disjunkcija dva zadata broja, a zatim se nalazi Hemingova težina rezultata (broj bitova različitih od nule) korišćenjem algoritma koji uzastopno pronalazi i briše bit različit od nule najnižeg reda.

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;
}

Vidi još

• Damerau-Levenštajnovo rastojanje
• Žakardov indeks
• Sličnost (matematika)
• Serensenov indeks sličnosti

Napomene

• Ovaj članak uključuje materijal iz dokumenta Federalni standard 1037C (Federal Standard 1037C), Administracije za opšte službe (General Services Administration). Ovaj dokument je u javnom vlasništvu.

Spoljašnje veze

• Primer Hemingovog rastojanja (jezik: engleski)
• Alat za pravljenje Hemingovog koda (jezik: engleski)