Kodowanie Huffmana: dlaczego nie ma potrzeby stosowania separatora?

17 
Char        Code
====        ====
E           0000
i           0001
y           0010
l           0011
k           0100
.           0101
space       011
e           10
r           1100
s           1101
n           1110
a           1111

Oryginalny tekst:

Niesamowite oczy widziane w pobliżu jeziora

Zakodowane:
0000101100000110011100010101101101001111101011111100011001111110100100101

Dlaczego nie ma potrzeby stosowania separatora w kodowaniu Huffmana?

coding-theory encoding-scheme huffman-coding BufBills
źródło
1
Ponieważ, gdy dekodujesz wartość binarną, bierzesz fragment „od lewej do prawej” bitów, w zależności od tego, co najpierw pasuje do wartości z oryginalnego tekstu. Podobnie jak w tym przypadku, widzisz fragment po lewej stronie (0000) pasujący do E. Jeśli w twoim kodzie char był jakikolwiek symbol o wartości 000, zastąpiłbyś 000 tym symbolem, a następnie zacząłbyś ponownie szukać od pozostałych bitów w sposób „od lewej do prawej”. Dlatego nie potrzebujesz żadnej separacji.
Syed Ali Hamza
1
Pytanie sugeruje, że zwykle potrzebne są separatory. Wiesz już, że nie potrzebujesz separatorów Eerie eyes seen near lake(no oprócz znaku spacji). Ale same postacie nie potrzebują separatorów. Dlaczego tak nie jest?
MSalters
spróbuj samemu go zdekodować, nigdy nie będzie dwuznaczności.
njzk2
@MSalters: Ale separatory są zwykle potrzebne ze słowami o zmiennej długości: cat cheat for mice≠ catch eat form ice. Twoja analogia jest błędna: każda litera jest atomowa; litery są trywialnie rozróżniane i wewnętrznie rozdzielne. Lepszą analogią byłoby „Dlaczego możesz czytać kursywy (odręcznie) skrypt, gdy każde słowo jest tylko jedną długą, kłębiącą się, przecinającą się linią?”, A nawet to kiepska analogia, skoro możesz spojrzeć na odręczne słowo ( lub nawet część jednej) i rozróżniaj poszczególne litery - podczas gdy łańcuch zakodowany w Huffmanie jest bełkotem, jeśli nie widzisz początku.
G-Man mówi „Przywróć Monikę”
@MSalters Nie widzę cię. Nie potrzebuję separatorów dla znaków, ponieważ używamy kodowania o stałej szerokości: każdy kolejny blok ośmiu bitów odpowiada jednemu znakowi. Ale kodowanie Huffmana nie ma stałej szerokości, stąd pytanie.
David Richerby

Odpowiedzi:

50

Nie potrzebujesz separatora, ponieważ kody Huffmana to kody bez prefiksów (również niepomyślnie znane jako „kody prefiksów”). Oznacza to, że żadne słowo kodowe nie jest przedrostkiem żadnego innego słowa kodowego. Na przykład słowo kodowe „e” w twoim przykładzie to 10 i widać, że żadne inne słowo kodowe nie zaczyna się od cyfr 10.

Oznacza to, że możesz zachłannie dekodować, czytając zakodowany ciąg znaków od lewej do prawej i wysyłając znak, gdy tylko zobaczysz słowo kodowe. Na przykład 0, 00 i 000 niczego nie kodują, więc nadal odczytujesz bity. Kiedy czytasz 0000, koduje to „E”, a ponieważ kod nie zawiera prefiksu, wiesz, że nie ma innego słowa kodowego 0000x, więc możesz teraz wypisać „E” i zacząć czytać następne słowo kodowe. Ponownie, 1 nie koduje niczego, ale 10 koduje „e”. Żadne inne słowo kodowe nie zaczyna się od „10”, więc możesz wypisać „e”. I tak dalej.

