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