0
$\begingroup$

Long version:

Is there any algorithm similar to Levenshtein distance which can compare vectors? I will post several examples with desired inputs/outputs and then I will also show that it is not the same as if the vectors are (prefixed with zeros) concatenated to strings and then Levenshtein is computed:

Desired inputs/outputs:

[1, 2, 555] vs [1, 2, 777]
1: replace 555 with 777.

[1, 2, 556] vs [1, 2, 778]
1: replace 556 with 778.

[1, 2, 555] vs [3, 4, 777]
3: replace 1 with 3, replace 2 with 4, replace 555 with 777.

[1, 2, 5] vs [3, 4, 7]
3: replace 1 with 3, replace 2 with 4, replace 5 with 7.

[1, 2, 556] vs [3, 4, 778]
3: replace 1 with 3, replace 2 with 4, replace 556 with 778.

[1, 2, 3] vs [1, 2, 2, 3]
1: insert 2 at position 1.

[1, 2, 3, 4, 5, 666] vs [1, 2, 4, 3, 6, 777] # same as e.g.: "123456" vs "124378"
4:
[1, 2, 4, 3, 4, 5, 666] - inserted 4 at position 2
[1, 2, 4, 3, 6, 5, 666] - replaced 4 with 6 at position 4
[1, 2, 4, 3, 6, 5, 666] - replaced 5 with 777 at position 5
[1, 2, 4, 3, 6, 5]      - deleted 666 at position 6

Concatenating to strings:

"12555" vs "12777"
3: replace 5 with 7 at position 3, replace 5 with 7 at position 4, and replace 5 with 7 at position 5.

"12556" vs "12778"
3: replace 5 with 7 at position 3, replace 5 with 7 at position 4, and replace 6 with 8 at position 5.

"12555" vs "34777"
5: replace 1 with 3 at position 1, replace 2 with 4 at position 2, replace 5 with 7 at position 3, replace 5 with 7 at position 4, and replace 5 with 7 at position 5.

"125" vs "347"
3: replace 1 with 3 at position 1, replace 2 with 4 at position 2, and replace 5 with 7 at position 3.

"12556" vs "34778"
5: replace 1 with 3 at position 1, replace 2 with 4 at position 2, replace 5 with 7 at position 3, replace 5 with 7 at position 4, and replace 6 with 8 at position 5.

"123" vs "1223"
1: insert 2 at position 1.

"12345666"vs "12436777"
5: delete 3 at position 3, replace 5 with 3 at position 5, replace 6 with 7 at position 7, replace 6 with 7 at position 8, and insert 7 at position 8.

Padding zeros to get same element size and concatenating to strings:

"001002555" vs "001002777"
3: replace 5 with 7 at position 7, replace 5 with 7 at position 8, and replace 5 with 7 at position 9.

"001002556" vs "001002778"
3: replace 5 with 7 at position 7, replace 5 with 7 at position 8, and replace 6 with 8 at position 9.

"001002555" vs "003004777"
5: replace 1 with 3 at position 3, replace 2 with 4 at position 6, replace 5 with 7 at position 7, replace 5 with 7 at position 8, and replace 5 with 7 at position 9.

"001002556" vs "003004778"
5: replace 1 with 3 at position 3, replace 2 with 4 at position 6, replace 5 with 7 at position 7, replace 5 with 7 at position 8, and replace 6 with 8 at position 9.

"001002003004005666"vs "001002004003006777"
6: replace 3 with 4 at position 9, replace 4 with 3 at position 12, delete 5 at position 15, replace 6 with 7 at position 17, replace 6 with 7 at position 18, and insert 7 at position 18.

