Double-Array Trie Question

Question

Я пытаюсь понять реализацию Double-Array Trie из http://linux.thai.net/~thep/datrie/datrie.html Но я не понимаю следующую часть.

check[base[s] + c] = s
base[s] + c = t 

Что означает здесь добавление c.

Может кто-нибудь объяснить алгоритм простым языком.

Answer 1

Представьте, что вы сворачиваете двумерный массив в одномерный массив:

int arr2D[2][3];
int arr1D[2 * 3]; // # of rows * # of columns

// access element [1][2] of 2D array, i.e., the last element
int elem2D = arr2D[1][2];
// access element [1][2] of 1D array, i.e., the last element
int elem1D = arr1D[1 * 3 + 2];
// =========================================================
lets visualize the array access:
arr2D => x/y 0  1  2
          0 [N][N][N]
+1 on x > 1 [N][N][N]
+2 on y ---------- ^
y_len  =>   ^-------^ 3 elements
so the access happens with x * y_len + y
                           1 *   3   + 2
now for the 1D array
we want the second row, so we go with 1 * 3
(0-based access, y_len = 3)
and then we want the 3rd element, so + 2
(again, 0-based access)
arr1D =>  x  0  1  2 
            [N][N][N]
             3  4  5
1 * 3 = 3 > [N][N][N]
      + 2 = 5 ---- ^

Надеюсь, я не сделал это слишком сложным (хотя я думаю, что сделал ...).:)

Answer 2

Символы «основаны на нуле», то есть «a» равно 0, «b» равно 1, «c» равно 2, и так далее.Поиск «а» будет означать добавление этого 0 к базовому адресу текущего узла и проверку владельца по этому индексу.Если этот владелец является текущим узлом, есть строка, начинающаяся с «a» с текущего узла в дереве, и базовый адрес в этом индексе является базовым адресом для следующего поиска.