title: Python implementation of the Sequitur algorithm?
body: <p>I need to use the Sequitur algorithm for a bioinformatics project but so far I haven't found any Python implementations of the algorithm. This is what I've got so far:</p>
  
  <pre><code>    def new_rule(sequence,rules,x,y,z):
      y = list(y)
      if max(y) &gt; 1:
          ind = y.index(max(y))
  
          locations = np.zeros(max(y))
  
          counter = 0
          for i, j in enumerate(z):
              if j == x[ind]:
                  locations[counter] = i
                  counter+=1
  
      new_rule = 'A'+str(len(rules)+1)
      rules.append([new_rule,x[ind]])
  
      return sequence.replace(x[ind],new_rule), rules
  
  def word_count(sequence):
      return len(sequence)-sequence.count(' ')
  
  def recursive_sequitur(sequence,rules):
      count_down = word_count(sequence)-1
  
  x,y,z = n_grams(sequence,count_down)
  
  while count_down&gt;1:
      if len(y) &gt; 1 and max(y) &gt; 1:
          sequence, rules = new_rule(sequence,rules,x,y,z)
          x,y,z = n_grams(sequence,count_down)
  
      else:
          count_down-=1
          x,y,z = n_grams(sequence,count_down)
  
  return sequence, rules
  </code></pre>