作者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/m.aspx?n=bbs/java/M.1544955167.A.C68.html