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

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

За фиксну дужину ''-{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> Користи се у [[телекомуникације|телекомуникацијама]] где број замењених битова у бинарној речи фиксне дужине представља процену грешке, и стога се понекад назива '''сигнално растојање'''. Анализа Хамингове тежине се користи у више дисциплина укључујући [[теорија информацијаинформације|теорију информација]], [[теорија кодирања|теорију кодирања]], и [[криптографија|криптографију]]. Међутим, за упоређивање ниски различитих дужина, или ниски где се не очекују само замене симбола већ и њихово уметање или брисање, од веће користи су софистицираније метрике, попут [[Левенштајново растојање|Левенштајновог растојања]].

[[ПрограмскиПајтон језик(програмски Питонјезик)|Пајтон]] функција <code>hamming_distance()</code> рачуна Хамингово растојање између две ниске (или других итерабилних објеката) једнаке дужине, тако што направи низ нула и јединица које означавају поклапања или непоклапања између одговарајућих позиција у две ниске, и затим сабере елементе тог низа.

Следећа [[ПрограмскиC језик(програмски Цјезик)|C]] функција рачуна Хамингово растојање два цела броја (посматрана у бинарном облику, то јест као низ битова). Време извршавања ове процедуре је пропорционално Хаминговом растојању два броја а не броју битова у улазу. Рачуна се [[битовска операција|битовска]] [[искључива дисјункција|ексклузивна дисјункција]] два задата броја, а затим се налази [[Хамингова тежина]] резултата (број битова различитих од нуле) коришћењем алгоритма <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> који узастопно проналази и брише бит различит од нуле најнижег реда.