続 Python で Suffix Array の構築

Python

むむ。そか、naive に1文字づつ切り出して比較するより、適当なサイズごとに比較してやったほうが速いよな、そりゃ。

そもそもの問題はコピーを作らずに比較できないことなのだけれど、 Python 3000ではsubstringを共有させるようにしようとか、 そういう話も持ち上がっていたみたい。 結局どうなるかは覚えてない。

お、やっぱりそういう話もあるのか。Reference Count の管理コストとの兼ね合いになると思うんだけど、言語処理屋からすると共有してくれたほうがありがたい。
閑話休題。
C++ で naive な Suffix Array 構築アルゴリズムを実装して SWIG でバインディングを作ってみたり。

#ifndef SUFFIX_ARRAY_H

#include <algorithm>
#include <utility>
#include <functional>
#include <string>

namespace SuffixArray {
    template<typename TextIterator, typename Index>
    class SuffixComparator : public std::binary_function<Index, Index, bool> {
    public:
        SuffixComparator(TextIterator begin, TextIterator end) : begin_(begin), end_(end) { }

        inline bool operator()(Index i, Index j) const {
            return std::lexicographical_compare(begin_ + i, end_, begin_ + j, end_);
        }

    private:
        TextIterator begin_;
        TextIterator end_;
    };

    template<typename TextIterator, typename IndexIterator>
    void buildSuffixArray(
        TextIterator textBegin, TextIterator textEnd,
        IndexIterator indexBegin, IndexIterator indexEnd) 
    {
        typedef typename std::iterator_traits<IndexIterator>::value_type Index;
        std::sort(indexBegin, indexEnd, SuffixComparator<TextIterator, Index>(textBegin, textEnd));
    }


    class SuffixArray {
    public:
        typedef int Index;
        typedef wchar_t Character;
    public:
        SuffixArray(const std::wstring& text) : text_(text) {
            size_ = text.length();
            build();
        }
        
        void build() {
            Index* indices = new Index[size_];
            for (size_t i = 0; i < size_; i++) {
                indices[i] = i;
            }

            buildSuffixArray(text_.begin(), text_.end(), indices, indices + size_);
            indices_ = indices;
        }

    private:
        std::wstring text_;
        const Index* indices_;
        size_t size_;
    };
}

#endif /* SUFFIX_ARRAY_H */

%module suffix_array
%include "std_wstring.i"
%{
#include "suffix_array.hpp"
%}
%include suffix_array.hpp

結構適当なコードだけど、setup.py を書いてビルドして実行したら 880 KBytes 程度のテキストなら所要時間 0.5秒ぐらい。やっぱりこういうところはネイティブコードだな。
実際には Multikey Quicksort なりなんなりのもっと巧妙なアルゴリズムを使うからさらに高速化できるんだけどな。