optimization pointers?

[r.e.s.]

Would anyone care to offer pointers on how the following code
might be optimized?  Or alternatives?  ...

---
def lz(string):
    """ Return the Lempel-Ziv complexity (LZ78) of string. """

    vocabulary = []
    word = ''
    for char in string:
        word += char
        if word not in vocabulary:
            vocabulary.append(word)
            word = ''
    return len(vocabulary)
---

On my 2 GHz system running PythonWin, the above code averages 
about 1.3 hrs to process a 1 MB string.  I'd hoped to compute 
LZ78 for multi-GB files, but it seems infeasible. (?)

Thanks for any feedback.
--
r.e.s.