На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (2) 1 [2]  все  ( Перейти к последнему сообщению )  
> Увеличение степени сжатия и скорости чтения
    А вот начальное состояние автомата (для алгоритма Лемпела-Зива -- начальное заполнение окна, для динамического Хаффмана -- начальное древо...) можно подобрать оптимальным для всего набора файлов, которые будут сжиматься. Или пару-тройку таких начальных состояний smile.gif
      QUOTE (Visitor @ 6.11.03, 19:49)
      Восстановить состояние автомата-кодера можно, только прочитав весь предшествующий сжатый поток...

      В этом то и суть блочного архивирования. Каждый блок архивируется своим отпимальным для него методом.
      В начале архива имеем структуру блоков где указанано:
      номер блока и текущее смещение-указатель на этот блок в архиве
      так же имеем "таблицу" файлов находящихся в архиве, где указывается: имя файла, смещение на блоки файла в архиве, и соответсвенно размер..
        Так уже ж есть блоки -- сами файлы. Зачем еще усложнять? smile.gif Или имеется ввиду оптимальное, с точки зрения применения разных алгоритмов сжатия разбиения файла на блоки?

        Ето таки может сработать, в самом деле...

        Но что-то мне подсказывает, что ето будет (как минимум) полиномиально высокой степени сложно сделать. А то и НП-полно вообще smile.gif
          Щас как раз и занялся этим..
          завтра выложу результаты smile.gif, если все будет Ok
            QUOTE (Visitor @ 6.11.03, 20:16)
            Так уже ж есть блоки -- сами файлы. Зачем еще усложнять? smile.gif Или имеется ввиду оптимальное, с точки зрения применения разных алгоритмов сжатия разбиения файла на блоки?

            Именно.. получается, что один файл разбит на блоки, каждый из которых имеет отпимальный метод сжатия..
            Конечно при архивации придется перебирать мнрожество методов для каждого блока и это займет много времени. Но зато в итоге получим "идеальный" архив smile.gif А по скорости разархивирования тоже не должен уступать..
              Распаковку быстрее, чем LZSS (вообще методов семейства LZ77) ты сделаешь вряд ли. LZB чуть получше, поэтому советую именно его.
              Интервальное кодирование (более скоростная модификация арифметического), как и Хаффман, как и контекстное моделирование, для разнородных данных, ИМХО, не лучший метод, да и по скорости явно медленнее. LZW (в общем, любые LZ78) - метод тормозной.
              А по поводу блочного кодирования... ты знаешь, не думаю, что у тебя будет большой выигрыш, т.к. при чередовании методов будет теряться информация о предыдущих байтах (или её нужно собирать заново - опять же время), соответственно и сжатие хуже. Подумай: создал ты адаптивную PPM-модель, закодировал 16kb, а потом переходишь к LZB... здесь, в общем-то можно использовать предыдущие байты как окно, но когда ты перейдёшь обратно в PPM, придётся строить модель заново (хотя, можно и использовать старую, но ещё не факт, что так лучше).
              Не буду тебя отговаривать, но ИМХО, это только лишний гемор.
              Я б использовал LZB или ZIP вообще (чтоб не мучаться) smile.gif
              RAR, кстати, тоже LZSS использует, только там куча фильтров, поэтому и тормозит.
              Сообщение отредактировано: 7in -
                Не, тут постановка такая: создать архиватор, причем не контекстно-адаптивный, как LZSS, или статистический, как LZW или хаффмана, а идеальный, использующий как знание о структуре всего кодируемого потока, так и каждой отдельно взятой его части smile.gif

                И потом посмотреть, что из етого получится. (И заодно разрешить некоторые теологические споры, касающиеся того, сколько "посторонней" информации вносят существующие архиваторы в сжатый поток smile.gif)
                  Итак..
                  Получился почти "идеальный" архиватор с элементами собственно распаковки данных.. rolleyes.gif
                  Упаковка идет раз 10 медленней чем всякие RARы и ZIPы, но зато распаковка куда быстрее, правда пока не намоного примерно на 5-10%, но над этим работы продолжаются.. cool.gif
                    А как на счёт степени сжатия? smile.gif
                    И какой метод использован? smile.gif
                    p.s. Ты это всё вручную пишешь? smile.gif
                      Объясняю технологию...
                      Имеем кучу файлов, которые необходимо заархивировать.
                      В процессе архивации читаем файл по блокам (например по 16 кБ, можно выбрать любой). Архивируем его (блок)по-очереди несколькими способами (LZb(W), RLEB(W), Huffman или вообще не архирируем). Сравниваем какой метод для этого блока наиболее эффективен и пишем его в архив. Правда на это уходит до фига времени cool.gif

                      При разархивации знаем каким методом блок заархивирован и распаковываем его..

                      Про процентное содержание я уже писал biggrin.gif
                      Коэфф. сжатия лучше даже чем у RARа tongue.gif
                      Сообщение отредактировано: GrAnd -
                      1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
                      0 пользователей:


                      Рейтинг@Mail.ru
                      [ Script execution time: 0.0805 ]   [ 14 queries used ]   [ Generated: 22.11.26, 12:37 GMT ]