Android и lib.rus.ec, чем сжать (надо open source)?
Есть такая вещь, как Large Text Compression Contest. Алгоритмы соревнуются, кто лучше сожмет гигабайт английской википедии. В настоящее время лидирует алгоритм durilca'kingsize с результатом 125 мегабайт (т.е. сжатие в 8 раз).
Я не знаю, насколько эти алгоритмы завязаны на английский язык, но, кажется, имеет смысл поглядеть на лидеров забега.
Я не знаю, насколько эти алгоритмы завязаны на английский язык, но, кажется, имеет смысл поглядеть на лидеров забега.
По приблизительным подсчётам 7zip с 64MB словарём может сжать до 17-18 ГБ, таким образом я смог бы получить >90%, однако добрые разработчики андроида ограничили размер кучи приложения до 24 МБ (в моём случае таким образом хранить словарь в памяти не получится.А в чём проблема с меньшим словарём? Он не даст достаточного качества сжатия?
(т.е. сжатие в 8 раз).в 8*4 раза, т.к. исходный файл уже сжат bzip2 и разжимается до 4 Гб
edit: у меня из рассмотрения таблички получается вывод, что при ограничении <=24Mb на декомпрессию можно не задумываясь брать bzip2 -9
Есть такая вещь, как Large Text Compression Contest. Алгоритмы соревнуются, кто лучше сожмет гигабайт английской википедии. В настоящее время лидирует алгоритм durilca'kingsize с результатом 125 мегабайт (т.е. сжатие в 8 раз).а) Половина алгоритмов закрыты.
Я не знаю, насколько эти алгоритмы завязаны на английский язык, но, кажется, имеет смысл поглядеть на лидеров забега.
б) Первый алгоритм, уложившийся в чёртовы 24МБ находится на 57-ом месте. А 24 МБ - это ограничение на мощных смартах со Snapdragon + куча памяти. В 16МБ уложился 76-ой алгоритм.
Правда все ещё можно организовать для конкретно этой операции свап.
Эту строчку резервирую для отборной ругани (на которую вслух я не способен) на тех, кто придумал или не смог обойтись без этого лимита.
в) Между кодированием одного файла wiki и кодированием кучи книжек есть существенная разница - в моём случае нужен не произвольный доступ, конечно, но хотя бы быстрый переход к одному из файлов.
в 8*4 раза, т.к. исходный файл уже сжат bzip2 и разжимается до 4 ГбУ меня по нему вопрос: как у него с произвольным доступом? Или прокатит сжать каждый файл в отдельности?
edit: у меня из рассмотрения таблички получается вывод, что при ограничении <=24Mb на декомпрессию можно не задумываясь брать bzip2 -9
в 8*4 раза, т.к. исходный файл уже сжат bzip2 и разжимается до 4 ГбТы что-то напутал.
считай, что его нет. рассказы будет иметь смысл жать группами по N
Ты что-то напутал.что именно?
The test data for the Large Text Compression Benchmark is the first 10^9 bytes of the English Wikipedia dump on Mar. 3, 2006. http://download.wikipedia.org/enwiki/20060303/enwiki-2006030... (1.1 GB or 4.8 GB after decompressing with bzip2).
считай, что его нет. рассказы будет иметь смысл жать группами по NМеня беспокоит время работы читалки, которая будет стоить индекс. Я так понял ей придётся распаковывать ВСЁ. Хотя индекс можно заранее построить.
Ну ты же не думаешь, что повторное применение bzip2 к этому делу ещё в 4 раза объём сокращает? 
Нет конечно. Это Text Compression Contest. Durilka сжимает 4.8 Гб текстовых данных до 125 мегабайт. То, что тестовый набор распространяется в виде 1Гб bzip2-архива не имеет значения.
Иными словами, моё замечание относилось к тому, что 8x сжатие английского текста — довольно посредственный результат, для дурилки правильнее говорить о 32-40х коэффициенте сжатия.
Иными словами, моё замечание относилось к тому, что 8x сжатие английского текста — довольно посредственный результат, для дурилки правильнее говорить о 32-40х коэффициенте сжатия.
Нет конечно. Это Text Compression Contest. Durilka сжимает 4.8 Гб текстовых данных до 125 мегабайт. То, что тестовый набор распространяется в виде 1Гб bzip2-архива не имеет значения.Я уже начал сомневаться в своей адекватности.
Иными словами, моё замечание относилось к тому, что 8x сжатие английского текста — довольно посредственный результат, для дурилки правильнее говорить о 32-40х коэффициенте сжатия.
А как тогда получается, что 4,8ГБ файл, распространяемый сжатым в bzip2 с размером 1ГБ, после распаковки и упаковки тем же bzip2 получается размером всего 250МБ?
а, не, я неправ. сорри. они там вырезают первые 10^9 байт от полученных 4.8 Гб, так что мистики с bzip2 нет, и дурилка жмёт именно в 8 раз
bzip2 -9 (по дефолту 5)Похоже я всё-таки в здравом уме, и ни о чём большем, чем 10x речь пока не идёт.
enwik9: compressed size of first 10^9 bytes of enwiki-20060303-pages-articles.xml.
Я не знаю, насколько эти алгоритмы завязаны на английский языкЗавязываются обычно на структуру текста в целом (например, взаимосвязи между точками в конце предложения и большими буквами в начале следующего плюс иногда используют словарь с популярными словами. На другой язык перенести алгоритм обычно несложно, но требует работы.
Кстати, стоит взглянуть на FreeArc и методы, которые он выберет для текстов либрусека. Он открытый, хороший, а управляющая логика написана на Хаскеле. Хотя для текстов там наверняка PPMD, который охоч до памяти, но может и что-то другое.
32-40х коэффициенте сжатия.Это даже для сжатия видео с потерями неплохо.
Беспотерьное сжатие таким не бывает (если не /dev/null сжимать и для текстов 8 раз - это уже суперхорошо. enwik имеет довольно регулярную структуру (XML plain text сжимается хуже. В свое время В общем, спасибо за замечание, пытаюсь прикрутить bzip2. Хорошо у апача есть свободная реализация.
В свое время бесчеловечные эксперименты Шеннона на людях убедительно померяли энтропию английского текста (отнюдь не по его знаменитой формуле). Получилась как раз в районе 1 бита на символ.лол, забавное совпадение.
Оставить комментарий
agaaaa
Загорелся идеей впихнуть зеркало lib.rus.ec на свой Андроид-телефон. В несжатом состоянии библиотека весит ~66ГБ. В zip - ~26. Однако меня душит жаба покупать новую SD карточку.По приблизительным подсчётам 7zip с 64MB словарём может сжать до 17-18 ГБ, таким образом я смог бы получить >90%, однако добрые разработчики андроида ограничили размер кучи приложения до 24 МБ (в моём случае таким образом хранить словарь в памяти не получится. Конечно можно хранить его в файле, оставляя на долю ОС кэширование при доступе, однако к этому способу прибегать не хотелось бы.
С другой стороны, я бы с удовольствием написал (или встроил, если лицензия позволит) для FBReaderJ какой-нибудь специализированный алгоритм, который мог бы хорошо сжать огромную кучу текстовых файлов.
Какие будут соображения?