Python で Suffix Array の構築

import codecs, re

def most_long_match(a, b, array, i=1):
   while cmp(array[a:a+i], array[b:b+i]) == 0:
      i += 1
      if len(array) - a == i:
         break
   return cmp(array[a:a+i], array[b:b+i])

mat = re.compile('<.+?>')
 
fp = codecs.open('04.txt', 'r', 'utf8')
body = ''.join( line for line in fp if (not mat.match(line)) )
fp.close()

suffix = sorted(range(len(body)), cmp=lambda x,y:most_long_match(x, y, body))

なんで slice を伸ばし続ける。だんだんと比較のコストがでかくなるじゃないか。さらに 境界の判定は a + i だけ(しかも判定式が直感的でない)で、b + i の方にはないし。つうかもうちょいモジュール化を意識して書いたほうがいいと思うなぁ。
で、適当に書いてみた。

import sys
from itertools import izip

class SuffixComparator(object):
    __slots__ = 'text length'.split(' ')
    
    def __init__(self, text):
        self.text = text
        self.length = len(text)

    def __call__(self, a, b):
        for i, j in izip(xrange(a, self.length), xrange(b, self.length)):
            c = cmp(self.text[i], self.text[j])
            if c: return c
        return cmp(j, i)

def build_suffix_array(text, indices = None):
    if indices is None:
        indices = range(len(text))

    indices.sort(SuffixComparator(text))
    return indices

def read_file(filename):
    fp = file(filename)
    try:
        return fp.read()
    finally:
        fp.close()

def suffix(text, index, max_length):
    last = text.find('\n', index, index + max_length)
    if last != -1:
        return text[index:last]
    else:
        return text[index:index + max_length]

def main(args, options):
    if args:
        text = ''.join(read_file(f) for f in args)
    else:
        text = sys.stdin.read()

    if options.encoding:
        text = text.decode(options.encoding)

    suffix_array = build_suffix_array(text)
    for i in suffix_array:
        sys.stdout.write('%d\t%s\n' % (i, suffix(text, i, 10).encode('utf-8')))

if __name__ == '__main__':
    from optparse import OptionParser
    
    parser = OptionParser()
    parser.add_option('-e', '--encoding', dest='encoding',
                      help='input encoding', metavar='encoding')
    (options, args) = parser.parse_args()

    main(args, options)

微妙に仕様が違うあたりはご愛嬌。
ちなみに Pentium M 2GHz の Windows 上 で 880 Kbytes のテキストに対して 30秒 ぐらいかかる。psyco と併用した場合は 16 秒ぐらいになるけど、どちらにしても遅い。
ナイーブなアルゴリズムってのもあるけど、こういう処理はやっぱり C/C++ で書いて SWIG でバインディング作るってのが定番だろうなぁ。