5
$\begingroup$

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%...

$\endgroup$
  • 3
    $\begingroup$ How much faster do you need? How slow is it now? Are you sure HammingDistance is the bottleneck? Can you give some small example sets where HammingDistance is slow? $\endgroup$ – Marius Ladegård Meyer Sep 23 '16 at 12:29
  • $\begingroup$ For approximately 16000 image-name hashvalue pairs the comparison takes on average 36 min. 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. $\endgroup$ – Quit007 Sep 23 '16 at 14:18
  • $\begingroup$ You have to give us something so that we can reproduce your issue, otherwise we cannot help. I generated two different hashes, each of length 256, and to apply HammingDistance took just 7x10^-6 seconds. $\endgroup$ – C. E. Sep 23 '16 at 20:13
  • $\begingroup$ In Mathematica, the full array is copied on each AppendTo, which leads to quadratic time complexity in the length of the array, here 16000. Since you are collecting all terms here, just use a Table, no need for a While. If you later want to only collect an unknown number of elements, look up Reap and Sow. But why do you need to collect them all, even the ones whose HammingDistance you manually set to Infinity? $\endgroup$ – Marius Ladegård Meyer Sep 23 '16 at 21:21
  • 1
    $\begingroup$ Maybe you can rewrite your question now that you know it has nothing to do with HammingDistance. 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 with HammingDistance. $\endgroup$ – C. E. Sep 25 '16 at 13:22
6
$\begingroup$

Thanks to all of the above comments I finally arrived at a solution for me which is probably not yet the fastest possible but suitable for me. Where I got it wrong was the While posted above that integrated in outer While-loop as I wanted to compare every element of the database with all other elements:

While[i <=Length[FileHashTab], {
j=i+1;
    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;
      }]
i=i+1;
}]

I found out that the first runs for i are really fast (even for 16000 elements) but as i progresses further the calculation starts to continuously slow down (although it should rather speed up due to decreasing number of elements that are being compared with each other). (Probably due to the Complexity of AppendTo as pointed out by Marius which I wasn't aware of)

Anyway I tried to get rid of the inner While-loop in a way that I make an array of two lists where one contains the all elements of the database (which is a 2dim-Array) from a starting element to the end and the other is a ConstantArray of the hashvalue I want to compare with the rest of the elements. To get everything sorted out properly I defined first some functions:

compIfHammingDist[hashTwoElememtsForDist_List] := 
If[StringLength@hashTwoElememtsForDist[[1]] == StringLength@hashTwoElememtsForDist[[2]], 
HammingDistance[hashTwoElememtsForDist[[1]], hashTwoElememtsForDist[[2]]], Infinity]

ConstructComparisonList[Liste_List, AbElementBisEnde_]:=
Module[{RunningList, ConstantList},
RunningList = Take[Liste, (AbElementBisEnde) - Length[Liste]];
ConstantList =  ConstantArray[Liste[[AbElementBisEnde]], Length[RunningList]];
Transpose[{ConstantList, RunningList}]]

(*remember the FileNameHashTabelle is structured as {{fileName,hashValue},{...,...},...}*)
FileNamesWithHashDist[FileNameHashTabelle_,AbElementBisEnde_] := {       
FileNameHashTabelle[[AbElementBisEnde, 1]],  
    Transpose[{
        Take[Transpose[FileNameHashTabelle][[1]], AbElementBisEnde - Length[FileNameHashTabelle]], 
        compIfHammingDist[#]& /@ ConstructComparisonList[Transpose[FileNameHashTabelle][[2]], AbElementBisEnde]
     }]}

SelectBelowThreshold[MeasuredFileDistValues_, SimilarityThreshold_]:= 
Module[{messung},
   messung = Select[MeasuredFileDistValues[[2]], #[[2]] < SimilarityThreshold &];
   If[Length[messung] != 0, Flatten[{MeasuredFileDistValues[[1]], Transpose[messung][[1]]}],Nothing]
]

The main happens in here where I still use While and AppendTo but not any more in a double loop. Furthermore I apply also at this point the Threshold to keep only sufficiently similar images in order to keep the Memory usage down:

measureImgFileDistanceAndApplyThreshold[FileHashTab_,SimilarityThreshold_]:= 
Module[{ImgNames, HashValues, vec = {}, i = 1},
   PrintTemporary[Monitor[
     While[i <= Length[FileHashTab] - 1, {
       AppendTo[vec, 
       SelectBelowThreshold[FileNamesWithHashDist[FileHashTab, i], SimilarityThreshold]];
     ++i;
     }],
 Row[{ProgressIndicator[i, {1, Length[FileHashTab]}], i}, " "]]];
vec
];

This way it the first calculation take 0.25 s for the whole hashtable on my machine and the further it progresses the faster it gets, so HammingDistance was obviously in spite of the large numbers not at all the limiting factor.

$\endgroup$
  • $\begingroup$ Great self-answer! I would love to see more of this on this site. $\endgroup$ – Marius Ladegård Meyer Sep 26 '16 at 7:59

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.