Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I have two lists as the followings:

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.

share|improve this question
1  
Will you always deal in integers only? –  Yves Klett Sep 6 '13 at 12:28
1  
... or even only 1 and -1? –  Yves Klett Sep 6 '13 at 12:38
    
values are only 1 and -1 –  barznjy Sep 6 '13 at 13:48
    
Then you are in for a treat (see answers)! Please edit your question to include the 1/-1 information. –  Yves Klett Sep 6 '13 at 14:03

6 Answers 6

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
share|improve this answer
    
Strangely HammingDistance doesn't work for mixed data i.e having both Integer and Symbols. –  Rorschach Sep 6 '13 at 16:20
1  
@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? –  Artes Sep 6 '13 at 16:50
    
I am sorry for reading the definition in wrong way.My bad, you are correct. –  Rorschach Sep 6 '13 at 18:05
1  
@Blackbird Note that HammingDistance works also for strings (there is useful the IgnoreCase option) unlike the other methods. –  Artes Sep 6 '13 at 18:31

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

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

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.

share|improve this answer
    
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. –  Mr.Wizard Sep 6 '13 at 17:03
    
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. –  Stephen Luttrell Sep 7 '13 at 11:40
    
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). –  Mr.Wizard Sep 7 '13 at 11:45

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} *)
share|improve this answer
    
I get the same rankings in v7. I hadn't realized that Subtract was faster than BitXor. –  Mr.Wizard Sep 7 '13 at 11:50
    
Ah, I see now that it's only faster on this data, not general Integer data. Nevertheless +1 well earned for teaching me something. –  Mr.Wizard Sep 7 '13 at 11:58

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

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]
share|improve this answer
    
@YvesKlett Here is another fun one for -1/1: Tr@Log[ab ac]/I/Pi –  Mr.Wizard Sep 6 '13 at 13:16
1  
@Mr.Wizard If we a priori know the Length then this one is shorter: (n - ab.ac)/2 –  Kuba Sep 6 '13 at 13:20
    
@Mr.Wizard, you could save one character with Tr@Log[-1, ab ac] –  Simon Woods Sep 7 '13 at 12:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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