Важная информация

User Tag List

Страница 1 из 7 12345 ... ПоследняяПоследняя
Показано с 1 по 10 из 67

Тема: Оптимальное LZ-кодирование

  1. #1

    По умолчанию Оптимальное LZ-кодирование

    Ситуация: есть некий файл, его хочется запаковать LZ-методом.
    Файл гружу в память и для каждого байта строю набор всех подходящих к нему LZ-кодов (длина, смещение, размер кода в битах).

    Надо: выбрать оптимальную цепочку этих кодов и сгенерить самый короткий из возможных выходных запакованных файлов.

    Вопрос: как? =)

    Делаю пакер megalz на сях.
    --- Кто съел всю уху?

  2. #1
    С любовью к вам, Yandex.Direct
    Размещение рекламы на форуме способствует его дальнейшему развитию

  3. #2
    Member Аватар для valker
    Регистрация
    27.01.2005
    Адрес
    С.-Петербург
    Сообщений
    92
    Благодарностей: 6
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от lvd
    Ситуация: есть некий файл, его хочется запаковать LZ-методом.
    Файл гружу в память и для каждого байта строю набор всех подходящих к нему LZ-кодов (длина, смещение, размер кода в битах).

    Надо: выбрать оптимальную цепочку этих кодов и сгенерить самый короткий из возможных выходных запакованных файлов.

    Вопрос: как? =)

    Делаю пакер megalz на сях.
    Платформа какая?

    Возможно, поможет представление кода, как прохода по графу, а оптимальный в смысле длины кода, как путь по графу минимальной длины.

  4. #3
    Guru Аватар для caro
    Регистрация
    14.01.2005
    Адрес
    Ekaterinburg
    Сообщений
    2,481
    Благодарностей: 776
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от lvd
    Ситуация: есть некий файл, его хочется запаковать LZ-методом.
    Посмотри исходники, надеюсь поможет.

  5. #4

    По умолчанию

    Цитата Сообщение от valker
    Платформа какая?
    Какая разница - если на сях пишу... Не спек уж точно! =) Жрёт память по-чёрному, так что не дос тоже. :)

    Возможно, поможет представление кода, как прохода по графу, а оптимальный в смысле длины кода, как путь по графу минимальной длины.
    Ну да - и как этот путь минимальной длины искать? ;)
    --- Кто съел всю уху?

  6. #5

    По умолчанию

    Цитата Сообщение от caro
    Посмотри исходники, надеюсь поможет.
    Хм... там даже и намёка нет на оптимальный выбор цепочки... =)
    --- Кто съел всю уху?

  7. #6
    Guru Аватар для caro
    Регистрация
    14.01.2005
    Адрес
    Ekaterinburg
    Сообщений
    2,481
    Благодарностей: 776
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от lvd
    Хм... там даже и намёка нет на оптимальный выбор цепочки... =)
    Приведено три варианта, которые на одном и том же тестовом файле дают разные результаты паковки.
    Думаю готовый вариант решения задачи не стоит ждать

  8. #7

    По умолчанию

    Цитата Сообщение от caro
    Приведено три варианта, которые на одном и том же тестовом файле дают разные результаты паковки.
    Из которых один - с хаффманом после ЛЗ, а другой - с арифм. кодированием после ЛЗ. У меня только ЛЗ =)

    Думаю готовый вариант решения задачи не стоит ждать
    Да вот Хрумер дал один намёк в емыле - буду туда копать =)
    --- Кто съел всю уху?

  9. #8
    Moderator Аватар для elf/2
    Регистрация
    14.01.2005
    Адрес
    N.Novgorod
    Сообщений
    803
    Благодарностей: 117
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    вот тут есть n-ное количество статей на тему non-greedy/lazy parsing'а для LZ* алгоритмов:
    http://www-koi.compression.ru/download/lz.html

    они дают не оптимальный результат, но сжатие улучшают выбирая более правильные цепочки...

  10. #9
    Member Аватар для valker
    Регистрация
    27.01.2005
    Адрес
    С.-Петербург
    Сообщений
    92
    Благодарностей: 6
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от lvd
    Какая разница - если на сях пишу... Не спек уж точно! =) Жрёт память по-чёрному, так что не дос тоже.

    Ну да - и как этот путь минимальной длины искать?
    Если чистый С, то реализовать алгоритм Дейкстры (он подходит для неотрицательных весов).
    Если С++, то возьми BGL (Boost Graph Library), там этот алгоритм (и многие другие) уже реализован.

    Удачи!

  11. #10
    Member
    Регистрация
    17.01.2005
    Адрес
    Gorno-Altaysk
    Сообщений
    82
    Благодарностей: 18
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Valker: оптимальность кодирвания может быть как минимум 2 типов: опимальность в смысле размера упакованного файла, и оптимальность в смысле минимизации количества пар(длина смещение) и литералов. Какая у тебя имеется ввиду?

Страница 1 из 7 12345 ... ПоследняяПоследняя

Информация о теме

Пользователи, просматривающие эту тему

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •