Sequential pattern matching algorithm in Python
Question: 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.

problem definition:

implement a function sequential_pattern_match

> input: tokens, (an ordered collection of strings)
>
> output: a list of tuples, each tuple = (any subcollection of tokens, tag)

domain experts will define the matching rule, usually using regex

> test(tokens) -> tag or None

Example:

> input: ["Singapore", "Python", "User", "Group", "is", "here"]
>
> output: [(["Singapore", "Python", "User", "Group"], "ORGANIZATION"), ("is",
> 'O'), ("here", 'O')]

'O' means no match.

Conflict resolution rules:

  1. a match that appears first has higher precedence. e.g. "Singapore property sales", if two conflicting matches are possible, "Singapore property" as asset and "property sales" as event, then the first one is used.
  2. a longer match has higher precedence than shorter match. e.g. "Singapore Python User Group" as organization takes higher precedence than individual matches of "Singapore" as location + "Python" as language.

With my expertise in algorithms and data structure, this is my implementation:

    
    
    from itertools import ifilter, imap
    
    
    MAX_PATTERN_LENGTH = 3
    
    def test(tokens):
        length = len(tokens)
        if (length == 1):
            if tokens[0] == "Nexium":
                return "MEDICINE"
            elif tokens[0] == "pain":
                return "SYMPTOM"
        elif (length == 2):
            string = ' '.join(tokens)
            if string == "Barium Swallow":
                return "INTERVENTION"
            elif string == "Swallow Test":
                return "INTERVENTION"
        else:
            if ' '.join(tokens) == "pain in stomach":
                return "SYMPTOM"
    
    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__ == "__main__":
        tokens = "I went to a clinic to do a Barium Swallow Test because I had pain in stomach after taking Nexium".split()
        output = sequential_pattern_match(tokens)
        slashTags = ' '.join(t + '/' + tag for tokens, tag in output for t in tokens)
        print(slashTags)
        assert slashTags == "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"
    
        import timeit
        t = timeit.Timer(
            'sequential_pattern_match("I went to a clinic to do a Barium Swallow Test because I had pain in stomach after taking Nexium".split())',
            'from __main__ import sequential_pattern_match'
        )
        print(t.repeat(3, 10000))
    

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?

(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)


Answer: 
    def sequential_pattern_match(tokens):
        for first, rest in _splits(tokens):
            x = _halves_match(first, rest)
            if x:
                return x
    
    def _splits(tokens):
        for i in xrange(min(len(tokens), MAX_PATTERN_LENGTH), 0, -1):
            yield tokens[:i], tokens[i:]
    
    def _halves_match(first, rest):
        tag = test(first)
        if tag:
            return [(first, tag)] + (rest and sequential_pattern_match(rest))
    
    def test(tokens):
        length = len(tokens)
        if length == 1:
            if tokens[0] == "Nexium":
                return "MEDICINE"
            elif tokens[0] == "pain":
                return "SYMPTOM"
            else:
                return "O"
        elif length == 2:
            if tokens == ["Barium", "Swallow"]:
                return "INTERVENTION"
            elif tokens == ["Swallow", "Test"]:
                return "INTERVENTION"
        elif tokens == ["pain", "in", "stomach"]:
            return "SYMPTOM"
    

replaced `ifilter`, `imap` with simple `for` loop. generator expression with
`for` loop with `yield`.

Time reduced in my machine:

  * _1.02694065435_ -> _0.708227394544_ (Python 2.7.5)
  * _1.1575780184_ -> _0.425939527209_ (PyPy 2.1)

