Архиватор для текстовых файлов

Discussion in 'С/С++, C#, Rust, Swift, Go, Java, Perl, Ruby' started by raven1992, 30 Mar 2012.

  1. raven1992

    raven1992 New Member

    Joined:
    6 Oct 2011
    Messages:
    57
    Likes Received:
    3
    Reputations:
    0
    Друзья, поймал себя на том, что постоянно архивирую\разархивирую десятки(сотни) Тб тектовиков.
    Да и прямо сейчас если бы всё разархивировал - вышло бы Тб под 20 текста.

    Собственно, вопрос:
    никто не задавался всерьёз вопросом написания специализированного архиватора под текстовые файлы?:)
    Ведь 7% макс. компрессии у zip - мягко говоря странно, при чарсете то из 40 символов..) Да ещё и при том, что в осмысленном тексте 90% вдухисмвольных комбинаций, по-моему уложатся отнюдь не в 40^40, а в 40^10 комбинаций...
    Да и скорость zip архивации признаться оставляет желать лучшего. Мне кажется специализированный архиватор выдавал бы куда большую скорость, да и компрессию тоже.

    В общем решил вот написать себе. Помощь, вообще говоря, не требуется - просто стало интересно: неужели ещё никто не сделал хорошего архиватора для неупорчдоченных ограниченных чарсетов?

    Да и может кто из вас задавался подобным вопросом..?


    и второй пост.

    Я так понимаю всё-таки никто из нас и вас не писал того о чём я говорю.
    Потому предлагаю сделать этот тред - тредом текстового АРХИВАТОРА :-D

    Все кто вникал в сабж - могут писать тут свои мысли.

    Пока что я для планирую использовать алгоритм Хаффмана (точнее я долго размышлял над тем, как эфективно следует сжимать, но и сам пришёл к этому методу)
    При этом алгоритм будет 2-проходным, т.к. скорость чтения с современных HDD<<время сжатия, и не планирую использовать никакого арифметического кодирования, т.к. это уже и так прекрасно реализовано в zip\rar.


    ps. а возможно кто-то захочет писать текстовый архиватор (для текстов, содержащих слова) параллельно со мной?! О_о :)
     
    #1 raven1992, 30 Mar 2012
    Last edited by a moderator: 2 Apr 2012
  2. Kaimi

    Kaimi Well-Known Member

    Joined:
    23 Aug 2007
    Messages:
    1,761
    Likes Received:
    816
    Reputations:
    230
    Ну так используй 7zip или rar...
    Сомневаюсь, что результирующая поделка будет сжимать лучше.
     
    _________________________
  3. raven1992

    raven1992 New Member

    Joined:
    6 Oct 2011
    Messages:
    57
    Likes Received:
    3
    Reputations:
    0
    неспециализированные архиваторы создают свою таблицу для каждого блока из n* данных. Это позволяет добиться универсальности, но за это приходится платить.

    Адаптивность - палка о двух концах. А не-адаптивный архиватор... скорее повесится, прежде чем создаст таблицу для 10-20Гб файла, в то время, как сам я смог бы с лёгкостью задать(выбрать) ему точную таблицу "сходу". Ведь я-то знаю что содержится в файле и с какими статистическими вероятностями.

    Точнее... конечно же, "специализированному" архиватору тоже придётся создать несколько таблиц под различные часто-встречаемые текстовики. И на одно создание таких таблиц уйдут часы. Зато потом можно будет выбирать нужною таблицу самому и получать высокое качество сжатия при практически полном отсутствии нагрузки на проц=> высочайшую скорость
     
    #3 raven1992, 30 Mar 2012
    Last edited: 30 Mar 2012
  4. Kaimi

    Kaimi Well-Known Member

    Joined:
    23 Aug 2007
    Messages:
    1,761
    Likes Received:
    816
    Reputations:
    230
    И будет не универсально. Текст может быть в ANSI, UTF8, KOI-8R.... Язык может быть китайский, хрен знает какойский...

    Как будешь составлять таблицу на каждый случай? Или это будет поделка, которая в общем и целом нужна будет только тебе и только под твой типовой формат данных.

    Хочешь скорость? Распаковывай используя GPU
     
    _________________________
  5. raven1992

    raven1992 New Member

    Joined:
    6 Oct 2011
    Messages:
    57
    Likes Received:
    3
    Reputations:
    0
    В не-универсальности вся суть.
    Неужели у тебя самого текстовые данные на компе более, чем в 10 форматах?
    У меня например отсилы в четырёх, если не считать всяких там *doc *rtf которые к текстовым относить уже неправильно.

    Причем именно на эти 4-ре приходятся просто таки огромные количества недостаточно эффективно сжатого материала.
    Возможно у кого-то другого есть свои (другие) 5-6 форматов, но ведь редко больше.

    ps. а напрягает меня скорее скорость сжатия, чем скорость распаковки + угнетает эффективность, далёкая от "теоретически возможной" для алгоритма Хаффмана.
    Хотя какая именно степень сжатия должна быть в теории для [a-z,0-9] я в общем-то не считал. Но явно заметно отличающаяся от [A-Z,a-z,А-Я,а-я,0-9] ;) Да и вообще если во всем файле примерно постоянная статистическая вероятность символьных комбинаций - логично использовать всего одну таблицу соответствия для всего файла, будь он хоть 100-гиговый, вообще не тратя ресурсы на "анализ" упаковываемых данных, со всеми вытекающими
     
    #5 raven1992, 30 Mar 2012
    Last edited: 30 Mar 2012
  6. Kaimi

    Kaimi Well-Known Member

    Joined:
    23 Aug 2007
    Messages:
    1,761
    Likes Received:
    816
    Reputations:
    230
    В 4 и такие объемы? Да ты видимо кардер или коллекционер списков слов, либо филиал библиотеки планируешь открыть.
    Текстовых файлов содержащих чисто a-z0-9, да даже ещё каких-нибудь 3-4-5 "форматов", у меня наберется мегабайт на 50 максимум (из тех что я лично создавал).
     
    _________________________
  7. raven1992

    raven1992 New Member

    Joined:
    6 Oct 2011
    Messages:
    57
    Likes Received:
    3
    Reputations:
    0
    ммм. да. пожалуй проблема, вставшая передо мной и правда окажется близка не многим.
    Вообще она касается конкретно сжатия баз данных, чарсет которых заранее 100%но известен, так же как и статистические вероятности содержания комбинаций символов.

    И печально наблюдать, как серверный многоядерник грызёт эти базы, убивая гигафлопы на совершенно бесполезное высчитывание вероятностей для каждого жалкого 128мб блока данных, да ещё и забивает место в конечном файле ненужными таблицами соответствий

    ps
    с 20Тб я правда, пожалуй, подзагнул) Но всё же.
     
    #7 raven1992, 30 Mar 2012
    Last edited: 30 Mar 2012
  8. Spot

    Spot Elder - Старейшина

    Joined:
    1 Mar 2007
    Messages:
    462
    Likes Received:
    38
    Reputations:
    1
    Так ты бы определился, что для тебя важнее - процентуальное сжатие файла поотношению к исходному размеру файла или скорость сжатия/распаковки?

    Тут идет двустороняя зависимость: Чем больше ты хочешь "сжать" файл, тем дольше будет происходить данная операция. И наоборот - чем быстрее ты захочешь "паковать/распаковывать" файл, тем меньше ты сможешь его сжимать.

    Просто сравни уже имеющиеся архиваторы, вроде rar, zip,7-zip .....
    Вот тут парочка

    Что бы писать свой архиватор, да ещё и специализированный под текстовые документы - оее, тут надо хорошо прошерстить эту тему + матчасть.
     
  9. DYUMON

    DYUMON New Member

    Joined:
    15 Sep 2010
    Messages:
    68
    Likes Received:
    2
    Reputations:
    0
    winrar с ключем сжатия текста никак?
     
  10. raven1992

    raven1992 New Member

    Joined:
    6 Oct 2011
    Messages:
    57
    Likes Received:
    3
    Reputations:
    0
    эта тема - не от безысходности. На самом деле, если не работать постоянно с большей частью хранимой информации - не проблема и купить несколько 2тб винтов - стоят сейчас отсилы баксов по 60. Собсна у меня и так их несколько, и реальной проблемы с этим нет.
    Дело в другом. В искусстве.

    Ну а по сабжу:
    Сейчас думаю над тем, как генерировать таблицу, содержащую частично-пересекающиеся паттерны разной длинны.
    Т.е. например в упаковываемом файле 110к слов "email" и 100к слов "mail", при том что большая часть слов mail является фрагментами 110к слов email

    Проблемы с тем, чтобы расставить приоритетность паттернов в таблице с виду нет,
    умножаем (количество сэкономленных байт на фрагменте)*(количество таких фрагментов в файле).
    Но после того, как мы "заархивируем" первое слово из таблицы, заменив его чем-либо коротким - изменятся количества байт, которые сэкономят некоторые другие записи в таблице, частью которых была первая запись(или к-рые сами были её частью)

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

    Кроме прочего (если подходить к проблеме серьёзно) - существует и проблема определения стартового паттерна. Считать стартовым самый длинно-частый (тот, к-рый сам по себе экономит максимум байт) - конечно отдалённо правильно, но окажется далеко не всегда оптимальным.

    ps.
    Хотя пока писал это - пришла идея.
    Первым прогоном создать таблицу, выделить несколько комбинаций символов(допустим 4), и вторым прогоном создать сразу 4 таблицы - где каждый из них первый.
    А во время третьего прогона - не создавать новых паттернов, используя и выбирая из существующих в таблицах, например так, чтобы суммарный вес каждых 256 байт(может больше или меньше) оказывался наименьшим.

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

    ...

    в общем если я пишу непонятно - прошу меня извинить. Но если у кого есть идеи по тому, как более эффективно составлять таблицу соответствия (не жалея ОЗУ, процессорных мощностей и прогонов) - пишите как придумали вы.

    ps.
    rar макс.архивирование со текстовыми настройками и буфферами по максимуму и жмёт действительно на половину лучше и в 2 раза дольше дефолтного макс-зипа.
     
    #10 raven1992, 1 Apr 2012
    Last edited: 1 Apr 2012
  11. GoodGoogle

    GoodGoogle Moderator

    Joined:
    5 Aug 2011
    Messages:
    1,148
    Likes Received:
    332
    Reputations:
    225
    При максимальной компресии, можно сжать и до 1 ТБ.
    RAR, WINZIP(с его множественными форматами сжатия)

    Тести на 1 ГБ текстовиках, смотри где будет результативней.
     
    #11 GoodGoogle, 1 Apr 2012
    Last edited: 1 Apr 2012
    1 person likes this.
  12. Revolutionit

    Revolutionit New Member

    Joined:
    8 Feb 2012
    Messages:
    1
    Likes Received:
    0
    Reputations:
    0
    ppmd / LZP are very good at compressing text and give a good result.
     
  13. mr_walker

    mr_walker Member

    Joined:
    9 Aug 2009
    Messages:
    41
    Likes Received:
    34
    Reputations:
    2
    raven1992, Ты не из НАУ случайно?
     
Loading...