Рассмотрим использование алгоритма Хаффмана на пример оптимизации занимаемого пространства а БД при хранении массива, состоящего из целых чисел в диапазоне [0,255]. Массив представляет собой отображение звуковой информации wav-файла. Среднее количество хранимых элемента массива составляет ~20 000. Поиск по данным в данном примере осуществляться не будет.
Вкратце: метод основан на замене наиболее часто повторяющихся символов в сообщении на наиболее короткую последовательность битов, осуществляя тем самым взаимно-однозначное соответствие между ними, тем самым уменьшая длину всего сообщения.
Поскольку среднее значение в массиве колеблется в районе 127, то, предварительно, приведём диапазон к виду [-127,127], тем самым сократив занимаемое пространство на ~1/3.
Результаты представления массива после различных преобразований массива $data с 9288 элементами (в символах):
serialize( $data );
// length: 110694
implode( ',' , $data /*[0,255]*/ );
// length: 36232
implode( ',' , $data /*[-127,127]*/ );
// length: 28202
implode( ',' , $huffman->compress( $data ) );
// length: 21471
base64_encode( $huffman->compress( implode( ',' , $data ) ) );
// length: 14568
$huffman->compress( implode( ',' , $data ) );
// length: 10924
Поскольку замена конкатинации на представление чисел в виде -127..-022..001..002…023..127 ощутимой выгоды не даст (разница составляет 28202-9288*3=338), то мы использовали конкатинацию с разделителем — запятой.
Как видно из результатов, использование метода Хаффмана в данном примере уменьшило занимаемое пространство в БД в 3 раза, по сравнению с обычными способами представления данных.