Алгоритм Хаффмана
Рассмотрим использование алгоритма Хаффмана на пример оптимизации занимаемого пространства а БД при хранении массива, состоящего из целых числ в диапазоне [0,255]. Массив представляет собой отображение звуковой информации wav-файла. Среднее количество хранимых элемента массива составляет ~20 000. Поиск по данным в данном примере осуществляться не будет.
Вкратце: метод основан на замене наиболее часто повторяющихся символов в сообщении на наиболее короткую последовательность битов, осуществляя тем самым взаимно-однозначное соответствие между ними, тем самым уменьшая длину всего сообщения.
Поскольку среднее значение в массиве колеблется в районе 127, то, предварительно, приведём диапазон к виду [-127,127], тем самым сократив занимаемое пространство на ~1/3.
Результаты представления массива после различных преобразований массива $data с 9288 элементами (в символах):
1 2 3 4 5 6 7 8 9 10 11 12 | 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 для реализации алгоритма.