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

    Если у кого то есть идеи милости прошу...
      Пару идей, но не более.
      1)Можно выбирать алгоритм в зависимости от типа файла:
      BMP - сжимать чем-то типа RLE (RunLength Encoding),
      Gif, Jpg - вообще не сжимать,
      текстовые - LZH и т.д.
      2)Все файлы склеить в один, к которому и применить какой-нибудь метод сжатия (получится аналог Solid-архивов, т.е. используется один словарь на все файлы)

      PS: Все равно Rar не переплюнуть huh.gif
        QUOTE (tserega @ 6.11.03, 18:07)
        PS: Все равно Rar не переплюнуть huh.gif

        Дело в том, что распаковка архива должна производиться динамически, например подрузка текстур или звуковых файлов в процессе игры..
        и Что касается rar'a то здесь действительно имеем большую плотность записи, но не очень больщую скорость распаковки..
          QUOTE
          Все равно Rar не переплюнуть

          Поетому он такой и тормозной. smile.gif Требования-то противоречивые smile.gif
          Сообщение отредактировано: Visitor -
            Дело в том, что если разбирать стурктуру файла по типу данных, то придется создавать что то типа дополнительного списка (заголовка архива), в котором будут прописаны методы сжатия для каждого файла, смещение на файл в архиве и дополнительные сведения, что породит дополнительный поиск и затраты времени..
              QUOTE (GrAnd @ 6.11.03, 13:24)
              Дело в том, что если разбирать стурктуру файла по типу данных, то придется создавать что то типа дополнительного списка (заголовка архива), в котором будут прописаны методы сжатия для каждого файла, смещение на файл в архиве и дополнительные сведения, что породит дополнительный поиск и затраты времени..

              Я примерно это и имел в виду. А затраты по скорости поиска из-за этих таблиц будут ничтожны (скажем так, O(const) )
                Появилась небольшая идейка..

                Для увеличения плотности архивации само архивирование производим по-блочно...

                Так как размеры файлов различны, да и содержимое в разных местах файла так же отлично, то при определеннной разбивке файла на части(блоки), архивируем каждый блок по отдельности различными самым отпимальным методом для данного блока (RLEB, RLEW, LZB, LZW или Хафманом). Метод выбираем в процессе архивации..
                Единственное размер блоков должен быть одинаковым, хотя и сам их размер можем тоже подобрать в процессе архивации..
                Таким образом получим наибольшую плотность архивирования.
                  QUOTE (tserega @ 6.11.03, 18:31)
                  А затраты по скорости поиска из-за этих таблиц будут ничтожны (скажем так, O(const) )

                  Как знать..
                  Если необходимо из примерно 2000-2500 файлов найти нужный, то придется сначала отсортировывать расположение файлов в архиве..
                    Зачем?
                    Будем хранить в начале файла таблицу, в которой будет показано, гду расположен каждый файл!
                      Архивирование поблочно: все ето делает код Лемпела-Зива (он структуре своей содержит ету адаптивность). Можно его доработать (что, подозреваю, и сделано во всяких рарах и т.п.), чтобы он адаптивно переключался между режимами сжатия (размерами скользящего окна) и передачи входного потока без изменений.

                      А выходной поток, сжатый по LZ, обрабатывать уже хаффманом или арифметическим кодированием, т.к, повторов строк в нем где-то в 8 раз меньше, а повторы символов есть... Получили продвинутый PKZIP. smile.gif
                      ---
                      Тут другой вопрос: а файлы ети последовательно читать надо или должен быть прямой доступ к каждому?
                      ---
                      Пора и мне в Werewolfы... smile.gif
                      Сообщение отредактировано: Visitor -
                        QUOTE (tserega @ 6.11.03, 19:04)
                        Зачем?
                        Будем хранить в начале файла таблицу, в которой будет показано, гду расположен каждый файл!

                        Имел ввиду отсортированность самой таблицы.. Это действительно убыстрит доступ к файлу по имени...
                        Сообщение отредактировано: GrAnd -
                          2Visitor:
                          доступ идет абсолютно к произвольному файлу в данный момент времени..
                            Я имелл ввиду, к произвольному байту произвольного файла, или к произвольному файлу просто?
                              к файлу...
                                Тогда склеивать файлы в 1 ни в коем случае нельзя... Все хорошие алгоритмы сжатия просто не оставяют достаточно избыточной информации, чтобы начать читать сжатый поток "с середины". Восстановить состояние автомата-кодера можно, только прочитав весь предшествующий сжатый поток...
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


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