基於路徑的基於有界散列集的無限散列集

假設有一棵樹，參數爲XML樹。而且你需要一套完整的根節點路徑，但是你想把這個集合分成i個組，其中我是用戶指定的。基於路徑的基於有界散列集的無限散列集

因此，例如，一個HTML文件：

/html 
/html/head 
/html/head/title  
/html/head/title/[text] 
/html/body 
/html/body/[text]

變爲例如當i爲3：

{{1, 11, 111}, {1111, 12, 121}}

然後變成例如：

{3, 4}

使用簡化的樹類只能獲取節點名稱;獲取子樹的ArrayList;並檢查它是否是葉節點;構建這組哈希的最佳方式是什麼？

編輯：請參閱下面的示例解決方案答案，這遠遠不是最優的，因爲它非常緩慢，甚至可能不是最佳方法。

來源

2009-07-23 Robert

這是功課嗎？你有沒有去過它。你試過什麼了？ – 2009-07-23 11:38:04

我自己的解決方案如下，雖然我不確定這是否是實現這一目標最有效的方法......也許其他人可以提供有關Java錯綜複雜的一些洞察。

public ArrayList<Integer> makePathList(AbstractTree<String> tree){ 
    StringBuilder buffer = new StringBuilder(); 
    ArrayList<Integer> pl = new ArrayList<Integer>(); 
    ArrayList<StringBuilder> paths = getPaths(tree, buffer); 
    for(StringBuilder sb : paths){ 
     pl.add(sb.toString().hashCode()); 
    } 

    return pl; 
} 

public ArrayList<StringBuilder> getPaths(AbstractTree<String> tree, StringBuilder parent){ 

    ArrayList<StringBuilder> list = new ArrayList<StringBuilder>(); 
    parent.append("/"); 
    parent.append(tree.getNodeName()); 
    list.add(new StringBuilder(parent)); 
    if (!tree.isLeaf()){ 

     int i = 0; 
     Iterator<AbstractTree<String>> child = tree.getChildren().iterator(); 
     while (i < tree.getChildren().size()){ 

      list.addAll(getPaths(child.next(), new StringBuilder(parent))); 
      i++; 
     } 
    } 
    return list; 
} 

public HashSet<Integer> createShingleSet(ArrayList<Integer> paths, int shingleLength){ 
    HashSet<Integer> shingleSet = new HashSet<Integer>(); 
    for(int i = 0; i < paths.size(); i += shingleLength){ 
     Multiset<Integer> set = new Multiset<Integer>(); 
     for(int j = 0; j < shingleLength; j++){ 
      if (i + j < paths.size()) 
       set.add(paths.get(i + j));  
     } 
     shingleSet.add(set.hashCode()); 
    } 
    return shingleSet; 
}

編輯：傳遞一個StringBuilder更適合大文件。

編輯：爲相同的哈希碼提供相同的路徑，這似乎需要後應用

來源

2009-07-23 12:45:58 Robert

如果我這樣做，我的第一個想法將是一個MultiMap（有several implementations那裏，或者你可以推出自己的）。

這個多圖的關鍵將是用於到達節點的部分路徑，值數組應該是列表（不是Set，除非順序不重要 - 在XML中它是）共享該節點的節點部分路徑。

來源

2009-07-23 12:18:07 kdgregory

基於路徑的基於有界散列集的無限散列集

回答

相關問題