Double-Array Trie Question

Question

J'essaye de comprendre la mise en œuvre de Double-Array Trie de http://linux.thai.net/~thep/datrie/datrie.html Mais je ne comprends pas la partie suivante.

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

Que signifie ajouter c ici. Quelqu'un peut-il expliquer l'algorithme dans un langage simple?

Answer 1

Imaginez-vous un tableau 2D de rentrée, dans un tableau 1D:

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 ----^

J'espère que je ne faisais pas cela trop compliqué (même si je pense que je l'ai fait ...). :)

Answer 2

Les caractères sont "basés sur zéro", c'est-à-dire que "a" est 0, "b" vaut 1, "c" vaut 2, et cetera. Chercher "a" signifierait ajouter 0 à l'adresse de base du nœud actuel et vérifier le propriétaire à cet index. Si ce propriétaire est le noeud courant, il y a une chaîne commençant par "a" du noeud courant dans le trie, et l'adresse de base à cet index est l'adresse de base pour la recherche suivante.