建立trie的一些疑问

Question

我参考了下面的一篇文档。
http://linux.thai.net/~thep/datrie/datrie.html文档描述的很详细，我的疑问是，base，check，next这几个数组里面存放的元素都是什么？实现的核心内容是状态转移，这是我的理解。另外，为什么第二种实现可以省掉next数组呢？

Answer 1

ConstructionThe construction of double-array trie is in principle the same as that of tripple-array trie. The difference is the base relocation:Procedure Relocate(s : state; b : base_index)
{ Move base for state s to a new place beginning at b }
begin
    foreach input character c for the state s
    { i.e. foreach c such that check[base[s] + c]] = s }
    begin
        check[b + c] := s;     {  owner }
        base[b + c] := base[base[s] + c];     { copy data }
        { the node base[s] + c is to be moved to b + c;
          Hence, for any i for which check[i] = base[s] + c, update check[i] to b + c }
        foreach input character d for the node base[s] + c
        begin
            check[base[base[s] + c] + d] := b + c
        end;
        check[base[s] + c] := none     { free the cell }
    end;
    base[s] := b
end

Answer 2

哪位帮忙解释下面的一段吧。
后面的我再回去研究看看。ConstructionThe construction of double-array trie is in principle the same as that of tripple-array trie. The difference is the base relocation:Procedure Relocate(s : state; b : base_index)
{ Move base for state s to a new place beginning at b }
begin
    foreach input character c for the state s
    { i.e. foreach c such that check[base[s] + c]] = s }
    begin
        check[b + c] := s;     {  owner }
        base[b + c] := base[base[s] + c];     { copy data }
        { the node base[s] + c is to be moved to b + c;
          Hence, for any i for which check[i] = base[s] + c, update check[i] to b + c }
        foreach input character d for the node base[s] + c
        begin
            check[base[base[s] + c] + d] := b + c
        end;
        check[base[s] + c] := none     { free the cell }
    end;
    base[s] := b
end
http://linux.thai.net/~thep/datrie/doubreloc.gif

Answer 3

哪位可以解释一下建立的过程，后面的我回去再研究研究...
ConstructionThe construction of double-array trie is in principle the same as that of tripple-array trie. The difference is the base relocation:Procedure Relocate(s : state; b : base_index)
{ Move base for state s to a new place beginning at b }
begin
    foreach input character c for the state s
    { i.e. foreach c such that check[base[s] + c]] = s }
    begin
        check[b + c] := s;     {  owner }
        base[b + c] := base[base[s] + c];     { copy data }
        { the node base[s] + c is to be moved to b + c;
          Hence, for any i for which check[i] = base[s] + c, update check[i] to b + c }
        foreach input character d for the node base[s] + c
        begin
            check[base[base[s] + c] + d] := b + c
        end;
        check[base[s] + c] := none     { free the cell }
    end;
    base[s] := b
end