Double array question

Question

I am trying to understand the implementation of Trie Double Array from http://linux.thai.net/~thep/datrie/datrie.html But I do not understand the next part.

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

What does adding c mean.

Can someone explain the algorithm in plain language.

Answer 1

Imagine dropping a 2D array into a 1D array:

 int arr2D[2][3]; int arr1D[2 * 3]; // # of rows * # of columns // access element [1][2] of 2D array, ie, the last element int elem2D = arr2D[1][2]; // access element [1][2] of 1D array, ie, 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 ---- ^ 

I hope I did not make it too complicated (although I thought ...). :)

Answer 2

Zero-based characters, i.e. "a" is 0, "b" is 1, "c" is 2, and so on. Searching for "a" means adding this 0 to the base address of the current node and checking the owner at that index. If this owner is the current node, the line starts with "a" from the current node in trie, and the base address of this index is the base address for the next search.