How can I extract similarities/patterns from a collection of binary strings?

Question

I have a collection of binary strings of given size encoding effective solutions to a given problem.

By looking at them, I can spot obvious similarities and intuitively see patterns of symmetry and periodicity.

Are there mathematical/algorithmic tools I can "feed" this set of strings to and get results that might give me an idea of what this set of strings have in common?

By doing so I would be able to impose a structure (or at least favor some features over others) on candidate solutions in order to greatly reduce the search space, maximizing chances to find optimal solutions for my problem (I am using genetic algorithms as the search tool - but this is not pivotal to the question).

Any pointers/approaches appreciated.

Answer 1

Pattern recognition is a broad subject. If your strings have a small alphabet then perhaps some of the DNA matching algorithms would be applicable.

Of Interest?:

http://bio.informatics.indiana.edu/sunkim/c/s06/I690/aomtp.pdf

http://etd.ohiolink.edu/send-pdf.cgi/Frey%20Jeffrey%20Daniel.pdf?kent1208961242

http://www.cs.ucr.edu/~stelo/cpm/cpm09/04_fl09.pdf

http://www.iaeng.org/IJCS/issues_v34/issue_2/IJCS_34_2_03.pdf

Answer 2

You need to take a look in unsupervised clustering algorithms such as:

• Hierarchical Clustering
• k-Nearest Neighbours
• k-Means

Since they're binary strings, something simple such as Huffman Coding might work (only if you have a bit number of strings so you can estimate bit frequencies).

All of this methods are described in any Pattern Recognition / Machine Learning text worthy of that tag. The classic textbook is Duda, Stork & Hart: http://rii.ricoh.com/~stork/DHS.html

To use all of this methods you'll need some similarity measure between strings. If they are binary, you can start with the simplest thing: counting the numer of different bits in each string.