минимальный компрессор-декомпрессор

Тема в разделе "WASM.A&O", создана пользователем Dukales, 16 июн 2011.

  1. Dukales

    Dukales New Member

    Публикаций:
    0
    Регистрация:
    5 июл 2009
    Сообщения:
    199
    Очень интересует минимальный код архиватора, типа http://www.suncloud.ru/workshop/alg...UFFMAN&http://neves.suncloud.ru/help/main.htm или http://www.suncloud.ru/workshop/alg...LEMPEL&http://neves.suncloud.ru/help/main.htm, только более высокоуровневый =) (C, C++, Java). Пусть сжимает не очень, но главное, чтобы мало кода было (текста, а не размер получившегося модуля).
     
  2. Dukales

    Dukales New Member

    Публикаций:
    0
    Регистрация:
    5 июл 2009
    Сообщения:
    199
    Очень жаль...
     
  3. GoldFinch

    GoldFinch New Member

    Публикаций:
    0
    Регистрация:
    29 мар 2008
    Сообщения:
    1.775
    zlib-1.2.5\contrib\puff ?
     
  4. Dmitry_Milk

    Dmitry_Milk Member

    Публикаций:
    0
    Регистрация:
    20 ноя 2007
    Сообщения:
    535
    Если заранее знать тип сжимаемых данных, то иногда можно подобрать достаточно простой алгоритм средней степени паршивости. Скажем, если это сигнал, то частенько можно вылезти за счет дельта-кодирования с существенно уменьшенной разрядностью (не влезающее - полностью, после спецкомбинации), если русскоязычный текст - закодировать пятью битами маленькие буквы (несколько редковстречающихся заменить пробелом и знаками пунктуации, все остальные символы - полностью после спецкода). Ну или более общо - те же коды Хаффмана, если предвычисленные, можно держать в отдельном файле данных/ресурсах, тогда сам исполняемый код архивации/деархивации будет небольшим.
     
  5. Dukales

    Dukales New Member

    Публикаций:
    0
    Регистрация:
    5 июл 2009
    Сообщения:
    199
    Dmitry_Milk
    Спасибо. Значит Хаффман с таблицей - самое очевидное.
     
  6. Dukales

    Dukales New Member

    Публикаций:
    0
    Регистрация:
    5 июл 2009
    Сообщения:
    199
    GoldFinch
    большой
     
  7. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    rle. Кода - копейки.
     
  8. Dukales

    Dukales New Member

    Публикаций:
    0
    Регистрация:
    5 июл 2009
    Сообщения:
    199
    Booster
    это совсем не то))). мне надо сжимать данные общего вида, а не строки, типа "Я - ИНЖЕНЕЕЕЕЕЕЕЕЕРР!!!"
     
  9. valterg

    valterg Active Member

    Публикаций:
    0
    Регистрация:
    19 авг 2004
    Сообщения:
    2.105
    http://www.compression.ru/download/lz.html
    Ищи здесь или в Инете алгоритм/программу lzss (lz77) - простая и относительно эффективная.
    Ищи старые версии, т.к. потом стали бороться за эффективность, увеличилась разрядность и алгоритм распух.
     
  10. klzlk

    klzlk New Member

    Публикаций:
    0
    Регистрация:
    2 июн 2011
    Сообщения:
    449
    Мало встроенных в ось чтоле(не можите заюзать - так это ваши проблемы) ?
     
  11. gazlan

    gazlan Member

    Публикаций:
    0
    Регистрация:
    22 май 2005
    Сообщения:
    414
    Если устраивает лицензия, то aPLib (http://www.ibsensoftware.com/files/aPLib-1.01.zip), правда без исходников, но компактна, неплохо жмет, обкатана, использовалась в нескольких EXE-compressor'ах, включая ASPack.

    То, что у вас по ссылкам - это учебный хлам, забудьте. (И вообще, про этот сайт: http://gazlan.freetzi.com/pix3.html - первые 5 картинок на этой странице). Минимальным по размеру кода будет, наверное, LZW, по размеру сжатого потока - PPM (level 6+).

    Вообще же, результат сильно зависит от размера входного потока. Маленькие файлы (~100 байт) плохо жмут все, на средних неплох Ari, для больших BZ2. Кода там хватает, но кое-какие простые реализации можно посмотреть на сайте Andrew Polar (http://www.ezcodesample.com/)

    На первый случай, в качестве готовой реализации можно взять (очень) старый LZH (http://read.pudn.com/downloads/sourcecode/zip/1519/LZHUF.C__.htm) - LZHUF.C, change:1989-04-01, size:14,630 b - в свое время, это был хит сезона, многие нынешние компрессоры "выросли" из него.
     
  12. TermoSINteZ

    TermoSINteZ Синоби даоса Команда форума

    Публикаций:
    2
    Регистрация:
    11 июн 2004
    Сообщения:
    3.546
    Адрес:
    Russia
    А на питоне не пойдет?
    Код (Text):
    1. >>> import lzw
    2. >>>
    3. >>> mybytes = lzw.readbytes("README.txt")
    4. >>> lessbytes = lzw.compress(mybytes)
    5. >>> newbytes = b"".join(lzw.decompress(lessbytes))
    6. >>> oldbytes = b"".join(lzw.readbytes("README.txt"))
    7. >>> oldbytes == newbytes
    8. True
    Куда уж меньше :)

    Реализация в 10 кб кода (без учета комментов)
     
  13. S_Alex

    S_Alex Alex

    Публикаций:
    0
    Регистрация:
    27 авг 2004
    Сообщения:
    561
    Адрес:
    Ukraine
  14. TermoSINteZ

    TermoSINteZ Синоби даоса Команда форума

    Публикаций:
    2
    Регистрация:
    11 июн 2004
    Сообщения:
    3.546
    Адрес:
    Russia
    S_Alex
    Класс. Спс за ссылку.
     
  15. Dukales

    Dukales New Member

    Публикаций:
    0
    Регистрация:
    5 июл 2009
    Сообщения:
    199
    Вообще мне это надо для того, чтобы была возможность запихивать как можно больше информации статической вместе с исходником в проверяющую систему acm.timus.ru. Допустим идея такая: данные в base64 в строке (const char * data = "\1\22\132\20\0\255"; - это ~14/5 символа на байт - менее выгодно) - превращаются в простые данные. А дальше - ещё и разжимаются. Просто интересно, сколько может унести с собой исходник, размером в 64к символов. Так что мне в идеале надо просто функцию void(*)(void * s, void * d, unsigned sz) минимального размера и сжималку любой сложности и вида под распаковщик.
     
  16. dinoweb

    dinoweb Дмитрий

    Публикаций:
    0
    Регистрация:
    12 окт 2005
    Сообщения:
    129
    Адрес:
    Россия. Красноярск
    А без таких извращений задача не решается? :)

    Тогда скажите что за данные "общего вида" хотите передать. Это должно быть какие-то структурированные данные? Тогда наиболее удобный формат сжатия можно придумать специально под них.
     
  17. gazlan

    gazlan Member

    Публикаций:
    0
    Регистрация:
    22 май 2005
    Сообщения:
    414
    Иными словами, сжимать надо текст небольшого размера (64 K). Я бы выбрал PPM с арифметиком. В свое время искал алго для похожей задачи - хранения HTML pages в DB, PPM показал наилучшее сжатие. Небольшой не получится, но несложно найти готовый.

    Например:
    http://www.codeproject.com/KB/recipes/ppmd.aspx
    http://www.arturocampos.com/ac_ppmc.html
    http://falinc.narod.ru/

    На http://www.compression.ru/ должны быть ссылки на Шкарина и Субботина.
     
  18. Dukales

    Dukales New Member

    Публикаций:
    0
    Регистрация:
    5 июл 2009
    Сообщения:
    199
    gazlan
    Нет. Задача не такая.
    dinoweb
    Да, данные "общего вида". lzhuf.c - выиграл похоже). Круче чем upx себя сжимает =) (конечно с upx-ом ему не сравниться в правильном смысле в любом случае =)).