# Calculating similarity between bit strings/signal

I have a project I'm working on where I'm trying to efficiently compare sequences of binary data to determine how similar they are. Basically, a sequence might look like this: 1001010010100011110...

I spent a while on my own trying to come up with a way to do it because it's fun for me to work through problems like this on my own, and actually made some progress. Unfortunately, everything I came up with never quite worked; a solution that accounts for substitutions (bits that flip) is easy, but what keeps getting me is handling bits that are inserted or deleted, i.e.: 100101 -> 1000101

Trying to find a solution online keeps leading me here, and I keep coming across the term cross-correlation. I also see lots of interesting links on the wikipedia page for Time Series for calculating similarities. Unfortunately, at the moment, a lot of the math is unclear to me, and I can't efficiently go through and distinguish what the appropriate technique might be for my situation.

So I have two different approaches to my problem that I'm interested in learning about:

1) What method would you recommend for calculating the similarity between two bit sequences (typically 50 to 150 bits in length) that is robust to substitutions, insertions, and deletions?

2) I'm not sure this is possible, but is there some kind of distance metric(s) I can calculate independently for each signal that will allow me to group them together with actually doing direct pairwise comparisons?

For 1, I feel like cross-correlation might be the right approach, but I haven't gotten past just plugging sequences in R and seeing how it works for identifying lag. I know edit distance will work, but ultimately will want something more efficient. Eventually, I will be trying to group billions of these together.

Thanks

• Have you looked at en.wikipedia.org/wiki/Levenshtein_distance?
– MBaz
Dec 2 '15 at 22:42
• I've come across it in bioinformatics where it's used to compare genetic sequences, but I was hoping that because my data is purely numeric and simpler than the case of comparing character strings, that there is a more direct mathematical approach. Ultimately, I think I could adjust that method to be more efficient for my particular case, but I'm less sure that I will be able to adapt it for use in GPGPU computing using OpenCL, which is my goal down the line. Dec 3 '15 at 3:04