A package for quickly determining the similarity between two sequences of bits

Question

I need to compare a sequence of query bits with a database to millionths of bits. All bit sequences are 100 bits long. I need the search as fast as possible. Are there any packages to quickly determine the similarities between two bit sequences? --Edit-- Bit sequences are position sensitive.

I saw a possible Twiddling Hacks bit algorithm , but if there is a ready-made package that will be better.

Answer 1

If the database is fairly static, you may need to build a tree data structure on it.

Search a tree recursively or in multiple threads, and the actual variable is stored for each search. If the actual difference becomes larger than what you think is “similar,” interrupt the search.

eg. Suppose we have the following tree:

      root
   0       1
 0   1   0   1
0 1 0 1 0 1 0 1

If you want to search for patterns similar to 011 and only want to allow a maximum of 1 bit, do a search like this (recursively or multithreaded):

• Start from the root
• Take the left branch (0), it looks like so the difference is still 0
  • Take the left branch (0), this is different, so the difference becomes 1, which is still acceptable
    • take the left branch (0), it's different, so the difference becomes 2, which is too big. Cancel the search in this thread.
    • (1), , 1, ( ).
  • (1), , 0,
    • (0), , 1, , .

, .

, .

, 64- .

Answer 2

, , 50 , , ( ), , :

• .
• multi_map ( STL, Java, , )

:

• 2 : , , , ( , , , "" )
• , , N
• multimap N, , .
• N. , . , /, .
• N-1, 1 .
• N-1. 1, . , /, .
• N + 1
• / , -, 1. , / .

2, 3,... .

, , , , %.

, , . , , , , , , .

, .

Answer 3

.

STL multi_map ( ++).

. , N .

D , multi_map, ND, N-D + 1,..., N-1, N, N + 1,... N + D-1, N + D .

, multi_map , , .

( , , 0 1, .)

, 1 , 3 multi_map 100 , 3% - .