2011-05-13 74 views
4

我想了解从http://linux.thai.net/~thep/datrie/datrie.html 双阵列Trie实现但我不明白以下部分。双数组Trie问题

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

添加c是什么意思?

任何人都可以用简单的语言解释算法。

+1

您是否了解Triple-Array实现的工作原理? Double-Array版本仅将'base'和'next'数组合并成一个。添加'c'的作用与Triple-Array版本相同。 – xofon 2011-05-13 11:44:45

回答

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

我希望我没有做这个太复杂了(虽然我觉得我做了...)。 :)

0

字符是“基于零”的,即“a”是0,“b”是1,“c”是2等等。查找“a”意味着将0添加到当前节点的基地址并检查该索引处的所有者。如果该所有者是当前节点,则从trie中的当前节点有一个以“a”开头的字符串,并且该索引处的基地址是下一次查找的基地址。