Es gibt Beweise dafür, dass das Huffman-Verfahren für ein festes Eingabealphabet (ohne Zeichenketten zu einem neuen Zeichen zu kombinieren) optimale Ergebnisse liefert. Vielleicht wäre das ein Rechercheansatz für dich.
Was die Kolmogorow-Komplexität (Minimale Größe der komprimierten Daten plus des zum Dekormprimieren benötigten Programms zusammen) angeht, die lässt sich nicht berechnen. Damit lässt sich in der Hinsicht auch keine Optimalität beweisen.
Zitieren
