Databases
StackOverflow2013
Postsdbo
POFast string search using bitwise operators
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POFast string search using bitwise operators
    primarykey
    data
    text
    <p>What is the fastest (parallel?) way to find a substring in a very long string using bitwise operators?</p> <p>e.g. find all positions of "GCAGCTGAAAACA" sequence in a human genome <a href="http://hgdownload.cse.ucsc.edu/goldenPath/hg18/bigZips/hg18.2bit" rel="nofollow noreferrer">http://hgdownload.cse.ucsc.edu/goldenPath/hg18/bigZips/hg18.2bit</a> (770MB)</p> <p>*the alphabet consists of 4 symbols ('G','C',T,'A') represented using 2 bits: 'G':00, 'A':01, 'T':10, 'C':11 </p> <p>*you can assume the query string (the shorter one) is fixed in length, e.g. 127 characters</p> <p>*by fastest I mean not including any pre-processing/indexing time</p> <p>*the file is going to be loaded into memory after pre-processing, basically there will be billions of short strings to be searched for in a larger string, all in-memory.</p> <p>*bitwise because I'm looking for the simplest, fastest way to search for a bit pattern in a large bit array and stay as close as possible to the silicon.</p> <p>*KMP wouldn't work well as the alphabet is small</p> <p>*C code, x86 machine code would all be interesting.</p> <p>Input format description (.2bit): <a href="http://jcomeau.freeshell.org/www/genome/2bitformat.html" rel="nofollow noreferrer">http://jcomeau.freeshell.org/www/genome/2bitformat.html</a></p> <p>Related: </p> <p><a href="https://stackoverflow.com/questions/1572290/fastest-way-to-scan-for-bit-pattern-in-a-stream-of-bits">Fastest way to scan for bit pattern in a stream of bits</a></p> <p><a href="https://stackoverflow.com/questions/8811335/algorithm-help-fast-algorithm-in-searching-for-a-string-with-its-partner">Algorithm help! Fast algorithm in searching for a string with its partner</a></p> <p><a href="http://www.arstdesign.com/articles/fastsearch.html" rel="nofollow noreferrer">http://www.arstdesign.com/articles/fastsearch.html</a></p> <p><a href="http://en.wikipedia.org/wiki/Bitap_algorithm" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Bitap_algorithm</a></p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USalex
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    3. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POFast string search using bitwise operators
      1. This table or related slice is empty.
      1. VTDownMod
    2. VO
      singulars
      1. POFast string search using bitwise operators
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POFast string search using bitwise operators
      1. This table or related slice is empty.
      1. VTUpMod
    1. CO(aside from the arbitrary restriction, usually indicative of homework) - Search for Boyer-More, KMP
      singulars
      1. POFast string search using bitwise operators
      1. USMitch Wheat
    2. COWhy is it necessary to use bitwise operators?
      singulars
      1. POFast string search using bitwise operators
      1. USMichael Mior
    3. COIs the data recorded using 2-bits per character? If not, there is no benefit to the observation that the alphabet consists of just 4 characters (or, at least, I can't think of any benefit).
      singulars
      1. POFast string search using bitwise operators
      1. USJonathan Leffler
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload