Измерение эффективности кодирования Хаффмана с помощью цепочки битов Python - PullRequest
Новая
       28

Измерение эффективности кодирования Хаффмана с помощью цепочки битов Python

4 голосов
/ 08 ноября 2011

У меня есть следующая строка, которую я хотел бы кодировать Хаффманом и эффективно хранить в битовом массиве: 

>>> print sequence
GTCAGGACAAGAAAGACAANTCCAATTNACATTATG|

Частоты символов в sequence: 

>>> print freqTuples
[(0.40540540540540543, 'A'), (0.1891891891891892, 'T'), (0.16216216216216217, 'C'), (0.16216216216216217, 'G'), (0.05405405405405406, 'N'), (0.02702702702702703, '|')]`

Я перевожу это в словарь кодов Хаффмана: 

>>> print codeDict
{'A': '1', 'C': '010', 'G': '001', 'N': '0110', 'T': '000', '|': '0111'}

Затем я использовал пакет Python bitstring для перевода строки, символ за символом, в экземпляр класса BitArray, который я называю bitArray, который содержит биты для каждого символа, закодированного с помощью соответствующего кода Хаффмана. : 

>>> print bitArray.bin
0b001000010100100110101100111100110101101100000100101100000001101010100000010000010111

Вот битовый массив в байтах: 

>>> print bitArray.tobytes()
!I\254\363[^D\260^Z\240Ap

Я должен использовать tobytes() вместо bytes, так как сгенерированный битовый массив не делится равномерно на 8-битные сегменты.

Когда я вычисляю эффективность хранения представления BitArray (соотношение размеров массива битов и входной строки), я получаю худшую производительность, чем если бы я оставил входную строку без кодировки: 

>>> sys.getsizeof(bitArray.tobytes()) / float(len(sequence))
1.2972972973

Правильно ли я измеряю эффективность хранения? (Если я кодирую более длинные входные строки, это соотношение улучшается, но кажется, что оно приближается к асимптотическому пределу около 0,28. Я хотел бы подтвердить, что это правильный способ измерения.)

Редактировать

Следующие два подхода дают разные ответы: 

>>> print len(bitArray.tobytes()) / float(len(mergedSequence))
0.297297297297

>>> print bitArray.len / (8.*len(mergedSequence))
0.283783783784

Я не уверен, во что верить. Но в процессе записи данных в хранилище я думаю, что мне понадобится байтовое представление, что заставляет меня склоняться к выбору первого результата.

Ответы [ 3 ]

2 голосов
/ 08 ноября 2011 
>>> sys.getsizeof(bitArray.tobytes()) / float(len(sequence))
1.2972972973

Подразумевается, что кодированная версия на 30% длиннее , чем исходная последовательность.

Я не думаю, что вы хотите использовать getsizeof здесь - если вы хотитечтобы минимизировать размер объекта Python, вы должны также использовать getsizeof(sequence), а не len.

Если вместо этого вы хотите сделать то, для чего предназначено кодирование Хаффмана, и минимизировать двоичный файлпредставление, тогда вы хотите использовать len на оба (при условии, что последовательность представляется как один байт на символ).

Итак, ваше реальное соотношение составляет 11/37.

Я предполагаю, что вы используете кодирование Хаффмана в качестве упражнения, так как это не похоже на логический способ эффективно хранить то, что является просто четырехбитным кодом с символом завершения.По крайней мере, было бы лучше использовать арифметическое кодирование, которое позволит вам использовать кодирование base-5 вместо base-2, которое оптимально для 5 возможных символов.

Действительно, я бы предположил, что в последовательности, достаточно длинной, чтобы ее можно было сжать, существует известное соотношение G: A: C: T и / или 2-битное кодирование фиксированной длины будет столь же эффективным (Соотношения приближаются к 1: 1: 1: 1), поскольку вам не нужно кодировать символ завершения.

2 голосов
/ 08 ноября 2011

Я не совсем уверен в том, что такое bitarray, но разве вы не можете просто сделать: 

>>> len(bitArray.tobytes()) / float(len(sequence))

Я не говорю, что это решит вашу проблему, но может случиться так, что вещь "getizeof" (опять же, кое-что, с чем я не очень хорошо знаком), отбрасывает вас.

Из того, что вы там написали, похоже, что вы немного сравниваете яблоки с апельсинами.

1 голос
/ 08 ноября 2011

Вы знаете, что ответ неправильный, потому что словарь Хаффмана меньше 4 бит на символ, поэтому реальный ответ должен быть меньше 0,5. Если словарь и частота символов не изменяются для более длинных строк, то степень сжатия не должна уменьшаться до асимптотического предела по мере увеличения длины строки.

Из документации sys: 

"getsizeof() calls the object’s __sizeof__ method and adds
 an additional garbage collector overhead if the object is
 managed by the garbage collector."

Вам нужна функция, которая будет возвращать длину самой цепочки битов, а не заголовок + заголовок. В документации BitString говорится, что свойство len или length возвращает длину в битах. Так что попробуйте: 

bitArray.len / 8.*len(sequence)
...