Searching for degree of similarity is not a completely trivial task. In a sense, you want to describe the distance between two "words" or sequences of characters as a number in some way.
One idea might be to consider PAIRS of consecutive characters. For example, suppose we allow any combination of upper case, lower case, numbers, and a space.
Clist = ['A':'Z','a':'z','0:9',' '];
That represents the universe of things we will care about. I suppose I could add in punctation, etc., but that will do for here.
Now, consider all possible combinations of two consecutive elements from that set.
[C1,C2] = meshgrid(Clist);
So there are 3136 possible 2 character combinations from that set. Now think of the two sequences: 'ABC123' and the sequence '3ABC12'. They have exactly the same set of characters, but in a slightly different sequence, since the 3 is in a different place.
We can use the above set of 2 character sequences to compute the distance between a pair of strings. For example, comare 'ABC123' to 'B1A3C2'. Again, the same numbers and letters, but in a very different sequence here. The previous pair would be seen to have a much smaller distance. I'd suggest a simple scheme. Look at the pairs of consecutive elements of each sequence, and count the num,ber of times a pair is seen in BOTH sequences, so look for overlap of two character sub-sequences. That is, we have these three sequences:
'ABC123' ~ {'AB', 'BC', 'C1', '12', '23'}
'3ABC12' ~ {'3A', 'AB', 'BC', 'C1', '12'}
'B1A3C2' ~ {'B1', '1A', 'A3', '3C', 'C2'}
I've broken them each into 2 digit subsquences. See that 'AB' occurs in BOTH sequences 1 and 2. Similarly, 'BC' also appears in both cases. In fact, 4 of those 5 sequences of 2 characters appear in BOTH sequences 1 and 2. Compare that instead to sequences 1 and 3. There we see NO 2 character subsequences that are the same. So we could define a distance between two sequences in terms of the number of 2 character subsequences they have in common.
You should see this uses the order of characters as an important factor. It would be quite doable, and give you a simple measure of distance. You could add more information into such a measure, but this would gve you a start.
