SEQUITUR

だいぶ放置していたけれども、ふと思い立ってSEQUITURを実装しました。SEQUITURアルゴリズムというのは文字列などを文法構造に変換するアルゴリズムで、データの圧縮などに利用されたりするものです。->コード
SEQUITURについてはhttp://sequitur.info/がとても分かり易いです。
上のサイトにC++のコードが置いてあったのでそれをもとにして実装しました。もともと複雑なアルゴリズムなのであんまりすっきり書けなかったですが..。

使いかた。

#include <gail/lang/alphabet.hpp>
#include <gail/lang/sequitur.hpp>

#include <iostream>
#include <vector>
#include <string>

using namespace std;
using namespace gail;

int main(int argc, char *argv[])
{
    string str("abcdbcabcdbcabc");

    vector< vector<seq_code> > rule;

    // SEQUITUR実行
    seq_parse<ascii>(str.begin(), str.end(), rule);

    cout << "ORIGINAL : " << str << endl;
    for (size_t i = 0; i < rule.size(); ++i)
    {
        cout << "RULE" << i << " : ";
        for (size_t j = 0; j < rule[i].size(); ++j)
        {
            seq_code c = rule[i][j];
            if (is_nonterm(c))
                cout << "R" << nonterm_decode(c) << ' ';
            else
            {
                cout << term_decode<ascii>(c) << ' ';
            }
        }
        cout << endl;
    }
    return 0;
}

実行結果

ORIGINAL : abcdbcabcdbcabc
RULE 0 : R1 R1 R2 
RULE 1 : R2 d R3 
RULE 2 : a R3 
RULE 3 : b c 

という感じで文法構造が抽出されます。
それぞれのルールはシンボルの配列で、それが複数個集まったものが文法になります。
文法はvectorの入れ子で表現します。

vector< vector<seq_code> > rule;

seq_codeは終端記号と非終端記号を混在させる為に必要な型です。非終端記号かどうかはis_nonterm()を使って判別して実際の値はnonterm_decode()もしくはterm_decode()を使って求めます。nonterm_decode()の戻り値はルール番号で、term_decode()の戻り値は元々の値(上の場合はchar型)です。

char文字列以外の構造を解析する事も考えてテンプレート引数にアルファベット集合を表すクラスを渡すようにしました。アルファベットクラスの役割はもともとのオブジェクトを符号化することで、上のasciiクラスはそのままchar型の値を返すだけです。
例えば、SEQUITURを使って楽曲の構造解析をしたい場合は

ドの四分音符->0,
ドの八分音符->1,
ドの十六分音符->2,
...

みたいな感じで符号化するクラスを作って、リスト化したデータのbeginとendを渡せば解析できるはずです。試してはいませんけれども。