Алгоритм Хаффмана

Рассмотрим использование алгоритма Хаффмана на пример оптимизации занимаемого пространства а БД при хранении массива, состоящего из целых чисел в диапазоне [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 раза, по сравнению с обычными способами представления данных.

Библиотеки на PHP и JS для реализации алгоритма.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>