title: Sequential pattern matching algorithm in Python
body: <p>I find myself in this situation that I need to implement an algorithm for sequential pattern matching in Python. Can't find any working library/snippet on the internet after searching for hours.</p>
  <p>problem definition:</p>
  <p>implement a function sequential_pattern_match</p>
  <blockquote>
  <p>input: tokens, (an ordered collection of strings)</p>
  <p>output: a list of tuples, each tuple = (any subcollection of tokens, tag)</p>
  </blockquote>
  <p>domain experts will define the matching rule, usually using regex</p>
  <blockquote>
  <p>test(tokens) -&gt; tag or None</p>
  </blockquote>
  <p>Example:</p>
  <blockquote>
  <p>input: [&quot;Singapore&quot;, &quot;Python&quot;, &quot;User&quot;, &quot;Group&quot;, &quot;is&quot;, &quot;here&quot;]</p>
  <p>output: [([&quot;Singapore&quot;, &quot;Python&quot;, &quot;User&quot;, &quot;Group&quot;], &quot;ORGANIZATION&quot;), (&quot;is&quot;, 'O'), (&quot;here&quot;, 'O')]</p>
  </blockquote>
  <p>'O' means no match.</p>
  <p>Conflict resolution rules:</p>
  <ol>
  <li>a match that appears first has higher precedence.
  e.g. &quot;Singapore property sales&quot;, if two conflicting matches are possible, &quot;Singapore property&quot; as asset and &quot;property sales&quot; as event, then the first one is used.</li>
  <li>a longer match has higher precedence than shorter match.
  e.g. &quot;Singapore Python User Group&quot; as organization takes higher precedence than individual matches of &quot;Singapore&quot; as location + &quot;Python&quot; as language.</li>
  </ol>
  <p>With my expertise in algorithms and data structure, this is my implementation:</p>
  <pre><code>from itertools import ifilter, imap
  
  
  MAX_PATTERN_LENGTH = 3
  
  def test(tokens):
      length = len(tokens)
      if (length == 1):
          if tokens[0] == &quot;Nexium&quot;:
              return &quot;MEDICINE&quot;
          elif tokens[0] == &quot;pain&quot;:
              return &quot;SYMPTOM&quot;
      elif (length == 2):
          string = ' '.join(tokens)
          if string == &quot;Barium Swallow&quot;:
              return &quot;INTERVENTION&quot;
          elif string == &quot;Swallow Test&quot;:
              return &quot;INTERVENTION&quot;
      else:
          if ' '.join(tokens) == &quot;pain in stomach&quot;:
              return &quot;SYMPTOM&quot;
  
  def _evaluate(tokens):
      tag = test(tokens)
      if tag:
          return (tokens, tag)
      elif len(tokens) == 1:
          return (tokens, 'O')
  
  def _splits(tokens):
      return ((tokens[:i], tokens[i:]) for i in xrange(min(len(tokens), MAX_PATTERN_LENGTH), 0, -1))
  
  def sequential_pattern_match(tokens):
      return ifilter(bool, imap(_halves_match, _splits(tokens))).next()
  
  def _halves_match(halves):
      result = _evaluate(halves[0])
      if result:
          return [result] + (halves[1] and sequential_pattern_match(halves[1]))
  
  if __name__ == &quot;__main__&quot;:
      tokens = &quot;I went to a clinic to do a Barium Swallow Test because I had pain in stomach after taking Nexium&quot;.split()
      output = sequential_pattern_match(tokens)
      slashTags = ' '.join(t + '/' + tag for tokens, tag in output for t in tokens)
      print(slashTags)
      assert slashTags == &quot;I/O went/O to/O a/O clinic/O to/O do/O a/O Barium/INTERVENTION Swallow/INTERVENTION Test/O because/O I/O had/O pain/SYMPTOM in/SYMPTOM stomach/SYMPTOM after/O taking/O Nexium/MEDICINE&quot;
  
      import timeit
      t = timeit.Timer(
          'sequential_pattern_match(&quot;I went to a clinic to do a Barium Swallow Test because I had pain in stomach after taking Nexium&quot;.split())',
          'from __main__ import sequential_pattern_match'
      )
      print(t.repeat(3, 10000))
  </code></pre>
  <p>I don't think it can be faster. Unfortunately it was written in functional style, which may be unsuitable in Python. Are you able to come out with a faster implementation in OO or imperative style?</p>
  <p>(Note: I am sure it will be faster if implemented in C, but currently I have no plan of using other language other than Python)</p>