경로를 기억하는 동안 효율적인 허프만 트리 검색

Question

내와 관련된 후속 질문으로 Huffman Tree 's를 저장하는 효율적인 방법에 관한 질문 이진 트리를 검색하는 가장 빠르고 효율적인 방법이 무엇인지 궁금해하고 (허프만 코딩 출력을 기반으로) 특정 노드로 가져온 경로를 저장합니다.

이것이 제가 현재 가지고있는 것입니다.

• 루트 노드를 큐에 추가하십시오
• 대기열이 비어 있지 않지만 팝 아이템 오프 큐
  • 그것이 우리가 찾고 있는지 확인하십시오
    • 예 : 헤드 포인터를 루트 노드로 다시 따르고 각 노드에서는 왼쪽인지 오른쪽인지 확인하고 메모를합니다.
    • 검색에서 벗어나십시오
  • Enqueue 왼쪽과 오른쪽 노드

이것은 허프만 나무이기 때문에, 내가 찾고있는 모든 항목이 존재합니다. 위의 것은 폭이 큰 첫 번째 검색으로, 소스에있는 항목이 더 자주 트리에서 더 높아 압축을 더 잘 압축하기 위해 더 높기 때문에 허프만 나무에 가장 적합한 첫 번째 검색입니다. 그러나 추적하는 좋은 방법을 알 수는 없습니다. 노드에 넣은 헤드 포인터를 사용하여 역 추적하지 않고 특정 노드에 도달 한 방법.

이 경우, 나는 또한 우리가 머리를 뿌리로 따라 다니면 뿌리에서 오른쪽, 왼쪽, 왼쪽이라는 것을 알게된다. , 왼쪽 오른쪽. 또는 이진의 001, 내가 찾고있는 것이 효율적인 방식으로 100을 얻는 것입니다.

루트에서 노드로의 경로를 노드 내부의 별도 값으로 저장하는 것도 제안되었지만, 우리가 그 목적을 위해 만든 변수의 많은 비트보다 큰 트리를 가지고 있다면이 분해 될 것입니다. 포인트 데이터 저장은 또한 엄청난 양의 메모리를 차지할 것입니다.

Answer 1

가치 -> 비트 스트링 사전을 만들어 가장 빠른 조회를 제공합니다.

값이 알려진 크기 인 경우 비트 스트링 배열만으로도 인덱스별로 값을 찾을 수 있습니다.

Answer 2

허프만 인코딩 된 데이터를 한 번에 하나씩 해독하는 경우 성능이 좋지 않을 것입니다. 조회 테이블 사용을 피하고 싶은만큼 성능에 관심이 있다면 유일한 방법입니다. 허프만 코드가 만들어지는 방식은 왼쪽에서 오른쪽으로 고유하며 빠른 테이블 조회에 완벽하게 빌려줍니다.