Extended Hamming Distance


The Hamming distance has long been used to measure the similarity between two bit vectors of the same dimension. It was extensively used in the early applications of information theory that focused on measuring the error introduced by the noise in the channel through which messages are sent from the source to the target. The classic, or crisp, Hamming distance (CHD) does not recognize the notion of approximate similarity, because it measurues only the exact extent to which the two corresponding bits in two bit strings agree.

One can view the CHD as an edit distance with the operations of insertion and deletion. Given two bit vectors of the same dimension, the CHD is the minimum number of bit changes required to change one bit vector into the other. The Extended Hamming distance (EHD) is also an edit distance, but the set of operations is extended with a shift operation, which has not received much attention in the string literature. By extending the operation set with the shift operation, we account for the notion of approximate matches, i.e, situations when corresponding bits in two bit vectors are considered aligned even when they are not in the exact same positions.

A Quick readme is available here.

A paper on the Extended Hamming distance and its application in robot vision is available from here.

The zip archive with the source code and documentation can be downloaded from here.


Back to Free Software Index

Kulyukin' Home Page