Huffman-kode for ett tegn
Hva er høyden på huffmantrær med ett tegn, si a – blir det 0, med a som øverste node, eller vil man ha en node med a som barn og høyde 1?
Det er litt tricky, da. Sånne grensetilfeller vil ofte trenge litt ekstra tweaking. For greia er at en Huffman-kode for et alfabet med ett tegn trenger ingen bits. Koden for det ene symbolet vil bare være den tomme strengen. Meen så er spørsmålet hvordan man da skal vite hvor mange tomme koder det er i den tomme teksten. Lengden vil jo være lagret, men den er uansett bare 0.
Like fullt, om man ser hvordan Cormen mfl. håndterer kodene og trærne så sier de jo f.eks. at hvis
\(C\) is the alphabet from which the characters are drawn and all character frequencies are positive, then the tree for an optimal prefix-free code has exactly \(|C|\) leaves, one for each letter of the alphabet, and \(|C|−1\) internal nodes […].
Dette tilsier jo at om \(|C|=1\), så har man ingen interne noder, dermed ingen kanter, og høyden er 0.
Om du ser på pseudokoden og beskrivelsen av Huffman (s. 434), så ser du også at den vil i dette tilfelle redusere til å lage ett tre som består av kun det ene tegnet i \(C\) som rot. Altså med høyde 0. Dette vil jo naturligvis være optimalt, men man kan jo spørre seg om hvordan man da vil kunne lese den resulterende teksten.
Det er mulig Cormen mfl. har noen detaljer der jeg ikke har funnet i farten, men min forståelse er i hvert fall at (i) et Huffman-tre (altså bygget med Huffman) for et alfabet med ett symbol vil ha høyde 0, og koden for symbolet vil bestå av 0 bits, og (ii) man vil ikke entydig kunne dekode en tekst som er kodet med denne koden. For å gjøre dette entydig må man kode både lengden på den kodede strengen (i dette tilfellet null) og lengden på den opprinnelige strengen. Dette kan man riktignok gjøre uten ekstra lagringsplass, siden vi bare trenger én av de to lengdene. Om vi av koden (som også legges ved; se oppg. 15.3-5) kan se at alfabetet kun har ett tegn, så vet vi (hvis vi gjør det på denne måten) at lengden gjelder den opprinnelige strengen; ellers vet vi at den gjelder den kodede strengen.
Men dette er altså bare mitt forslag til hvordan man kan håndtere situasjonen. I den «normale» beskrivelsen har man jo bare en bitstreng, som er definert av sin lengde og sine bits, og den vil være tom, så man kan ikke avgjøre hvor lang den opprinnelige strengen var. Like fullt er det dette Huffman gjør, så et Huffman-tre for ett tegn har høyde 0.