エンジニアのソフトウェア的愛情

または私は如何にして心配するのを止めてプログラムを・愛する・ようになったか

エントロピー符号をステートマシンで解く

お題。


この問題は、名前が示す通り、エントロピー符号で符号化されています。


と、いうことは。一定の手順を踏むことで復号が可能ということになります。
と、いうことで。解いてみました。

以下、コード。コードの全体はGitHubに格納しています。

#include <iostream>
#include <sstream>
#include <string>

static const std::string NIBBLES[] =
{
    "0000", "1000", "0100", "1100", "0010", "1010", "0110", "1110",
    "0001", "1001", "0101", "1101", "0011", "1011", "0111", "1111"
};

static const std::string HEXES = "0123456789abcdef";

static const int STATES[][2] =
{
    {  1,  5 }, {  6,  2 }, {  3, 11 }, { 16,  4 },
    { 17,  7 }, { 23,  8 }, { 13,  9 }, { 10, 20 },
    { 12, 26 }, { 14, 15 }, { 18, 19 }, { 21, 22 }, { 24, 25 }
};

static const int CHAR_CODE    = 13;
static const int INVALID_CODE = 18;
static const int TERMINAL     = 26;

char state2char(int state)
{
    return "tsnid cloaerh"[state - CHAR_CODE];
}

std::string solve(const std::string& input)
{
    std::string bits;
    for(std::string::const_iterator i = input.begin(); i != input.end(); ++i)
    {
        bits += NIBBLES[HEXES.find(*i)];
    }

    std::string::size_type pos = 0;
    std::string            result;
    int                    state = 0;
    for(;;++pos)
    {
        if(bits.size() <= pos) { pos = std::string::npos; break; }

        state = STATES[state][bits[pos] - '0'];

        if(state == INVALID_CODE) { pos = std::string::npos; break; }
        if(state == TERMINAL)     { break; }
        if(state >= CHAR_CODE)    { result += state2char(state); state = 0; }
    }

    if(pos != std::string::npos)
    {
        std::ostringstream output;
        output << result << ":" << (pos + 1);
        return output.str();
    }
    else
    {
        return "*invalid*";
    }
}

// テストコード略


思ったよりきれいになりませんでした。まだまだ未熟だなー。

どのように符号化されているのかを調べる

今回の問題で定義されている文字がどのように符号化されているかをグラフにすると次のようになります。

このうち「×」になっているところは文字が割り当てられていないことを意味します(つまり、復号中にこの符号が出てきたら復号失敗になります)。たとえばグラフ中の各分岐で「0-0-0」という枝をたどると「t」にたどり着くことがわかると思います。各分岐点をステート、0/1のを入力、それぞれの枝をたどった先を次のステートとすると、ステートマシンと考えることができます。

ステートマシンを作る

まず。格分岐点と終点に番号を与えます。こんな感じ。


次にこれをもとに状態遷移表を作ります。コードではSTATESがこれに該当します。

入力\状態 0 1 2 3 4 5 6 7 8 9 10 11 12
0 1 6 3 16 17 23 13 10 12 14 18 21 24
1 5 2 11 4 7 8 9 20 26 15 19 22 25

13以上には文字あるいは終端が割り当てられているのでそこからの遷移はありません。なので遷移表に出てくる状態は0から12までです。


復号では、13以上の値が出てくるまでステートマシンを動かし、13以上の値が出てきたらそれを文字に変換して結果に追加し、次の文字の復号に進む、という手順を踏みます。文字が割り当てられていない18が出てきたらそこで復号失敗で終了します。終端の26が出てきたら復号完了で終了します。