David Richerby
źródło
1
Kody prefiksów są również powszechnie znane jako kody natychmiastowe (patrz na przykład Elementy teorii informacji autorstwa Cover & Thomas). Myślę, że termin Kod prefiksowy pojawia się znacznie częściej niż kod bez prefiksu.
Batman
3
Warto również wspomnieć, że aby zdekodować sekwencję połączonych kodów Huffmana, należy na początku podać prawidłową granicę słowa kodowego. Jeśli ktoś spróbuje zdekodować sekwencję na niewłaściwej granicy słowa kodowego, proces dekodowania wygeneruje niewłaściwą sekwencję symboli wyjściowych.
rwong
@rwong: Jeśli kod Huffmana zaczyna się niepoprawnie zsynchronizowany, może nadal wyświetlać nieprawidłowe symbole w nieskończoność, ale za każdym razem, gdy nieprawidłowo określa długość symbolu, liczba możliwych złych stanów zostanie zmniejszona.
supercat
@ superupat Myślę, że sformułowałbym to w inny sposób: Jeśli dekoder Huffmana jest początkowo ustawiony na niewłaściwej granicy słowa kodowego i rozpoczyna przetwarzanie, istnieje możliwość (która może wynosić zero lub cokolwiek, i może zależeć zarówno od słownika, jak i bit stream content), że może wylądować na granicy słowa kodowego przez przypadek w skończonym czasie, a kiedy to nastąpi, wygeneruje poprawny wynik dekodowania dla kolejnych symboli. Przeprowadzono pewne badania właściwości (w słowniku słów kodowych i strumieniu bitów), które gwarantowałyby tę ponowną synchronizację.
rwong
@rwong: Jeśli oryginalne dane były losowe z rozkładem takim, że każdy bit strumienia miałby niezależne prawdopodobieństwo bycia jednym lub zerem, prawdopodobieństwo pozostania niezsynchronizowanego dla więcej niż N symboli rozpadłoby się wykładniczo wraz ze wzrostem N. Rzeczywiste dane częściej zawierają wzorce, które mogą uniemożliwić ponowną synchronizację, ale w praktyce jest mało prawdopodobne, aby błąd na początku pliku tekstowego 100 MB spowodował uszkodzenie wszystkich 100 MB tekstu.
supercat
13

Warto wyobrazić sobie to jako drzewo. Po prostu przemierzasz drzewo, dopóki nie trafisz na węzeł liścia, a następnie restartujesz od korzenia. Z algorytmu, który wykonuje kodowanie huffmana, można zobaczyć, że tego rodzaju struktura jest tworzona w procesie.

https://en.wikipedia.org/wiki/File:HuffmanCodeAlg.png

quietContest
źródło
6
Ważnym aspektem jest to, że wszystkie poprawne słowa kodowe to liście. Potrzebujesz separatorów, jeśli masz również symbole na wewnętrznych węzłach.
MvG
3

Żaden kod inny niż E zaczyna się od 0000. Żaden kod inny niż I zaczyna się od 0001. I tak dalej. W skrajnym przypadku żaden kod inny niż e nie zaczyna się od 01. Nie masz takich rzeczy jak E = 0000, spacja = 000, gdzie nie wiedziałbyś, co zrobić, jeśli znajdziesz trzy zera.

Spójrz na zakodowany ciąg: 0000101100000 ...

Czytasz pierwsze zero. Wiesz, że kod to E, i, y, l, k, przecinek lub spacja. Następne zero oznacza, że ​​nie jest to k, przecinek ani spacja, ale E, i, y lub l. Następne zero oznacza, że ​​jest to E lub i. Następne zero oznacza, że ​​to E. Gdy wiesz, który to kod, wiesz, że przeanalizowałeś wszystkie bity dla tego kodu.

Masz 101100000 ... 1 oznacza, że ​​masz e, r, s, n lub a. Następny bit to 0, więc kod to e. Znów skończyłeś z tą postacią.

gnasher729
źródło
-2

Nie możemy używać separatora w kodowaniu Huffmana, ponieważ binarny ekwiwalent każdej litery nie pasuje do prefiksu kodu żadnej litery, więc możemy to zrobić bez użycia separatora.

Sandeep Das
źródło
3
Nie powiedziałem tego wcześniej, tylko bez mylących poziomów wielu zagnieżdżonych negacji. (A tak przy okazji, to nie jest tak, że nie można użyć separatora; tylko, że nie potrzeba do.)
David Richerby