Suppose you are given two sequences (or lists), l1 and l2, and now you would like to compare how much l1 is different from l2. How would you compare them, quantitatively?
There are many metrics to compare two sequences like l1 and l2, though the focuses are not always the same. Some compare the bag of elements contained by each sequence. Others may care more about the oscillation pattern within each sequence. There may even be someone simply compares the length difference of the two sequences.
We will, in the second half of this post, put our explanation in a scenario of natural language processing. However, comparing difference between discrete sequences (instead of vectors) could be a broader headache. You may have compared your Monday course schedule with your friends in another class, and noticed that they are different. Or you may have compared your recent phone call history with some other person’s, and noticed that they are, of course, different. Or you may also have compared sequence of book arrangement on the top level of your bookshelf with some other person’s book arrangement, and noticed that they are different. Many such sequences can be compared, and difference can be seen. But, how do you measure the difference?
Suppose you have had your books arranged in the manner of l1 on the top level of your bookshelf. From left to right, they look like below:
l1 = [A, 3, 8, Y, U, &, 5, 5, H]
Yes, you have only nine books, and among them there is a duplicated ‘5’. These nine books have fully occupied your narrow bookshelf’s top level, and each of them is with the same thickness. This means you could only put nine books on this level.
One day, your friend Lucy visited your study, and noticed your arrangement l1. Lucy was particularly attracted (… well somehow…) by l1. She went back her own home and planned to duplicate l1 in her study. Lucy has an infinitely wide bookshelf top level, but she only wanted to utilize nine slots, because she was to duplicate l1. She took a look at her top level bookshelf, there are some books already arranged there, in sequence l2. Though not necessarily different from l1, l2 looks like this:
l2 = [G, 3, U, Y, Y, H, T, #, 5, F, L, T, 0, K]
Lucy has 14 books on her top level.
Lucy wants to modify her l2 to make it an l1. What should she do?
There are some books {A, 8, &} missing, so she has to buy them beforehand. Particularly, she also needs one more ‘5’, as there are two occurrence of ‘5’ in l1.
Therefore, Lucy bought a bag of books {&:1, 8:1, 5:1, A:1} and leave the bag on her desk. Then she realized that besides collecting missing books, she needs to remove the excessive books {G, Y, T, #, F, L, T, 0, K} from her top level of shelf.
After the above preparation, Lucy started to rearrange the books.
How many steps would she need to rearrange l2 to l1? Or what could be the fastest, most straightforward way? The answer is to take all books off the shelf and put each one back on according to l1. However, by doing that, Lucy would need a desk large enough to accommodate all her 18 books (14 original one + 4 newly bought). She did not want to do that, as she just wanted to use a tiny space on her desk. (please, please don’t ask me why she does not use her ‘infinitely wide bookshelf’ :) This is because she decided to only utilize nine slots, as you had l1.)
Thus, Lucy’s rearranging strategy was to take off as few books as possible, and put on the correct ones back. Therefore, she may need a few more steps to reach the final arrangement same as l1.
Did she make it?
Yes, of course, and there are many solutions. Some take more steps, some take not as many. Some lead 10 books scattered on the desk, some may only require 9 to be there. But, none of the solutions will use fewer than 9 units of space on desk, as after all Lucy has only nine books on the shelf eventually.
We are coming to the end of Lucy’s story with her bookshelf.
Though she made it, and successfully changed l2 to something same as l1, we may want to find her a best solution, that uses least steps, and occupies least space on her desk. This optimal solution indicates the least cumbersome way to change l2 to l1. By looking for this optimal solution, we can say that we found a definition of ‘distance from l2 to l1.’ So it is with ‘distance from l1 to l2’ if we reverse the steps of this optimal solution.
Now, we found a way to measure the distance between two sequences. The pattern is that: the more steps used, the larger the distance would be; the more space used, the larger the distance would be. (However, how to integrate time and space is another issue, we may simply multiply one with another, or we can use sum of space at each time step.)
Hold on, how would we help Lucy to find an optimal solution? Is there a deterministic algorithm?
See you in the next section ><
