Double-Array Trie Question

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

check[base[s] + c] = s
base开发者_开发技巧[s] + c = t 

What does adding c means here.

Can anybody explain algorithm in simple language.

Imagine you collaps 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, 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 ---- ^

I hope I didn't make this too complicated (even though I think I did...). :)

Characters are "zero based", i.e., 'a' is 0, 'b' is 1, 'c' is 2, et cetera. Looking up "a" would mean to add that 0 to the base address of the current node and check the owner at that index. If that owner is the current node, there is a string starting with "a" from the current node in the trie, and the base address at that index is the base address for the next lookup.

You should edit your code to the following:

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

In the scenario that state s accepts a character c and transformed into state t: s - c -> t. The key point is what base[s] means. As a state may accept multiple characters:

| |c1|c2|c3| |--|--|--|--| | s| x| y| z| The problem is how you express these mappings of s-c1->x, s-c2->y, s-c3->z. Traditionally, a map is a good practice:

class State {
    Map<Character, State> mappings;
}

But what if you use an array to express the mappings? base[s] is a base index in next array, from which an offset c is added. base[s] + c is the final index in next to store the next state mapped from state s and character c. Note that character c is actually an integer in programming language.