Хемингово растојање — разлика између измена
Садржај обрисан Садржај додат
м Преусмерење на Хамингово растојање |
м Бот Мења: ro:Distanță Hamming |
||
Ред 1:
{| align="right"
#Преусмери [[Хамингово растојање]]▼
|-
| [[Слика:Hamming distance 3 bit binary.svg|мини|140п|3-битна бинарна [[коцка]] за налажење Хаминговог растојања]]
| [[Слика:Hamming distance 3 bit binary example.svg|мини|140п|Два примера растојања: 100->011 има растојање 3 (црвена путања); 010->111 има растојање 2 (плава путања)]]
|-
|colspan=2 | [[Слика:Hamming distance 4 bit binary.svg|мини|280п|4-бинарна [[хиперкоцка]] за налажење Хаминговог растојања]]
|-
|colspan=2 | [[Слика:Hamming distance 4 bit binary example.svg|мини|280п|Два примера растојања: 0100->1001 има растојање 3 (црвена путања); 0110->1110 има растојање 1 (плава путања)]]
|}
У [[теорија информација|теорији информација]], '''Хамингово растојање''' између две [[ниска (рачунарство)|ниске]] (речи) једнаких дужина је једнако броју места на којима се одговарајући симболи тих ниски не поклапају. Другим речима, Хамингово растојање представља минималан број ''замена'' које је неопходно спровести да би се једна ниска претворила удругу, или број ''грешака'' које су трансформисале једну ниску у другу.
== Примери ==
* "'''<font color=blue>т</font>ач<font color=blue>к</font>а'''" и "'''<font color=red>б</font>ач<font color=red>в</font>а'''" је 2.
* '''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.
* '''2<font color=blue>17</font>3<font color=blue>8</font>96''' и '''2<font color=red>23</font>3<font color=red>7</font>96''' је 3.
== Специјална својства ==
За фиксну дужину ''-{n}-'', Хамингово растојање је [[метрика (математика)|метрика]] на векторском простору речи те дужине, јер очигледно испуњава својства ненегативности, важи да је -{H(x, y) = 0}- [[акко]] -{x = y}-, испуњава својство симетрије, и лако се може показати [[потпуна индукција|потпуном индукцијом]] да задовољава и својство [[неједнакост троугла|неједнакости троугла]]. Хамингово растојање између речи ''-{a}-'' и ''-{b}-'' може такође да се посматра и као [[Хамингова тежина]] за -{''a''−''b''}- уз одговарајући избор оператора −.
Кад су у питању '''бинарне ниске''' ''-{a}-'' и ''-{b}-'' Хамингово растојање је једнако броју јединица у ''-{a}-'' -{[[ексклузивна дисјункција|XOR]]}- ''-{b}-''. Метрички простор бинарних ниски дужине ''-{n}-'', са Хаминговим растојањем је познат као ''Хамингова коцка''; она је као метрички простор еквивалентна скупу чворова у графу у облику хиперкоцке. Бинарне ниске дужине ''-{n}-'' могу да се посматрају и као вектор у <math>R^n</math> где се сваки симбол посматра као реална координата; на овај начин, ниске дају чворове ''-{n}-''-димензионе [[хиперкоцка|хиперкоцке]], а Хамингово растојање између две ниске је еквивалентно [[Менхетн растојању]] између чворова.
== Историја и примене ==
Хамингово растојање је названо по [[Ричард Хаминг|Ричарду Хамингу]], који га је увео у свом раду о [[Хаминговом коду]], ''Кодирања за откривање и корекцију грешака'' из 1950. године.<ref>-{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 .}-</ref> Користи се у [[телекомуникације|телекомуникацијама]] где број замењених битова у бинарној речи фиксне дужине представља процену грешке, и стога се понекад назива '''сигнално растојање'''. Анализа Хамингове тежине се користи у више дисциплина укључујући [[теорија информација|теорију информација]], [[теорија кодирања|теорију кодирања]], и [[криптографија|криптографију]]. Међутим, за упоређивање ниски различитих дужина, или ниски где се не очекују само замене симбола већ и њихово уметање или брисање, од веће користи су софистицираније метрике, попут [[Левенштајново растојање|Левенштајновог растојања]].
За ''-{q}-''-арне ниске над азбуком величине ''-{q}-'' ≥ 2 Хамингово растојање се примењује у случају ортогоналне [[модулација|модулације]], док се [[Лијево растојање]] користи за фазну модулацију. Ако је -{''q'' = 2}- или -{''q'' = 3}- ова два растојања се поклапају.
Хамингово растојање се такође користи у систематици, као мера генетског растојања.<ref name="pmid18351799">-{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 .}-</ref>
На мрежи (попут шаховске табле), тачке на [[Лијево растојање|Лијевом растојању]] 1 граде [[фон Нојманова околина|фон Нојманову околину]] око те тачке.
== Пример алгоритма ==
[[Програмски језик Питон|Питон]] функција <code>hamming_distance()</code> рачуна Хамингово растојање између две ниске (или других итерабилних објеката) једнаке дужине, тако што направи низ нула и јединица које означавају поклапања или непоклапања између одговарајућих позиција у две ниске, и затим сабере елементе тог низа.
{{-}}
<source lang="python">
def hamming_distance(s1, s2):
assert len(s1) == len(s2)
return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2))
</source>
Следећа [[Програмски језик Ц|Ц]] функција рачуна Хамингово растојање два цела броја (посматрана у бинарном облику, то јест као низ битова). Време извршавања ове процедуре је пропорционално Хаминговом растојању два броја а не броју битова у улазу. Рачуна се [[битовска операција|битовска]] [[ексклузивна дисјункција]] два задата броја, а затим се налази [[Хамингова тежина]] резултата (број битова различитих од нуле) коришћењем алгоритма <ref>Wegner, Peter (1960), "A technique for counting ones in a binary computer", Communications of the ACM 3 (5): 322, doi:10.1145/367236.367286 .</ref> који узастопно проналази и брише бит различит од нуле најнижег реда.
<source lang="c">
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;
}
</source>
== Види још ==
* [[Дамерау-Левенштајново растојање]]
* [[Жакардов индекс]]
* [[Сличност (математика)]]
* [[Серенсенов индекс сличности]]
== Напомене ==
*Овај чланак укључује материјал из документа ''Федерални стандард 1037C'' (''-{Federal Standard 1037C}-''), Администрације за опште службе (''-{General Services Administration}-''). Овај документ је у јавном власништву.
{{рефлист}}
== Спољашње везе ==
* [http://people.revoledu.com/kardi/tutorial/Similarity/HammingDistance.html Пример Хаминговог растојања] {{en}}
* [http://www.ee.unb.ca/cgi-bin/tervo/hamming.pl?X=+Generate+&L=12&D=4&T=000000000000 Алат за прављење Хаминговог кода] {{en}}
[[Категорија:Дискретна математика]]
[[Категорија:Алгоритми за рад са нискама]]
[[af:Hammingafstand]]
[[bg:Разстояние на Хеминг]]
[[ca:Distància de Hamming]]
[[cs:Hammingova vzdálenost]]
[[de:Hamming-Abstand]]
[[en:Hamming distance]]
[[es:Distancia de Hamming]]
[[fr:Distance de Hamming]]
[[he:מרחק המינג]]
[[hr:Hammingova udaljenost]]
[[it:Distanza di Hamming]]
[[ja:ハミング距離]]
[[ko:해밍 거리]]
[[hu:Hamming-távolság]]
[[nl:Hammingafstand]]
[[no:Hamming-avstand]]
[[pl:Odległość Hamminga]]
[[pt:Distância de Hamming]]
[[ro:Distanță Hamming]]
[[ru:Расстояние Хэмминга]]
[[fi:Hammingin etäisyys]]
[[vi:Khoảng cách Hamming]]
[[uk:Відстань Геммінга]]
[[zh:汉明距离]]
| |||