Дерево Хаффмана для больших файлов

Question

Я искал в Интернете, но не смог найти то, что мне нужно.

Мне нужно сжать большие файлы, используя кодировку Хаффмана. Моя идея состояла в том, чтобы прочитать первую 1-2 файла

(чтобы избежать первого чтения всего файла, чтобы построить дерево, а затем читать его еще раз, чтобы кодировать его, избегая O (2n)),

и построить дерево Хаффмана. Если какой-либо из 256 байтов алфавита отсутствует, я бы добавил его сам, если он появится позже в файле (а не в первых 1-2 МБ). Но пытаться проверить результат с помощью этого:

int * totalFr = new int[256]; 
unsigned char * symArr= new unsigned char[256]; 

for (int i = 0; i < 256; i++) 
{ 
    totalFr[i] = i; 
    symArr[i] = unsigned char(i); 
} 

int size = sizeof(symArr)/sizeof(symArr[0]); 
buildHuffmanTree(totalFr,symArr, size); 
delete[] totalFr; 
delete[] arrei; 

где buildHuffmanTree это функция, которая строит дерево Хаффмана, сделал мой Осознайте лучший символьный код, я мог бы получить было 7 битов, например 0000001.

И вот откуда мой вопрос пришел - стоит ли построить дерево Хаффмана для полного 256-буквенного алфавита? Или лучше использовать адаптивное кодирование Хаффмана для фрагментов, таких как 1-2MB

Answer 1

Вы не можете ожидать многого из кодирования Хаффмана, если данные не являются чрезвычайно предвзятыми относительно того, какие байты присутствуют. Я просто попробовал 100-килобайтный файл английского текста из Википедии. Он получил файл до 63% от его первоначального размера, поэтому, возможно, восемь бит до пяти бит в среднем. Также это делал Хаффман в блоках примерно по 16 КБ за раз, чтобы код был адаптирован к каждому блоку.

Нормальное сжатие zlib, которое также ищет соответствующие строки, снижает его до 35% от исходного размера. Более продвинутые компрессоры, такие как xz, которые тратят больше времени и памяти, все более и более ищущие для соответствия строк, а также немного лучше, чем кодирование Хаффмана, снижают его до 26% от исходного размера.