PS: There are various vector distances, but according to my quick research they are all variations of Euclidean distance (they works with vector's elements at same position but does not account with deletion, insertion, substitution).

PPS: Some working implementation instead of pseudo code or paper would be useful (preferably in python, perl, R but whatever language would be fine) There are also various implementation of Levenshtein and some of them are pretty fast (according to my understanding they are storing only result and not how the result was computed). So I would like to have as fast as possible algorithm. Thank you very much.

Short version:

I need algorithm which will compute Levenshtein distance for those two vectors [1, 2, 3, 4, 5, 666] vs [1, 2, 4, 3, 6, 777] in simmilar way as if it would e.g. for those two strings "123456" vs "124378"

Here is the algorithm for comparing "123456" vs "124378" strings in details (positions starts from 0):

"123456"  - 1st string
"1243456" - 1. inserted 4 at position 2
"1243756" - 2. replaced 4 with 7 at position 4
"1243786" - 3. replaced 5 with 8 at position 5
"124378"  - 4. deleted 6 at position 6
The Levenshtein distance is 4

Here is my desired algorithm for vectors [1, 2, 3, 4, 5, 666] vs [1, 2, 4, 3, 6, 777] in details (positions starts from 0):

[1, 2, 3, 4, 5, 666]      - 1st vector
[1, 2, 4, 3, 4, 5, 666]   - 1. inserted 4 at position 2
[1, 2, 4, 3, 6, 5, 666]   - 2. replaced 4 with 6 at position 4
[1, 2, 4, 3, 6, 777, 666] - 3. replaced 5 with 777 at position 5
[1, 2, 4, 3, 6, 777]      - 4. deleted 666 at position 6
The Levenshtein distance is 4

If I create strings from vectors [1, 2, 3, 4, 5, 666] and [1, 2, 4, 3, 6, 777] I get "12345666" and "12436777". But Levenshtein distance on this strings is different to what I want (see above vector example).

Here is the algorithm for comparing "12345666" vs "12436777" strings in details (positions starts from 0):

12345666 - 1st string
1245666  - 1. deleted 3 at position 2
1243666  - 2. replaced 5 with 3 at position 3
1243676  - 3. replaced 6 with 7 at position 5
1243677  - 4. replaced 6 with 7 at position 6
12436777 - 5. inserted 7 at position 7
The Levenshtein distance is 5
$\endgroup$
  • $\begingroup$ There are lots of algorithms for comparing vectors. What properties do you want it to have? How do you plan to evaluate a proposed answer? Why have you rejected Levenshtein distance? Asking for a list of all such algorithms would be too broad. Also, a list of examples is not a substitute for a specification of what properties you want it to have or an information description of what you're trying to achieve. (And reading through a long list of examples sounds a bit tedious to me, so might not get you the best possible answers.) $\endgroup$ – D.W. Apr 27 '16 at 20:36
  • $\begingroup$ Finally, I don't understand how to interpret your examples nor how they show that Levenshtein distance fails to achieve what you want. $\endgroup$ – D.W. Apr 27 '16 at 20:38
  • $\begingroup$ @D.W. I'm not rejecting Levenshtein distance. Maybe we misunderstood but I'm searching for Levenshtein which can work with vectors. I have multiple files where each line contain numbers from 1 ~ 500 (this is why I need to treat e.g. 347 as one element and not as string composed of 3,4,7 because 3,4,7 are another separate numbers). Those files has ~ 250000 lines. And I want to know how similar those files are to each other. $\endgroup$ – Wakan Tanka Apr 27 '16 at 20:40
  • $\begingroup$ I suggest editing the question to make it clearer what you're asking and what you're trying to achieve. I find your long list of "examples" hard to follow, as there's no accompanying explaination -- it's just a copy-paste of stuff that I'm sure makes sense to you but didn't mean much to me. Do you really need so many examples? Could you list just one example, and rather than copy-pasting input/output, provide some explanation of what is going on? Rather than trying to clarify in the comments, it'd be better to edit the question. Thanks! $\endgroup$ – D.W. Apr 27 '16 at 20:42
  • $\begingroup$ @D.W. I've edited the question. Hope that it is clear now and I did not make typo somewhere. Thank you. $\endgroup$ – Wakan Tanka Apr 27 '16 at 21:40
1
$\begingroup$

Don't convert the numbers to decimal digits and then concatenate. Instead, just use the sequence of numbers directly. The Levenshtein distance can be used on any sequence, not just a sequence of characters.

Formally, the Levenshtein distance can be used to compute the similarity of two elements of $\Sigma^*$, where $\Sigma$ is some alphabet. Normally for strings we let $\Sigma$ be the set of characters. However, in this case you can take $\Sigma=\mathbb{Z}$ (the set of all integers), so that each element of $\Sigma^*$ is just a sequence of integers. Now you can apply the Levenshtein edit distance directly to two sequences of integers, without doing any kind of conversion to decimal, concatenation of digits, or zero padding.

$\endgroup$

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.