作者j4568520 (KaSiM)
看板java
标题[问题] 关於Double Array Trie的实作问题
时间Sun Dec 16 18:12:44 2018
目前小弟在看github上实作Double Array Trie的 Project，
专案在此:
https://tinyurl.com/y7ys94ks
使用到 AhoCorasickDoubleArrayTrie.java、State.java
AhoCorasickDoubleArrayTrie.java里
有某段程式码想不太透，想麻烦大家帮忙指点迷津。
以下节录不明所以的程式码片段。
private int insert(List<Map.Entry<Integer, State>> siblings)
{
int begin = 0;
int pos = Math.max(siblings.get(0).getKey() + 1, nextCheckPos) - 1;
int nonzero_num = 0;
int first = 0;
if (allocSize <= pos)
resize(pos + 1);
outer:
// 此循环体的目标是找出满足base[begin + a1...an] == 0的n个空闲空间
,a1...an是siblings中的n个节点
while (true)
{
pos++;
if (allocSize <= pos)
resize(pos + 1);
if (check[pos] != 0)
{
nonzero_num++;
continue;
}
else if (first == 0)
{
nextCheckPos = pos;
first = 1;
}
begin = pos - siblings.get(0).getKey();
if (allocSize <= (begin + siblings.get(siblings.size() - 1).getKey()))
{
double l = (1.05 > 1.0 * keySize / (progress + 1)) ? 1.05 : 1.0 *
keySize / (progress + 1);
resize((int) (allocSize * l));
}
if (used[begin])
continue;
for (int i = 1; i < siblings.size(); i++)
if (check[begin + siblings.get(i).getKey()] != 0)
continue outer;
break;
}
if (1.0 * nonzero_num / (pos - nextCheckPos + 1) >= 0.95)
nextCheckPos = pos;
used[begin] = true;
size = (size > begin + siblings.get(siblings.size() - 1).getKey() + 1) ?
size : begin + siblings.get(siblings.size() - 1).getKey() + 1;
for (Map.Entry<Integer, State> sibling : siblings)
{
check[begin + sibling.getKey()] = begin;
}
for (Map.Entry<Integer, State> sibling : siblings)
{
List<Map.Entry<Integer, State>> new_siblings = new
ArrayList<Map.Entry<Integer, State>>
(sibling.getValue().getSuccess().entrySet().size() + 1);
if (fetch(sibling.getValue(), new_siblings) == 0)
{
base[begin + sibling.getKey()] =
(-sibling.getValue().getLargestValueId() - 1);
progress++;
}
else
{
int h = insert(new_siblings); // dfs
base[begin + sibling.getKey()] = h;
}
sibling.getValue().setIndex(begin + sibling.getKey());
}
return begin;
}
在insert方法的最後会呼叫fetch方法，
将目前节点里所有的子节点全存放到new_siblings，
回传new_siblings的size()值。并判断回传值是否为0。
然而我看到fetch方法里，有个"isAcceptable()"，
判断该节点是否为末端节点，如果它是末端节点，
就会在new_siblings新增一个fakeNode。
照这样的逻辑看下去，好像无论如何都不会发生
" fetch(sibling.getValue(), new_siblings) == 0 " 的情况。
因为如果不是末端节点，就一定会有子节点加入new_siblings，
但如果节点是末端节点，又会被加上fakeNode。
就我的理解，呼叫fetch方法的当下如传入末端节点，
应该回传值要是0才对，代表没任何子节点存到new_siblings。
不知道我有哪里想错了，也搞不太清楚fakeNode的意义。
再麻烦各位先进不吝指教。谢谢！
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.24.209.229
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/java/M.1544955167.A.C68.html