Алгоритм сжатия коротких сообщений

Тема в разделе "WASM.A&O", создана пользователем Sov, 2 дек 2007.

  1. asmlamo

    asmlamo Well-Known Member

    Публикаций:
    0
    Регистрация:
    18 май 2004
    Сообщения:
    1.729
    Код не мой ... но народ тестил говорит там есть трабла с длинными сообщениями ... длинной более 64 к
     
  2. S_Alex

    S_Alex Alex

    Публикаций:
    0
    Регистрация:
    27 авг 2004
    Сообщения:
    561
    Адрес:
    Ukraine
    Да, для текста самое то, жмет хорошо. Проверено.
     
  3. Sov

    Sov New Member

    Публикаций:
    0
    Регистрация:
    29 авг 2007
    Сообщения:
    20
    gazlan
    Спасибо, воспользуюсь библиотекой
     
  4. drmist

    drmist New Member

    Публикаций:
    0
    Регистрация:
    31 май 2005
    Сообщения:
    112
    Хаффмана не советую использовать - медленный и жмет не очень.
    Аплиб самое то. Или самопальный LZSS.
     
  5. Scratch

    Scratch New Member

    Публикаций:
    0
    Регистрация:
    1 янв 2005
    Сообщения:
    161
    ..а почему не zlib? помойму неплохой вариант
     
  6. gazlan

    gazlan Member

    Публикаций:
    0
    Регистрация:
    22 май 2005
    Сообщения:
    414
    Ацтой. Не говоря уже о том, что _короткие_ тексты сжимать вообще не будет.
     
  7. Xerx

    Xerx Алексей

    Публикаций:
    0
    Регистрация:
    17 фев 2005
    Сообщения:
    528
    Адрес:
    Russia
    Для сжатия текста лучше всего семейство PPM. Т.к. текст короткий, то и порядок подойдет небольшой - 2-3.
    Есть много реализаций на http://compression.ru
     
  8. gazlan

    gazlan Member

    Публикаций:
    0
    Регистрация:
    22 май 2005
    Сообщения:
    414
    PPM выгоден для (очень) больших текстов (> 1 Mb). Для _коротких_ текстов "сжатие", скорее всего, будет отрицательным. Для файлов в несколько Kb (HTML-странички) PPM (даже очень высоких порядков: 8..16 ) по компрессии сравним с LZ.
     
  9. Xerx

    Xerx Алексей

    Публикаций:
    0
    Регистрация:
    17 фев 2005
    Сообщения:
    528
    Адрес:
    Russia
    А почему бы сначала не преобразовать текст BWT, затем передать его MTF или DC и в итоге сжать арифметическим целочисленным кодером?

    BWT - http://en.wikipedia.org/wiki/Burrows-Wheeler_transform
    MTF - http://en.wikipedia.org/wiki/Move-to-front_transform

    P.S. Еще могут быть полезны:
    http://faqs.org.ru/progr/common/bwt.htm
    http://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D1%81%D0%B6%D0%B0%D1%82%D0%B8%D1%8F_%D0%B1%D0%B5%D0%B7_%D0%BF%D0%BE%D1%82%D0%B5%D1%80%D1%8C

    P.P.S. Вместо BWT не стоит использовать преобразование ST, текст короткий и смысла особого нет.
     
  10. gazlan

    gazlan Member

    Публикаций:
    0
    Регистрация:
    22 май 2005
    Сообщения:
    414
    Бессмысленно для _коротких_ сообщений. BWT практически начнет работать при размере блока в десятки килобайт.
    MTF - чуть раньше. Арифметика на коротких текстах проигрывает LZ (и вообще, не так много выигрывает у Хаффмановского сжатия, при этом сильно уступая по скорости).
     
  11. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.077
    ну, ребята, вы разошлись:)) - выше уже предложены решения, а вы всё остановится не можете:)).
     
  12. drmist

    drmist New Member

    Публикаций:
    0
    Регистрация:
    31 май 2005
    Сообщения:
    112
    >> PPM
    не очень прост в реализации и памяти много требуется
    для небольших строк LZ - самое оно
     
  13. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.077
    drmist
    для определённости
    это сколько симболов:))??