경로를 기반으로하는 해시의 제한된 세트를 기반으로하는 제한되지 않은 해시 집합

XML 트리를위한 트리가 있다고 가정합니다. 그리고 노드 경로에 대한 완전한 루트 집합을 원하지만 그 집합을 i의 그룹으로 나누고 싶습니다. 여기서 i는 사용자 지정입니다.경로를 기반으로하는 해시의 제한된 세트를 기반으로하는 제한되지 않은 해시 집합

그래서 예를 들어 HTML 문서 : 내가 3 때

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

예를 들어이된다 : 단순화 트리 클래스를 사용

{3, 4}

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

다음 예를 들어이된다 노드 이름 만 가져올 수 있습니다. 하위 트리의 ArrayList를 가져옵니다. 리프 노드인지 확인합니다. 이 해시 집합을 만드는 가장 좋은 방법은 무엇입니까?

EDIT : 아래 샘플 솔루션 답변을 참조하십시오. 이것은 매우 느리고 어쩌면 최선의 방법이 아니기 때문에 최적이 아닙니다.

출처

2009-07-23 Robert

이 숙제인가 이후에 적용해야하는 것? 당신은 그것에 가본 적이 있습니까? 지금까지 뭐 해봤 어? –

나는 숙제가 아니다. 비록 내가 배치에 학생이지만. 난 아직도 내 자신의 솔루션을 노력하고있어, 본질적으로 내가 트리를 통과 해요 해시의 ArrayList를 만드는 자바의 자신의 문자열 해시 함수를 사용하여, 다음 그 목록을 통해 집합을 추가 반복 해 각각에 해싱 함수를 적용 세트. 다 끝났을 때 코드를 올리거나 심지어 작동하는 것에 가깝게 놓을 것입니다. – Robert

답변으로 샘플 용액 추가 – Robert

내 솔루션은 다음과 같습니다. 그러나 이것이 가장 효율적인 방법 일지 확신 할 수는 없지만 다른 사람들이 자바의 복잡함에 대한 통찰력을 제공 할 수 있습니다.

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; 
}

EDIT : 큰 파일의 경우 StringBuilder를 전달하는 것이 좋습니다.

편집 : 동일한 경로가 동일한 해시 코드를 제공하기 위해,이

출처

2009-07-23 12:45:58 Robert

내가 이것을하고 있었다면, 나의 첫번째 생각은 멀티 맵 (거기에 several implementations이 있거나 자신을 굴릴 수있다)이다.

이 멀티 맵의 키는 노드에 도달하는 데 사용되는 부분 경로이며 값 배열은 목록이 될 것입니다 (순서가 중요하지 않은 경우 집합이 아니며 XML은 중요하지 않은 경우 XML을 공유하는 노드입니다). 부분 경로.

출처

2009-07-23 12:18:07 kdgregory

경로를 기반으로하는 해시의 제한된 세트를 기반으로하는 제한되지 않은 해시 집합

답변

관련 문제