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 1243784:[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 6Concatenating to strings:12555 vs 127773: replace 5 with 7 at position 3, replace 5 with 7 at position 4, and replace 5 with 7 at position 5.12556 vs 127783: replace 5 with 7 at position 3, replace 5 with 7 at position 4, and replace 6 with 8 at position 5.12555 vs 347775: 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 3473: replace 1 with 3 at position 1, replace 2 with 4 at position 2, and replace 5 with 7 at position 3.12556 vs 347785: 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 12231: insert 2 at position 1.12345666vs 124367775: 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 0010027773: replace 5 with 7 at position 7, replace 5 with 7 at position 8, and replace 5 with 7 at position 9.001002556 vs 0010027783: replace 5 with 7 at position 7, replace 5 with 7 at position 8, and replace 6 with 8 at position 9.001002555 vs 0030047775: 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 0030047785: 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.001002003004005666vs 0010020040030067776: 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 124378Here is the algorithm for comparing 123456 vs 124378 strings in details (positions starts from 0):123456  - 1st string1243456 - 1. inserted 4 at position 21243756 - 2. replaced 4 with 7 at position 41243786 - 3. replaced 5 with 8 at position 5124378  - 4. deleted 6 at position 6The Levenshtein distance is 4Here 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 6The Levenshtein distance is 4If 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 string1245666  - 1. deleted 3 at position 21243666  - 2. replaced 5 with 3 at position 31243676  - 3. replaced 6 with 7 at position 51243677  - 4. replaced 6 with 7 at position 612436777 - 5. inserted 7 at position 7The Levenshtein distance is 5
Levenshtein distance cabable working with (large) vectors - not strings
algorithms;strings;string metrics