エントロピー符号をステートマシンで解く - エンジニアのソフトウェア的愛情

お題。

オフラインリアルタイムどう書く第8回の参考問題 - Qiita

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

エントロピー符号 - Wikipedia

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

以下、コード。コードの全体は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のを入力、それぞれの枝をたどった先を次のステートとすると、ステートマシンと考えることができます。