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