Algorytm scalania pakietów - Package-merge algorithm

Algorytm pakiet seryjnej jest O (NL) -czas Algorytm znalezienia optymalnej długości ograniczone kodu Huffmana dla danego rozkładu w danym alfabetu wielkości n , gdzie nie słowo kodowe jest dłuższy niż L . Jest to algorytm zachłanny i uogólnienie oryginalnego algorytmu Huffmana . Scalanie pakietów działa poprzez zredukowanie problemu konstrukcji kodu do problemu binarnego kolekcjonera monet .

Problem kolekcjonera monet

Załóżmy, że kolekcjoner monet ma kilka monet o różnych nominałach, z których każda ma wartość numizmatyczną niezwiązaną z jej nominałem. Kolekcjonerowi monet skończyły się pieniądze i musi wykorzystać część swojej kolekcji monet, aby kupić coś, co kosztuje N . Chce wybrać podzbiór monet ze swojej kolekcji o minimalnej wartości numizmatycznej, których nominały łącznie N .

Binarna wersja tego problemu polega na tym, że wszystkie nominały są potęgami 2, czyli 1, 1/2, 1/4 itd. Dolarów.

Opis algorytmu scalania pakietów

Załóżmy, że największy nominał to 1 dolar, a N jest liczbą całkowitą. (Algorytm działa, nawet jeśli te założenia się nie spełnią, dzięki trywialnym modyfikacjom.) Kolekcjoner monet najpierw rozdziela swoje monety na listy, po jednej dla każdego nominału, posortowane według wartości numizmatycznej. Następnie pakuje monety o najmniejszych nominałach parami, zaczynając od pary o najmniejszej łącznej wartości numizmatycznej. Jeśli pozostanie jedna moneta, będzie to moneta o najwyższej wartości numizmatycznej tego nominału i odtąd jest odkładana na bok i ignorowana. Pakiety te są następnie dołączane do listy monet o kolejnym najmniejszym nominale, ponownie w kolejności wartości numizmatycznej. Pozycje z tej listy są następnie pakowane w pary i łączone w następną najmniejszą listę i tak dalej.

Na koniec znajduje się lista przedmiotów, z których każdy jest monetą jednodolarową lub pakietem składającym się z dwóch lub więcej mniejszych monet o nominale 1 dolara. Są one również sortowane według wartości numizmatycznej. Kolekcjoner monet wybiera następnie najmniejszą wartość N z nich.

Zwróć uwagę, że czas działania algorytmu jest liniowy w stosunku do liczby monet.

Skrócenie ograniczonego długości kodowania Huffmana do problemu kolekcjonera monet

Niech L będzie maksymalną długością, jaką może mieć dowolne słowo kodowe. Niech p 1 , …,  p n będą częstotliwościami zakodowanych symboli alfabetu. Najpierw sortujemy symbole tak, że p i  ≤  p i +1 . Utwórz monety L dla każdego symbolu o nominałach 2 −1 , …, 2 − L , każdy o wartości numizmatycznej p i . Za pomocą algorytmu scalania pakietów wybierz zbiór monet o minimalnej wartości numizmatycznej, których nominały łącznie n  − 1. Niech h i będzie liczbą wybranych monet o wartości numizmatycznej p i . Długość ograniczona optymalny kod Huffman zakoduje symbol I z ciągu bitów o długości h I . Kanoniczne kodu Huffmana może być łatwo zbudowany w prosty sposób oddolnym chciwego, zważywszy, że H I są znane i mogą być podstawą szybkiego kompresji danych .

Ulepszenia wydajności i uogólnienia

Przy tej redukcji algorytm jest O(nL) -czas i O(nL) -przestrzeń. Jednak oryginalna praca, " Szybki algorytm dla optymalnych kodów Huffmana o ograniczonej długości ", pokazuje, jak można to ulepszyć do czasu O(nL) i przestrzeni O(n) . Pomysł polega na uruchomieniu algorytmu po raz pierwszy, zachowując tylko wystarczającą ilość danych, aby móc określić dwa równoważne podproblemy, które sumują się do połowy pierwotnego problemu. Odbywa się to rekurencyjnie, co skutkuje algorytmem, który zajmuje około dwa razy więcej czasu, ale wymaga tylko przestrzeni liniowej.

W algorytmie scalania pakietów wprowadzono wiele innych ulepszeń w celu zmniejszenia stałej multiplikatywnej i przyspieszenia jej w szczególnych przypadkach, takich jak problemy z powtarzającymi się p is . Podejście polegające na łączeniu pakietów zostało również dostosowane do powiązanych problemów, takich jak kodowanie alfabetyczne .

Wykazano, że metody wykorzystujące teorię grafów mają lepszą asymptotyczną złożoność przestrzeni niż algorytm scalania pakietów, ale nie znalazły one tak dużego praktycznego zastosowania.

Bibliografia

  1. ^ B Larmore Lawrence L. ; Hirschberg, Daniel S. (1990). „Szybki algorytm dla optymalnych kodów Huffmana o ograniczonej długości”. Czasopismo Stowarzyszenia Maszyn Komputerowych . 37 (3): 464–473. doi : 10.1145/79147.79150 .
  2. ^ Moffat, Alistair ; Turpin, Andrew (październik 1997). „W sprawie wdrożenia minimalnych kodów prefiksów redundancji”. Transakcje IEEE dotyczące komunikacji . 45 (10): 1200–1207. doi : 10.1109/26.634683 .
  3. ^ Witten, Ian H .; Moffat, Alistair ; Dzwon, Timothy Clinton (1999). Zarządzanie gigabajtami: kompresowanie i indeksowanie dokumentów i obrazów (2 wyd.). Wydawnictwo Morgana Kaufmanna . Numer ISBN 978-1-55860-570-1. 1558605703.
  4. ^ Larmore, Lawrence L .; Przytyckiej, Teresie M. (1994). „Szybki algorytm dla optymalnych alfabetycznych drzew binarnych o ograniczonej wysokości”. SIAM Journal on Computing . 23 (6): 1283–1312. doi : 10.1137/s0097539792231167 .

Zewnętrzne linki

  • Baer, ​​Michael B. (2006). „Dwadzieścia (lub więcej) pytań: D- arne kodowanie prefiksu ograniczonego długością”. arXiv : cs.IT/0602085 .
  • Moffat, Alistair ; Turpin, Andrzeju; Katajainen, Jyrki (marzec 1995). Efektywna przestrzennie konstrukcja optymalnych kodów przedrostkowych . Konferencja kompresji danych IEEE. Snowbird, Utah, USA. doi : 10.1109/DCC.1995.515509 .
  • Implementacja algorytmu scalania pakietów " [1] "
  • Szybki koder entropii wykorzystujący algorytm scalania pakietów [2]