14
$\begingroup$

I have two lists as the following:

ab = {1, -1, -1, -1, 1, 1};
ac = {1, -1, -1,  1, 1, 1};

How I can find the difference (more precisely, the edit distance) between them? In this case the result should be 1, since there is one item difference between ab and ac.

Note: in my case, the list elements only take the values 1 and -1, and both lists are one-dimensional of the same length, but it is always nice to see more general solutions (elements are of Reals, lists are matrices, etc.).

Thank you.

$\endgroup$
  • 1
    $\begingroup$ Will you always deal in integers only? $\endgroup$ – Yves Klett Sep 6 '13 at 12:28
  • 1
    $\begingroup$ ... or even only 1 and -1? $\endgroup$ – Yves Klett Sep 6 '13 at 12:38
  • $\begingroup$ values are only 1 and -1 $\endgroup$ – sky-light Sep 6 '13 at 13:48
  • $\begingroup$ Then you are in for a treat (see answers)! Please edit your question to include the 1/-1 information. $\endgroup$ – Yves Klett Sep 6 '13 at 14:03
22
$\begingroup$

There is an appropriate metrics:

HammingDistance[ab, ac]
1

one could use also (but in general it yields different results since it counts transpositions, deletions etc.)

DamerauLevenshteinDistance[ab, ac]
1
$\endgroup$
  • $\begingroup$ Strangely HammingDistance doesn't work for mixed data i.e having both Integer and Symbols. $\endgroup$ – Rorschach Sep 6 '13 at 16:20
  • 1
    $\begingroup$ @Blackbird What problems have you encountered? How many should it be HammingDistance[{3, 2, a, 10, b, 5, 11, c}, {3, 2, a, 11, b, Pi, 11, 3}] ? 3, shouldn't it? $\endgroup$ – Artes Sep 6 '13 at 16:50
  • $\begingroup$ I am sorry for reading the definition in wrong way.My bad, you are correct. $\endgroup$ – Rorschach Sep 6 '13 at 18:05
  • 1
    $\begingroup$ @Blackbird Note that HammingDistance works also for strings (there is useful the IgnoreCase option) unlike the other methods. $\endgroup$ – Artes Sep 6 '13 at 18:31
16
$\begingroup$

For Integer data we also could write:

 Tr @ Unitize @ BitXor[ab, ac]
1

For Real data we can use the slightly slower but also shorter:

Tr @ Unitize[ab - ac]

Blackbird challenged me to provide a method that works on all input types. My approach is to select between methods depending on data.

