I need to make the calculation of the HammingDistance
for strings faster. The background is that I want to be able to compare the similarity of images of a textual database. (The similarity of two images can be calculated as nicely explained in Efficient way to compare animated images to tell if they are the same). In any event, the database consists of a list of image-names and the corresponding hash-values. While it is possible to store a binary version of the data in the database, I prefer a textual representation e.g. in a text file using IntegerString with a base of 36 to get the shortest textual representation (in terms of digits) of a numeric integer value.
Of course for calculating the HammingDistance
I could convert the hashstrings back to numeric values and implement the methods described in Fastest way to measure Hamming distance of integers. However, there are two issues:
- Since a Mathematica-compiled function cannot act on Strings, I need to convert the String to a numeric value. On average the hash-values have around 250 digits in their decimal representation, so I would need to combine the approaches described in Faster binary Hamming weight for big integers? and Fastest way to measure Hamming distance of integers, while
- I am a total newbie regarding compiling and calling external C-functions from Mathematica, so I understand less than half of what Oleksandr R. is doing in both threads, and unfortunately I have not enough reputation to comment in those threads directly.
Therefore, since HammingDistance
as it is implemented in Mathematica can evaluate directly Strings I am really wondering if there is not a faster way using some fast C compiled code from within Mathematica. If not I would be also happy with some step-by-step explanation on how to implement the C-code of Oleksandr. R. inside Mathematica.
(I got gcc and Visual Studio 2015 installed and succeeded also with getting Mathematica to recognize the VS compiler as described in C compilation not working with Visual Studio 2013)
Thank you for any suggestions or solutions!
@Marius: For approximately 16000 image-name/hashvalue-pairs the comparison takes on average 36 min. I would like to get the time down to less than a minute, as everything longer is not practicable.
For the comparison process I use a While
-Loop I am using for comparing a single image hash with the 16000 hashes from the textual database. Inside the while loop is only the code
While[j <= Length[FileHashTab], {
AppendTo[
vec, {FileHashTab[[j, 1]],
If[StringLength@ImgHash == StringLength@FileHashTab[[j, 2]],
HammingDistance[ImgHash, FileHashTab[[j, 2]]],
Infinity]}];
j = j + 1;
}]
with
FileHashTab={{ImgName,ImgHash},{...,...},...}
vec={};
so vec
is used for collecting the filenames with the corresponding hashdistance to the ImgHash
of the image I want to compare.
The interesting point is that the memory usage is really small and the CPU (i5 - 4 cores) is only loaded only with about 20%...
HammingDistance
is the bottleneck? Can you give some small example sets whereHammingDistance
is slow? $\endgroup$ – Marius Ladegård Meyer Sep 23 '16 at 12:29HammingDistance
took just7x10^-6
seconds. $\endgroup$ – C. E. Sep 23 '16 at 20:13AppendTo
, which leads to quadratic time complexity in the length of the array, here 16000. Since you are collecting all terms here, just use aTable
, no need for aWhile
. If you later want to only collect an unknown number of elements, look upReap
andSow
. But why do you need to collect them all, even the ones whoseHammingDistance
you manually set toInfinity
? $\endgroup$ – Marius Ladegård Meyer Sep 23 '16 at 21:21HammingDistance
. I'm a little disturbed by the thought of someone in the future having to read through all of this text to figure out if what's written here can help him with his problems withHammingDistance
. $\endgroup$ – C. E. Sep 25 '16 at 13:22