Levenshtein distance cabable working with (large) vectors - not strings

Question

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

Answer 1

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.