diff[a__?(VectorQ[#, IntegerQ] &)] := Tr @ Unitize @ BitXor @ a
diff[a__?(VectorQ[#, NumericQ] &)] := Tr @ Unitize @ Subtract @ a
diff[a_, b_] := HammingDistance[a, b]

Timings for some of the methods posted so far (search the site for timeAvg):

{ab, ac} = List @@ RandomInteger[2, {2, 250000}];  (* List @@ to prevent unpacking *)

HammingDistance[ab, ac]                  // timeAvg
Count[MapThread[Equal, {ab, ac}], False] // timeAvg
Tr @ Unitize @ BitXor[ab, ac]            // timeAvg
diff[ab, ac]                             // timeAvg

0.009984

0.05428

0.0005488

0.0005744

Now with Real data:

{ab, ac} = N /@ {ab, ac};

HammingDistance[ab, ac]                  // timeAvg
Count[MapThread[Equal, {ab, ac}], False] // timeAvg
Tr @ Unitize[ab - ac]                    // timeAvg
diff[ab, ac]                             // timeAvg

0.01872

0.0748

0.00312

0.0021728

(I learned something from this test: Subtract[a,b] is faster than a-b on packed reals.)

Now something unpackable:

{ab, ac} = RandomChoice[CharacterRange["a", "z"], {2, 250000}];

HammingDistance[ab, ac]                  // timeAvg
Count[MapThread[Equal, {ab, ac}], False] // timeAvg
diff[ab, ac]                             // timeAvg

0.005488

0.0524

0.005496

$\endgroup$
  • 3
    $\begingroup$ I knew this was one of those explode-in-your-face threads ;P $\endgroup$ – Yves Klett Sep 6 '13 at 12:25
  • $\begingroup$ @Yves Please define that. $\endgroup$ – Mr.Wizard Sep 6 '13 at 12:30
  • $\begingroup$ Simple/trivial question, one gazillion possible (and sometimes surprising and/or creative) answers. Oh, and my timings are usually abysmal... $\endgroup$ – Yves Klett Sep 6 '13 at 12:31
  • $\begingroup$ @Yves Ah, one of those. $\endgroup$ – Mr.Wizard Sep 6 '13 at 12:35
  • $\begingroup$ Is the term unsuitable / lost in translation? $\endgroup$ – Yves Klett Sep 6 '13 at 12:38
9
$\begingroup$

You could do this

ab = {1, -1, -1, -1, 1, 1};
ac = {1, -1, -1, 1, 1, 1};

EditDistance[ab, ac]

which would give a result even if the lists had different lengths (or whatever).

The documentation says:

EditDistance[u, v] gives the number of one-element deletions, insertions, and substitutions required to transform u to v.

$\endgroup$
  • $\begingroup$ I'm sorry, I have to down-vote this. EditDistance is not the same thing. Incidentally it is a far more complex measure and will be unusably slow on long vectors. $\endgroup$ – Mr.Wizard Sep 6 '13 at 17:03
  • 1
    $\begingroup$ The OP said “How I can find the difference between them? Now in our case the result should be 1, since there is one item difference between ab and ac.”, which is such a loose definition of “difference” that EditDistance is a feasible candidate. Though I agree with your comment about complexity. $\endgroup$ – Stephen Luttrell Sep 7 '13 at 11:40
  • 1
    $\begingroup$ Okay, I have to admit you're right. My impression of the question didn't allow for that but I was wrong. I removed my down-vote (I had to edit to do this). $\endgroup$ – Mr.Wizard Sep 7 '13 at 11:45
8
$\begingroup$

A very basic approach:

Count[Equal @@@ Thread[{ab, ac}], False]

1

or perhaps:

Count[MapThread[Equal, {ab, ac}], False]

1

Now if there is only 1 and -1 to watch out for, this will also do (thanks to Aky for pointing out a glaring error):

Plus @@ Abs[ab - ac]/2
$\endgroup$
  • 2
    $\begingroup$ You don't need Thread in the last one: Tr[ab-ac]/-2 $\endgroup$ – Mr.Wizard Sep 6 '13 at 12:43
  • 1
    $\begingroup$ It is too short for the answer so maybe you can add Count[ab ac, -1] somewhere for 1/-1 data case. $\endgroup$ – Kuba Sep 6 '13 at 12:59
  • 1
    $\begingroup$ @Kuba good one! You sure you do not want to answer yourself? $\endgroup$ – Yves Klett Sep 6 '13 at 13:01
  • 1
    $\begingroup$ @Kuba Short is the best kind of answer. I encourage you to post it. :-) $\endgroup$ – Mr.Wizard Sep 6 '13 at 13:07
  • 2
    $\begingroup$ @Mr.Wizard now you see what I meant by "explode in your face" :-) $\endgroup$ – Yves Klett Sep 6 '13 at 13:42
7
$\begingroup$

These results are specific to the case where the data are 1|-1, and may be specific to v6.

<<Developer`
n = 10^7
PackedArrayQ[ a = RandomInteger[1,n]*2 - 1 ]
PackedArrayQ[ b = RandomInteger[1,n]*2 - 1 ]
(* 10000000
   True
   True *)

AbsoluteTiming[ (Length@a - a.b)/2  ]
(* {0.435134, 4998582} *)

AbsoluteTiming[ Tr@Unitize@Subtract[a,b] ]
(* {0.792662, 4998582} *)

AbsoluteTiming[ Tr@Unitize@BitXor[a,b] ]
(* {0.883002, 4998582} *)

aa = FromPackedArray@a;
bb = FromPackedArray@b;

AbsoluteTiming[ (Length@aa - aa.bb)/2  ]
(* {1.373384, 4998582} *)

AbsoluteTiming[ Tr@Unitize@Subtract[aa,bb] ]
(* {1.366143, 4998582} *)

AbsoluteTiming[ Tr@Unitize@BitXor[aa,bb] ]
(* {2.590419, 4998582} *)
$\endgroup$
  • $\begingroup$ I get the same rankings in v7. I hadn't realized that Subtract was faster than BitXor. $\endgroup$ – Mr.Wizard Sep 7 '13 at 11:50
  • $\begingroup$ Ah, I see now that it's only faster on this data, not general Integer data. Nevertheless +1 well earned for teaching me something. $\endgroup$ – Mr.Wizard Sep 7 '13 at 11:58
6
$\begingroup$

I will abuse the fact that OP hasn't said if it is more general question.

This is my solution fo 1/-1 data case:

Count[ab ac, -1]
$\endgroup$
  • $\begingroup$ @YvesKlett Here is another fun one for -1/1: Tr@Log[ab ac]/I/Pi $\endgroup$ – Mr.Wizard Sep 6 '13 at 13:16
  • 1
    $\begingroup$ @Mr.Wizard If we a priori know the Length then this one is shorter: (n - ab.ac)/2 $\endgroup$ – Kuba Sep 6 '13 at 13:20
  • $\begingroup$ @Mr.Wizard, you could save one character with Tr@Log[-1, ab ac] $\endgroup$ – Simon Woods Sep 7 '13 at 12:25

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.