In [1]:

    

# Let's make a class that implements an inverted (substring) index where the map data
# structure is a sorted list of (substring, offset) pairs.  Query w/ binary search.

import sys
import bisect # for binary search

class IndexSorted(object):
    
    def __init__(self, t, ln, ival):
        """ Create index, extracting substrings of length 'ln' """
        self.t = t
        self.ln = ln
        self.ival = ival
        self.index = []
        for i in range(len(t)-ln+1):
            self.index.append((t[i:i+ln], i)) # add <substr, offset> pair
        self.index.sort() # sort pairs
    
    def query(self, p):
        """ Return candidate alignments for p """
        st = bisect.bisect_left(self.index, (p[:self.ln], -1)) # binary search
        en = bisect.bisect_right(self.index, (p[:self.ln], sys.maxsize)) # binary search
        hits = self.index[st:en] # this range of elements corresponds to the hits
        return [ h[1] for h in hits ] # return just the offsets


    

In [2]:

    

index = IndexSorted('CGTGCCTACTTACTTACAT', 5, 4)


    

In [3]:

    

index.query('CTTACTTA') # index: give us hints on where to look for this pattern


    

    
Out[3]:





[8, 12]

In [4]:

    

index.query('TTTTTTTT') # index: give us hints on where to look for this pattern


    

    
Out[4]:





[]

In [5]:

    

# Now let's make a similar class but using a Python dictionary instead of a sorted
# list.  A Python dictionary is basically a hash table.

class IndexHash(object):
    
    def __init__(self, t, ln, ival):
        """ Create index, extracting substrings of length 'ln' """
        self.t = t
        self.ln = ln
        self.ival = ival
        self.index = {}
        for i in range(len(t)-ln+1):
            substr = t[i:i+ln]
            if substr in self.index:
                self.index[substr].append(i) # substring already in dictionary
            else:
                self.index[substr] = [i] # add to dictionary
    
    def query(self, p):
        """ Return candidate alignments for p """
        return self.index.get(p[:self.ln], [])


    

In [6]:

    

index2 = IndexHash('CGTGCCTACTTACTTACAT', 5, 4)


    

In [7]:

    

index2.query('CTTACTTA') # index: give us hints on where to look for this pattern


    

    
Out[7]:





[8, 12]

In [8]:

    

index2.query('TTTTTTTT') # index: give us hints on where to look for this pattern


    

    
Out[8]:





[]