Почему Python и wc не согласны с количеством байтов?
Python и wc решительно не согласен с количеством байтов (длиной) данной строки:
with open("commedia.pfc", "w") as f:
t = ''.join(chr(int(b, base=2)) for b in chunks(compressed, 8))
print(len(t))
f.write(t)
Output : 318885
$> wc commedia.pfc
2181 12282 461491 commedia.pfc
Файл в основном состоит из нечитаемых символов, поэтому я предоставлю hexdump:
http://www.filedropper.com/dump_2
Файл является результатом сжатия без префикса, если вы спросите, я могу предоставить полный код, который генерирует его вместе с вводимым текстом.
Почему оба байта не равны?
Я добавляю полный код алгоритма сжатия, он выглядит долго, но полон документации и тестов, поэтому его должно быть легко понять:
"""
Implementation of prefix-free compression and decompression.
"""
import doctest
from itertools import islice
from collections import Counter
import random
import json
def binary_strings(s):
"""
Given an initial list of binary strings `s`,
yield all binary strings ending in one of `s` strings.
>>> take(9, binary_strings(["010", "111"]))
['010', '111', '0010', '1010', '0111', '1111', '00010', '10010', '01010']
"""
yield from s
while True:
s = [b + x for x in s for b in "01"]
yield from s
def take(n, iterable):
"""
Return first n items of the iterable as a list.
"""
return list(islice(iterable, n))
def chunks(xs, n, pad='0'):
"""
Yield successive n-sized chunks from xs.
"""
for i in range(0, len(xs), n):
yield xs[i:i + n]
def reverse_dict(dictionary):
"""
>>> sorted(reverse_dict({1:"a",2:"b"}).items())
[('a', 1), ('b', 2)]
"""
return {value : key for key, value in dictionary.items()}
def prefix_free(generator):
"""
Given a `generator`, yield all the items from it
that do not start with any preceding element.
>>> take(6, prefix_free(binary_strings(["00", "01"])))
['00', '01', '100', '101', '1100', '1101']
"""
seen = []
for x in generator:
if not any(x.startswith(i) for i in seen):
yield x
seen.append(x)
def build_translation_dict(text, starting_binary_codes=["000", "100","111"]):
"""
Builds a dict for `prefix_free_compression` where
More common char -> More short binary strings
This is compression as the shorter binary strings will be seen more times than
the long ones.
Univocity in decoding is given by the binary_strings being prefix free.
>>> sorted(build_translation_dict("aaaaa bbbb ccc dd e", ["01", "11"]).items())
[(' ', '001'), ('a', '01'), ('b', '11'), ('c', '101'), ('d', '0001'), ('e', '1001')]
"""
binaries = sorted(list(take(len(set(text)), prefix_free(binary_strings(starting_binary_codes)))), key=len)
frequencies = Counter(text)
# char value tiebreaker to avoid non-determinism v
alphabet = sorted(list(set(text)), key=(lambda ch: (frequencies[ch], ch)), reverse=True)
return dict(zip(alphabet, binaries))
def prefix_free_compression(text, starting_binary_codes=["000", "100","111"]):
"""
Implements `prefix_free_compression`, simply uses the dict
made with `build_translation_dict`.
Returns a tuple (compressed_message, tranlation_dict) as the dict is needed
for decompression.
>>> prefix_free_compression("aaaaa bbbb ccc dd e", ["01", "11"])[0]
'010101010100111111111001101101101001000100010011001'
"""
translate = build_translation_dict(text, starting_binary_codes)
# print(translate)
return ''.join(translate[i] for i in text), translate
def prefix_free_decompression(compressed, translation_dict):
"""
Decompresses a prefix free `compressed` message in the form of a string
composed only of '0' and '1'.
Being the binary codes prefix free,
the decompression is allowed to take the earliest match it finds.
>>> message, d = prefix_free_compression("aaaaa bbbb ccc dd e", ["01", "11"])
>>> message
'010101010100111111111001101101101001000100010011001'
>>> sorted(d.items())
[(' ', '001'), ('a', '01'), ('b', '11'), ('c', '101'), ('d', '0001'), ('e', '1001')]
>>> ''.join(prefix_free_decompression(message, d))
'aaaaa bbbb ccc dd e'
"""
decoding_translate = reverse_dict(translation_dict)
# print(decoding_translate)
word = ''
for bit in compressed:
# print(word, "-", bit)
if word in decoding_translate:
yield decoding_translate[word]
word = ''
word += bit
yield decoding_translate[word]
if __name__ == "__main__":
doctest.testmod()
with open("commedia.txt") as f:
text = f.read()
compressed, d = prefix_free_compression(text)
with open("commedia.pfc", "w") as f:
t = ''.join(chr(int(b, base=2)) for b in chunks(compressed, 8))
print(len(t))
f.write(t)
with open("commedia.pfcd", "w") as f:
f.write(json.dumps(d))
# dividing by 8 goes from bit length to byte length
print("Compressed / uncompressed ratio is {}".format((len(compressed)//8) / len(text)))
original = ''.join(prefix_free_decompression(compressed, d))
assert original == text
commedia.txt это filedropper.com/commedia
2 ответа
Вы используете Python3 и str объект - это означает, что количество вы видите в len(t) количество символов в строке Теперь символы не байты - и это так с 90-х годов.
Поскольку вы не объявляли явную кодировку текста, при записи файла кодируется ваш текст с использованием системной кодировки по умолчанию - в Linux или Mac OS X это будет utf-8 - кодировка, в которой любой символ выпадает из диапазона ASCII (ord(ch) > 127) использует более одного байта на диске.
Итак, ваша программа в основном неверна. Сначала определите, имеете ли вы дело с текстом или байтами. Если вы имеете дело с байтами, откройте файл для записи в двоичном режиме (wbне w) и измените эту строку:
t = ''.join(chr(int(b, base=2)) for b in chunks(compressed, 8))
в
t = bytes((int(b, base=2) for b in chunks(compressed, 8))
Таким образом, становится ясно, что вы работаете с самими байтами, а не искажаете символы и байты.
Конечно, существует уродливый обходной путь для "прозрачного кодирования" текста, который был у вас с байтовым объектом - (если ваш исходный список будет иметь все кодовые точки символов в диапазоне 0–256, то есть): вы могли бы закодировать свой предыдущий t с latin1 кодирование перед записью в файл. Но это было бы неправильно семантически.
Вы также можете поэкспериментировать с малоизвестным Python-объектом "bytearray": он дает возможность работать с элементами, которые являются 8-битными числами и имеют удобство изменчивости и расширяемости (как C-строка, которая будет иметь достаточно места в памяти). предварительно выделено)
@jsbueno прав. Более того, если вы откроете полученный файл в режиме двоичного чтения, вы получите хороший результат:
>>> with open('commedia.pfc', 'rb') as f:
>>> print(len(f.read()))
461491