Reply to http://www.playwithlua.com/?p=60

word_seg.py

import sys


def shift(words, stack, c):
    return words, stack + c


def reduce(words, stack, c):
    return words + (stack,), c


def get_valid_moves(vocab, words, stack):
    if not stack or stack not in vocab:
        return (shift,)
    else:
        return (shift, reduce)


def read_vocab(loc):
    words = set(['i', 'a'])
    with open(loc) as file_:
        for line in file_:
            word = line.strip().lower()
            if len(word) >= 2:
                words.add(word)
    return words


def parse_telegram(vocab, string, beam_width):
    beam = [(tuple(), '')]
    for c in string:
        new_beam = []
        for words, stack in beam:
            for move in get_valid_moves(vocab, words, stack):
                new_beam.append(move(words, stack, c))
        new_beam.sort(key=lambda state: len(state[0]))
        beam = new_beam[:beam_width]
    for words, stack in beam:
        if stack in vocab:
            return ' '.join(words + (stack,))
    else:
        return None


def main(vocab_loc, telegram):
    vocab = read_vocab(vocab_loc)
    print parse_telegram(vocab, telegram.lower(), len(telegram) * 100)


if __name__ == '__main__':
    main(*sys.argv[1:])