허프 먼 트리를 사용하여 메시지 디코딩

Question

디코딩 할 비트 열을 보내면 제대로 디코딩 할 때 하나의 추가 비트가 필요합니다. 나는 선주문을하여 나무를 인쇄했고, 종이 위에 나무를 그려 무언가를 놓치지 않았는지 확인했습니다. 선주문과 내 그려진 나무는 일치하지만 정확한 문자를 생성하는 데 필요한 비트는 꺼져 있습니다.

public void decode(String code){ 
    String result = ""; 
    TreeNode current = root; 
    current.preOrder(); 
    for(int i = 0;i < code.length();i++){ 
     //left--0 
     if(Character.getNumericValue(code.charAt(i))==0){ 
      if(current.getLeft() == null){ 
       result += current.getWeight().getLetter(); 
       current = root; 
       i--; 
      }else 
       current=current.getLeft(); 
     } 
     //right--1 
     else if(Character.getNumericValue(code.charAt(i))==1){ 
      if(current.getRight() == null){ 
       result += current.getWeight().getLetter(); 
       current = root; 
       i--; 
      }else 
       current=current.getRight(); 
     } 
    } 
    System.out.println(result); 
} 

오류가 디코딩 방법에 있다고 생각되는 때마다 내 트리가 올바르게 작성됩니다. 그러나 왜 추가 비트가 필요한지 알 수는 없습니다.

Answer 1

노드가 배치 된 것을 보지 않고 나는 단지 추측 할 수 있습니다. 왼쪽/오른쪽으로 이동할 때 잎 노드에 착륙했는지 확인하고 그럴 경우 해당 문자를 방출해야합니다.

if (current.getLeft() == null) { 
    ... 
} 
else { 
    current = current.getLeft(); 
    if (current.isLeaf()) { 
     result += current.getWeight().getLetter(); 
     current = root; 
    } 
} 

오른쪽도 마찬가지입니다.

자신에게

네 번 문자를 추가하고 루트에 현재 노드를 다시 두 줄을 중복되지 않도록하려면 대신 설정할 수있는 플래그를 반복의 끝에서 그것을 확인하지 마십시오 for 블록.

boolean append = false; 
if (Character.getNumericValue(code.charAt(i)) == 0) { 
    if (current.getLeft() == null) { 
     append = true; 
     i--; 
    } 
    else { 
     current = current.getLeft(); 
     if (current.isLeaf()) { 
      append = true; 
     } 
    } 
} 
// same for right side ... 
if (append) { 
    result += current.getWeight().getLetter(); 
    current = root; 
} 

다른 팁

• IllegalArgumentException 던져 default와 switch-0 또는 1 두 if 검사에서 전환합니다.
• 루프를 while으로 전환하면 i의 프리 감소가 다시 증가하고 루프를 중지하지 않도록 방지 할 수 있습니다.
• append으로 시작하여 true으로 설정하면 6 가지 경우 중 4 가지가 추가되기 때문입니다.