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; { mark 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
Definition 2. For a transition from state s to t which takes character c as the input, the condition maintained in the double-array trie is: check[base[s] + c] = s base[s] + c = t
s
根据定义2，base[s] + c = t;
而 s, base[s], t, base[t], base[b+c] ,u，b 均为 数组下标,c,d为字符序列码，即偏移量。
base[s]只是一个基地址，与数组中该下标对应的base，check是否为空，无关。
base[s] = k
base[s] + c = t; b + c = t‘, base[b+c] = base[t‘]; 因此：
check[b + c] := s; { mark owner }
base[b + c] := base[base[s] + c]; { copy data }
可以理解为： check[t‘] = s = check[t]; base[t‘] = base[t]; 即将 t（base[s] + c） 结点的base，check 值复制到 t‘结点中。
再调整t结点的孩子结点的check值，使其指向新的父节点t‘。
check[i] = base[s] + c 即 check[i] = t;
u = base[t] + d = base[base[s] + c] + d ; check[u] = check[base[base[s]+c] + d];
check[u] = t 即是：
check[base[base[s]+c] + d] = base[s] + c = t
修改父节点后：
check[base[base[s]+c] + d] = b+c = t‘
释放原先的t结点
check[base[s] + c] := none 即是 check[t] := none
令s指向新的孩子结点：
base[s] = b;