マルチキークイックソート

自然言語処理はじめました - Ngramを数え上げまくるを見てSuffixArrayを使ったNgram取得をやってみたくなりました！
SuffixArrayの構築には文字列のソートが必要なのでまずはここから始めます。
文字列のソートにはクイックソートを文字列のソートに応用したマルチキークイックソートを使います。アルゴリズムはこちらを参考にしました。
マルチキー・クイックソート(multikey-quicksort)で高速に文字列ソート - EchizenBlog-Zwei

まずは単純なクイックソートから

#coding: utf-8
def quicksort(seq):
    """単純なクイックソート
    数値のソート"""
    if not seq:
        return []
    pivot = seq.pop(0)
    left=[]
    right=[]
    for i in xrange(len(seq)):
        if seq[i] < pivot:
            left.append(seq[i])
        else:
            right.append(seq[i])
    left = quicksort(left)
    right = quicksort(right)
    return left + [pivot] + right

>>> seq = [4,2,3,6,1,9,7,5,10]
>>> print quicksort(seq)
[1, 2, 3, 4, 5, 6, 7, 9, 10]

OK！リスト内包表記を使うとワンライナーでも書けるようですが分かりやすさ重視ということで^^;
次はこのクイックソートを参考にしながらマルチキークイックソート

>>> def multikeysort(seq, cmpindex=0):
...     """単純なマルチキークイックソート
...     文字列のソート"""
...     if not seq:
...         return []
...     pivot = seq[0]
...     left=[]
...     mid=[]
...     right=[]
...     #cmpindex番目の文字を比較
...     for i in xrange(1, len(seq)):
...         if seq[i][cmpindex] < pivot[cmpindex]:
...             left.append(seq[i])
...         elif seq[i][cmpindex] == pivot[cmpindex]:
...             mid.append(seq[i])
...         else:
...             right.append(seq[i])
...     mid.append(pivot)
...     #IndexError防止と計算量軽減
...     if not pivot[cmpindex] == '$' and not len(mid) < 2:
...         mid = multikeysort(mid, cmpindex+1)
...     left = multikeysort(left, cmpindex)
...     right = multikeysort(right, cmpindex)
...     return left + mid + right
... 
#英語
>>> string = "abracadabra$"
>>> strings = [string[i:] for i in xrange(len(string))]
>>> for suffix in strings:
...     print suffix
... 
abracadabra$
bracadabra$
racadabra$
acadabra$
cadabra$
adabra$
dabra$
abra$
bra$
ra$
a$
$
>>> for suffix in multikeysort(strings):
...     print suffix
... 
$
a$
abra$
abracadabra$
acadabra$
adabra$
bra$
bracadabra$
cadabra$
dabra$
ra$
racadabra$

#ユニコード
>>> string = u"ソートは難しい$"
>>> strings = [string[i:] for i in xrange(len(string))]
>>> for suffix in strings:
...     print suffix
... 
ソートは難しい$
ートは難しい$
トは難しい$
は難しい$
難しい$
しい$
い$
$
>>> for suffix in multikeysort(strings):
...     print suffix
... 
$
い$
しい$
は難しい$
ソートは難しい$
トは難しい$
ートは難しい$
難しい$

とりあえず書けたというレベル^^;
今回は単純にleft, mid, rightの３つに分割しましたが、この処理はもっと効率の良い方法が存在するみたいです。

次はこのマルチキークイックソートを使ってSuffixArrayの構築、検索、Ngram取得の予定