簡易ダブル配列ジェネレータ

HTTP Digest 認証の credential を DFA の遷移表にそのままトライを記述すると冗長すぎるので、ディレクティブ名の部分を別のトライで照合するように修正を考えています。 この手の固定文字列のトライはダブル配列にしておくと省スペースになります。

    // double-array trie
    //  for "algorithm" => 1, "cnonce" => 2, "nc" => 3, "nonce" => 4,
    //      "opaque" => 5, "qop" => 6, "realm" => 7, "response" => 8,
    //      "uri" => 9, "username" => 10
    static const std::vector<int> base {
       -1,  0,-10, -3, -2,-10,-12, -2,-12,  1, -3, 11,  1, -2,  2, 20, 15,
       16, 26, 43, 15, 22, 45,  2, 24,  3, 23, 23, 30, 29,  4,  0, 31, 21,
       21, 36, 11,  0, 34, 16, 40,  5, 28, 40, 40, 47, 46,  0,  6, 48, 38,
       38, 52,  7, 49, 56, 32,  0, 43, 45, 41, 56, 62,  8, 56, 63, 66,  9,
       41, 51, 56, 70, 59, 68, 74, 10};
    static const std::vector<int> check {
       -1,  0,  1,  2,  1,  3,  5,  6,  7,  8,  9, 10, 11,  4, 13,  1,  1,
       14,  1,  1, 17, 20,  1, 21, 15, 24, 36, 26, 36, 27, 29, 28, 16, 32,
       33, 34, 15, 35, 39, 33, 38, 40, 18, 42, 43, 42, 44, 46, 45, 19, 49,
       50, 51, 52, 56, 54, 50, 55, 68, 58, 59, 60, 61, 62, 22, 22, 64, 66,
       49, 65, 69, 70, 71, 72, 73, 74};

手作業でダブル配列を作るのは面倒なので、簡易ジェネレータを書いて、自動生成させることにします。

#include <algorithm>
#include <string>
#include <vector>
#include <iostream>
#include <iomanip>

void translate_code_vectors (std::vector<std::string> keys, std::vector<std::vector<int> >& list);
void create_double_array_trie (std::vector<std::vector<int> > const& list,
    int const c0, int const i, int const parent,
    std::vector<int>& base, std::vector<int>& check);
void check_double_array_trie (std::string const& s, std::size_t const n,
    std::vector<int>& base, std::vector<int> const& check)

int
main ()
{
    std::vector<std::string> keys = {
        "algorithm",
        "cnonce",
        "nc",
        "nonce",
        "opaque",
        "qop",
        "realm",
        "response",
        "uri",
        "username",
    };
    std::sort (keys.begin (), keys.end ());
    std::vector<std::vector<int> > list;
    translate_code_vectors (keys, list);

    std::vector<int> base {-1, 0};
    std::vector<int> check {-1, 0};
    create_double_array_trie (list, 0, 0, 1, base, check);
    for (std::size_t i = 0; i < keys.size (); ++i)
        check_double_array_trie (keys[i], i + 1, base, check);

    for (auto x : base)
        std::cout << "," << std::setw(3) << x;
    std::cout << std::endl;
    for (auto x : check)
        std::cout << "," << std::setw(3) << x;
    std::cout << std::endl;
    return EXIT_SUCCESS;
}

translate_code_vectors は文字列を終端コード付きのコード・ベクタに変換します。終端コードは 1 で、アルファベット a は 2、b は 3 にコード化します。なお、この簡易ジェネレータは英小文字にしか対応していません。

void
translate_code_vectors (std::vector<std::string> keys,
    std::vector<std::vector<int> >& list)
{
    for (auto& s : keys) {
        std::vector<int> v;
        for (auto i : s) {
            v.push_back (i - 'a' + 2);
        }
        v.push_back (1);
        list.push_back (v);
    }
}

create_double_array_trie で、コード・ベクタから、base と check のダブル配列を作ります。 この関数は、 親ノードのコード c0 に対する i 桁目のコード c を拾い出してトライのノードを作ります。

void
create_double_array_trie (std::vector<std::vector<int> > const& list,
    int const c0, int const i, int const parent,
    std::vector<int>& base, std::vector<int>& check)
{
    if (list.empty ())
        return;
    // i-1 桁が c0 のコード列から、 i 桁目のコードを edge に取り出します。
    std::vector<bool> mark (28, false);
    std::vector<int> edge;
    for (std::size_t j = 0; j < list.size (); ++j) {
        if (i < list[j].size () && (i == 0 || list[j][i - 1] == c0)) {
            int const c = list[j][i];
            mark[c] = true;
        }
    }
    for (std::size_t c = 0; c < 28; ++c) {
        if (mark[c]) {
            edge.push_back (c);
        }
    }
    if (edge.empty ())
        return;
    // 状態 1 から昇順に空きを調べます。
    int b = 1 - edge[0];
    for (;;) {
        bool used = false;
        for (int c : edge) {
            if (b + c < check.size () && check[b + c] >= 0) {
                used = true;
                break;
            }
        }
        if (! used)
            break;
        ++b;
    }
    // base と check が小さすぎるときは大きさを伸ばします。
    int n = b + edge.back () + 1;
    if (check.size () < n) {
        base.resize (n, 0);
        check.resize (n, -1);
    }
    // check[base[parent] + c] == parent にします。
    base[parent] = b;
    for (int c : edge) {
        check[b + c] = parent;
    }
    // c ごとにトライ・ノードを追加します。
    for (int c : edge) {
        create_double_array_trie (list, c, i + 1, b + c, base, check);
    }
}

check_double_array_trie はダブル配列を正しく作ることができたかどうか調べて、正しいときは base に照合対象文字列の番号を書き込みます。

void
check_double_array_trie (std::string const& s, std::size_t const n,
    std::vector<int>& base, std::vector<int> const& check)
{
    int x = 1;
    for (int ch : s) {
        int y = base[x] + ch - 'a' + 2;
        if (y < 1 || y >= check.size () || check[y] != x) {
            std::cout << "not ok " << s << std::endl;
            return;
        }
        x = y;
    }
    int z = base[x] + 1;
    if (z < 1 || z >= check.size () || check[z] != x || base[z] != 0) {
        std::cout << "not ok " << s << std::endl;
        return;
    }
    std::cout << "ok " << s << std::endl;
    base[z] = n;
}