Hamming Distance (HD) has been used to measure the distance of two numbers when they are converted into binary representations. e.g., $Ham(1, 2)=2$ as 0001'XOR'0010'='0011' while $Ham(128, 1)$ equals $2$ as well. Here we see HD does not work well as it falsely indicates that the distance between $1$ and $2$ is equal to the distance between $1$ and $128$.

So my question is if there are any other distance measurement methods (or encoding methods) that can deal with this issue?


Nothing is falsely indicated there!

The Hamming distance is between strings (vectors) of the same length in the space $\{0,1\}^n. $ However the integer representation of such vectors is in a different space and the distance there is different.

Besides integer distance $|x-y|$ between two integers you can have minimal cyclic distance $$\min \{|x-y|,|n-x+y|\}$$ for two elements modulo $n.$

Note Some such distances won't be a metric. The triangle equality or symmetry may be violated.

More generally since polynomials are also widely used in Crypto, you could have metrics depending on the Hamming distance of their truth tables, or value tables if non-binary.

Or the minimal degree of two polynomials minus the number of common roots they have.

Edit: Or edit distance (levenshtein distance) which is usually defined as the minimal number of $$(insertions+ deletions+substitutions)$$ required to map a string of length $m$ to a string of length $n$ where $n=m$ is not needed. Sometimes, a weight is put on the different operations and weighted cost is minimized.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.