这种实现可以给节点加一个标志位，用来标识当前节点是一个叶子节点，用于识别查找输入是一个词的一部分而不是整个词的情况。
用双队列实现Trie
Trie可以看成是一个有限状态机，其中的状态是词汇表里的任何一个词的一部分或者整个词，比如假设there在词汇表里，那么th就是一个状态，这个过度函数f满足f(th, e)=the，f(th, z)=th。
如果我们想把一个trie存在一个array里，最直接的想法如下图，例子里字母表为"abcd"，假设所有可能的字符串都在trie里。
数组里元素是下一个状态的base index，对于任何一个当前状态，下一个可能状态个数等于字母表的size，这里是4，所以要分配一个size为4的连续block表达，base index就是这个block的起始位置的index，存在代表当前状态的数组元素里，比如所有可能状态bx(其中x=a,b,c,d)的base index已经标注在图里了。
这样存储不能满足不满的trie，比如如果bx状态只有"ba","bb","bc"没有"bd"，我们想节省存储空间，那么不给状态bx分配size为4的blcok，分一个size为3的，这会带来一个问题，那么原来应该在"bd"位置存储的就不是"bdx"的base index，而是"cax"的base index。
而这两种情况下那个元素的意义可以这样区分，如果是bd，那么pre-state是xxxxb，如果是ca，那么pre-state是xxxxxc。所以解决的办法是另外弄一个array记录当前状态的pre-state。
查找算法，如果要找bdc
1. base index of state "": base[0]=0
2. state change form "" to "b":
index of state "b" is (i = base[0] + 'b' - 'a')
if( check[i] == "" ) bi = base[i] //(base index of bx)
else failed
3. state change from "b" to "bd":
index of state "bd" is (i = base[bi] + 'd' - 'a')
if( check[i] == "b" ) bi = base[i] //(base index of bdx)
else failed
第三步会返回failed，也就是不在trie里。
区别完整word和前缀的方法是，对最后一个输入字符，check成功，但是base[i]是非法的，比如base队列里初始化的时候为0，如果base[i]==0且i!=0就是非法的。
base队列每个元素有双重意义，元素的index代表state，元素的值代表直接后续状态的base index。所以上面代码里面的check[i] == "b"里面的"b"应该写为base的index，因为"b"的含义是一个state，state和base的index是等价的。改为check[i] == base[0] + 'b' - 'a'，例如第3步应改为：
3. state change from "b" to "bd":
pre_i = i // keep the index of state "b"
index of state "bd" is (i = base[bi] + 'd' - 'a')
if( check[i] == pre_i ) bi = base[i] //(base index of bdx)
else failed
构建trie
构建是不断插入字符串的过程，会遇到要插入的位置已经被占了，例如上例中插入"bdc"，当到状态"bd"的时候发现位置已经被"ca"占了，现在有两个选择，要么把整个bx block移动到队列最后，要么把cx block移动。谁小就移谁。
移动b block到位置p：
base[p + i] = base[b + i]
check[p + i] = check[b + i] //==""
//update check[] of state trade "b" as pre-state
state p+i的后续state block的base index bi=base[p + i]，所以base[bi] + j(假设这个index合法)的pre-state变为p+i，也就是check[base[bi] + j] = p+i
// free b block
check[b + i] = 0
No comments:
Post a Comment