허프만 코드 : 예제, 응용 프로그램
현재로서는 소수의 사람들이 그 사실에 대해 생각합니다.압축 방법. 과거에 비해 개인용 컴퓨터를 사용하는 것이 훨씬 쉬워졌습니다. 실제로 파일 시스템을 사용하는 모든 사람은 아카이브를 사용합니다. 그러나 그들이 일하는 방식과 파일의 압축 원리에 대해 생각하는 사람은 거의 없습니다. 이 과정의 첫 번째 버전은 허프만 코드 였고, 여전히 다양한 인기 아카이브에 사용되었습니다. 많은 사용자는 파일을 압축하는 것이 얼마나 쉬운 지 생각해보고 어떤 방식으로 작동하는지 생각조차하지 않습니다. 이 기사에서는 압축을 수행하는 방법, 인코딩 과정을 가속화하고 단순화하는 데 도움이되는 요소를 살펴보고 코딩 트리를 구성하는 원리에 대해 알아 봅니다.
알고리즘의 역사
효과적인 첫 번째 알고리즘전자 정보의 코딩은 허프만이 20 세기 중반, 즉 1952 년에 제안한 코드였다. 현재 정보를 압축하기 위해 만들어진 대부분의 프로그램의 기본 요소입니다. 현재이 코드를 사용하는 가장 인기있는 소스 중 하나는 ZIP, ARJ, RAR 아카이브 및 기타 많은 소스입니다.
효율적인 코딩 원칙
허프만 알고리즘의 기본 원리는가장 가능성이 높고 자주 만나는 심볼을 이진 시스템의 코드로 대체 할 수 있습니다. 그리고 덜 공통적 인 것은 더 긴 코드로 대체됩니다. 긴 허프만 코드로의 전환은 시스템이 모든 최소값을 사용한 후에 만 발생합니다. 이 기술을 사용하면 전체 원본 메시지의 각 문자에 대한 코드 길이를 최소화 할 수 있습니다.
허프만 코드, 예제
알고리즘을 설명하기 위해코드 트리 구조의 그래픽 버전. 이 방법을 사용하는 것이 효과적이므로이 방법의 개념에 필요한 일부 값의 정의를 명확히하는 것이 좋습니다. 노드에서 노드로 전달되는 호 집합과 노드 집합은 대개 그래프라고합니다. 트리 자체는 특정 속성 집합을 가진 그래프입니다.
- 각 노드에서 하나 이상의 호를 입력 할 수 없습니다.
- 노드 중 하나가 트리의 루트 여야합니다. 즉 호가 전혀 들어 가지 않아야합니다.
- 루트에서 호를 따라 움직이기 시작하면이 프로세스가 노드 중 하나에 완전히 들어갈 수 있어야합니다.
허프만에 따라 나무를 만들기위한 알고리즘
허프만 코드의 구성은 문자로 이루어집니다.입력 알파벳의 향후 코드 트리에서 비어있는 노드 목록이 작성됩니다. 이 목록의 각 노드의 가중치는이 노드에 해당하는 메시지 문자의 발생 확률과 같아야합니다. 이 경우 미래 나무의 몇 가지 자유 노드 중에서 가장 무게가 덜 나가는 노드가 선택됩니다. 동시에, 최소 표시자가 여러 노드에서 관찰되는 경우 자유롭게 쌍을 선택할 수 있습니다.
압축 효율 향상
압축 효율을 높이려면트리에 첨부 된 특정 파일에 나타나는 문자의 확률에 관한 모든 데이터를 사용하고 많은 수의 텍스트 문서에 흩어 지도록 허용하지 않는 코드 트리를 작성하는 데 걸리는 시간. 이 파일을 처음 검토 할 경우 압축 할 개체의 문자 수 빈도에 대한 통계를 즉시 계산할 수 있습니다.
압축 프로세스의 가속화
알고리즘의 속도를 높이기 위해 문자의 정의이 편지 또는 편지의 출현 확률 및 출현 빈도에 대한 지표를 작성하지 않아야합니다. 덕분에이 알고리즘은 더 간단 해지고 작업이 크게 빨라졌습니다. 또한 부동 쉼표 및 구분과 관련된 작업을 피할 수 있습니다.
결론
허프만 코드 - 간단하고 오래 설립알고리즘으로, 잘 알려진 많은 프로그램과 회사에서 사용되고 있습니다. 단순성과 명료성으로 인해 모든 크기의 파일에 대해 효과적인 압축 결과를 얻고 스토리지 디스크에서 차지하는 공간을 크게 줄일 수 있습니다. 즉, 허프만 알고리즘은 오랫동안 연구되고 잘 설계된 방식이며, 관련성은 현재까지 감소하지 않습니다.
