マルチキークイックソート
自然言語処理はじめました - 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の3つに分割しましたが、この処理はもっと効率の良い方法が存在するみたいです。
次はこのマルチキークイックソートを使ってSuffixArrayの構築、検索、Ngram取得の予定