패키지-머지 알고리즘

Package-merge algorithm

패키지-머지 알고리즘은 코드 워드가 L보다 길지 않은 n 크기의 주어진 알파벳에서 주어진 분포를 위한 최적의 길이 제한 허프만 코드를 찾기 위한 O(nL) 시간 알고리즘이다.욕심 많은 알고리즘이며, 허프먼의 원래 알고리즘을 일반화한 것이다.패키지 머지는 코드 구성 문제를 이진 코인 수집기 문제로 줄임으로써 작동한다.[1]

동전 수집기의 문제

동전 수집가가 다양한 액면가의 동전을 여러 개 가지고 있다고 가정해 보자. 각 액면가에는 해당 액면가와 무관한 숫자 값이 있다.동전 수집가는 돈이 다 떨어져서 동전 수집의 일부를 사용하여 N원가의 물건을 사야 한다.그는 그의 최소 숫자 값 모음에서 동전들의 부분집합을 선택하기를 원한다. 그 숫자는 총 N이다.

이 문제의 2진법은 모든 액면가가 2달러, 즉 1달러, 2달러, 2달러, 4달러의 힘이라는 것이다.

패키지-머지 알고리즘 설명

가장 큰 단위는 1달러, N은 정수라고 가정해 보자.(알고리즘은 이러한 가정이 유지되지 않더라도 사소한 수정으로 작동한다.)동전 수집가는 우선 그의 동전을 수치로 분류하여 각 단위의 목록으로 분류한다.그런 다음 그는 가장 작은 단위 동전을 쌍으로 포장하는데, 이는 가장 작은 총 숫자 값의 쌍에서 출발한다.만약 동전이 하나 남아 있다면, 그것은 그 화폐의 가장 높은 수치의 동전이 될 것이고, 그것은 따로 남겨져 있고 앞으로 무시된다.그리고 나서 이 소포들은 다음으로 가장 작은 단위의 동전 목록으로, 다시 숫자 값의 순서로 합쳐진다.그 목록에 있는 항목은 쌍으로 포장되어 다음으로 가장 작은 목록으로 병합된다.

마지막으로 품목 리스트가 있는데, 각 품목은 1달러짜리 동전이나 2개 이상의 작은 동전들로 구성된 패키지로서 총 1달러짜리 지폐가 있다.그것들은 또한 숫자값의 순서로 정렬된다.그런 다음 동전 수집기는 그것들 중 최소값 N을 선택한다.

알고리즘의 시간은 동전의 수에서 선형이라는 점에 유의한다.

코인 수집기 문제에 대한 길이제한 허프먼 코딩 감소

어떤 코드 워드의 최대 길이가 되도록 L을 두어라.p1, …, p를n 인코딩할 알파벳 기호의 주파수가 되게 한다.우리는 먼저 기호들을 분류해서 pi ≤ pi+1. 각 기호, 2−1, …, 2의−L 각 숫자 값i p에 대한 L 동전을 만들어라.package-merge 알고리즘을 사용하여 최소 숫자 값의 코인 집합(단위: 총 n - 1)을 선택한다. h를i 선택한 숫자i 값 p의 코인 수로 한다.최적의 길이제한 허프먼 코드는 기호 i를 길이 h의i 비트 문자열로 인코딩한다.표준적인 허프만 코드는 h가i 알려져 있다는 점에서 단순한 상향식 탐욕적인 방법으로 쉽게 구성할 수 있으며, 이것이 빠른 데이터 압축의 기반이 될 수 있다.[2]

성능 개선 및 일반화

이 감소로 알고리즘은 O(nL)-시간과 O(nL)-공간이 된다.다만 원본인 '최적 길이제한 허프만 코드에 대한 빠른 알고리즘'은 이를 O(nL)-시간과 O(n)-공간으로 개선할 수 있는 방법을 보여준다.이 아이디어는 알고리즘을 처음 실행하는 것으로, 원래 문제의 절반 크기에 해당하는 두 개의 동등한 하위 문제를 결정할 수 있을 정도의 데이터만 보관하는 것이다.이것은 재귀적으로 행해져, 약 두 배 정도의 시간이 걸리지만 선형 공간만 필요로 하는 알고리즘이 만들어진다.[1]

패키지-머지 알고리즘에는 여러 가지 개선사항이 적용되어 승수 상수를 줄이고 ps를i 반복하는 문제와 같은 특별한 경우 이를 더 빨리 만들 수 있다.[3]패키지 머지 접근법은 알파벳 코딩과 같은 관련 문제에도 적용되었다.[4]

그래프 이론과 관련된 방법들은 패키지-머지 알고리즘보다 점증적 공간 복잡성이 더 나은 것으로 나타났지만, 이것들은 그다지 실용적인 적용으로 보지 못했다.

참조

  1. ^ a b Larmore, Lawrence L.; Hirschberg, Daniel S. (1990). "A fast algorithm for optimal length-limited Huffman codes". Journal of the Association for Computing Machinery. 37 (3): 464–473. doi:10.1145/79147.79150. S2CID 11696729.
  2. ^ Moffat, Alistair; Turpin, Andrew (Oct 1997). "On the implementation of minimum redundancy prefix codes". IEEE Transactions on Communications. 45 (10): 1200–1207. doi:10.1109/26.634683.
  3. ^ Witten, Ian H.; Moffat, Alistair; Bell, Timothy Clinton (1999). Managing Gigabytes: Compressing and indexing documents and images (2 ed.). Morgan Kaufmann Publishers. ISBN 978-1-55860-570-1. 1558605703.
  4. ^ Larmore, Lawrence L.; Przytycka, Teresa M. (1994). "A Fast Algorithm for Optimal Height-Limited Alphabetic Binary-Trees". SIAM Journal on Computing. 23 (6): 1283–1312. doi:10.1137/s0097539792231167.

외부 링크

  • Baer, Michael B. (2006). "Twenty (or so) Questions: D-ary Length-Bounded Prefix Coding". arXiv:cs.IT/0602085.
  • Moffat, Alistair; Turpin, Andrew; Katajainen, Jyrki (March 1995). Space-Efficient Construction of Optimal Prefix Codes. IEEE Data Compression Conference. Snowbird, Utah, USA. doi:10.1109/DCC.1995.515509.
  • 패키지-머지 알고리즘 "[1]"의 구현
  • 패키지-머지 알고리즘을 사용하는 고속 엔트로피 코더 [2]