Друзья, поймал себя на том, что постоянно архивирую\разархивирую десятки(сотни) Тб тектовиков. Да и прямо сейчас если бы всё разархивировал - вышло бы Тб под 20 текста. Собственно, вопрос: никто не задавался всерьёз вопросом написания специализированного архиватора под текстовые файлы? Ведь 7% макс. компрессии у zip - мягко говоря странно, при чарсете то из 40 символов..) Да ещё и при том, что в осмысленном тексте 90% вдухисмвольных комбинаций, по-моему уложатся отнюдь не в 40^40, а в 40^10 комбинаций... Да и скорость zip архивации признаться оставляет желать лучшего. Мне кажется специализированный архиватор выдавал бы куда большую скорость, да и компрессию тоже. В общем решил вот написать себе. Помощь, вообще говоря, не требуется - просто стало интересно: неужели ещё никто не сделал хорошего архиватора для неупорчдоченных ограниченных чарсетов? Да и может кто из вас задавался подобным вопросом..? и второй пост. Я так понимаю всё-таки никто из нас и вас не писал того о чём я говорю. Потому предлагаю сделать этот тред - тредом текстового АРХИВАТОРА :-D Все кто вникал в сабж - могут писать тут свои мысли. Пока что я для планирую использовать алгоритм Хаффмана (точнее я долго размышлял над тем, как эфективно следует сжимать, но и сам пришёл к этому методу) При этом алгоритм будет 2-проходным, т.к. скорость чтения с современных HDD<<время сжатия, и не планирую использовать никакого арифметического кодирования, т.к. это уже и так прекрасно реализовано в zip\rar. ps. а возможно кто-то захочет писать текстовый архиватор (для текстов, содержащих слова) параллельно со мной?! О_о
неспециализированные архиваторы создают свою таблицу для каждого блока из n* данных. Это позволяет добиться универсальности, но за это приходится платить. Адаптивность - палка о двух концах. А не-адаптивный архиватор... скорее повесится, прежде чем создаст таблицу для 10-20Гб файла, в то время, как сам я смог бы с лёгкостью задать(выбрать) ему точную таблицу "сходу". Ведь я-то знаю что содержится в файле и с какими статистическими вероятностями. Точнее... конечно же, "специализированному" архиватору тоже придётся создать несколько таблиц под различные часто-встречаемые текстовики. И на одно создание таких таблиц уйдут часы. Зато потом можно будет выбирать нужною таблицу самому и получать высокое качество сжатия при практически полном отсутствии нагрузки на проц=> высочайшую скорость
И будет не универсально. Текст может быть в ANSI, UTF8, KOI-8R.... Язык может быть китайский, хрен знает какойский... Как будешь составлять таблицу на каждый случай? Или это будет поделка, которая в общем и целом нужна будет только тебе и только под твой типовой формат данных. Хочешь скорость? Распаковывай используя GPU
В не-универсальности вся суть. Неужели у тебя самого текстовые данные на компе более, чем в 10 форматах? У меня например отсилы в четырёх, если не считать всяких там *doc *rtf которые к текстовым относить уже неправильно. Причем именно на эти 4-ре приходятся просто таки огромные количества недостаточно эффективно сжатого материала. Возможно у кого-то другого есть свои (другие) 5-6 форматов, но ведь редко больше. ps. а напрягает меня скорее скорость сжатия, чем скорость распаковки + угнетает эффективность, далёкая от "теоретически возможной" для алгоритма Хаффмана. Хотя какая именно степень сжатия должна быть в теории для [a-z,0-9] я в общем-то не считал. Но явно заметно отличающаяся от [A-Z,a-z,А-Я,а-я,0-9] Да и вообще если во всем файле примерно постоянная статистическая вероятность символьных комбинаций - логично использовать всего одну таблицу соответствия для всего файла, будь он хоть 100-гиговый, вообще не тратя ресурсы на "анализ" упаковываемых данных, со всеми вытекающими
В 4 и такие объемы? Да ты видимо кардер или коллекционер списков слов, либо филиал библиотеки планируешь открыть. Текстовых файлов содержащих чисто a-z0-9, да даже ещё каких-нибудь 3-4-5 "форматов", у меня наберется мегабайт на 50 максимум (из тех что я лично создавал).
ммм. да. пожалуй проблема, вставшая передо мной и правда окажется близка не многим. Вообще она касается конкретно сжатия баз данных, чарсет которых заранее 100%но известен, так же как и статистические вероятности содержания комбинаций символов. И печально наблюдать, как серверный многоядерник грызёт эти базы, убивая гигафлопы на совершенно бесполезное высчитывание вероятностей для каждого жалкого 128мб блока данных, да ещё и забивает место в конечном файле ненужными таблицами соответствий ps с 20Тб я правда, пожалуй, подзагнул) Но всё же.
Так ты бы определился, что для тебя важнее - процентуальное сжатие файла поотношению к исходному размеру файла или скорость сжатия/распаковки? Тут идет двустороняя зависимость: Чем больше ты хочешь "сжать" файл, тем дольше будет происходить данная операция. И наоборот - чем быстрее ты захочешь "паковать/распаковывать" файл, тем меньше ты сможешь его сжимать. Просто сравни уже имеющиеся архиваторы, вроде rar, zip,7-zip ..... Вот тут парочка Что бы писать свой архиватор, да ещё и специализированный под текстовые документы - оее, тут надо хорошо прошерстить эту тему + матчасть.
эта тема - не от безысходности. На самом деле, если не работать постоянно с большей частью хранимой информации - не проблема и купить несколько 2тб винтов - стоят сейчас отсилы баксов по 60. Собсна у меня и так их несколько, и реальной проблемы с этим нет. Дело в другом. В искусстве. Ну а по сабжу: Сейчас думаю над тем, как генерировать таблицу, содержащую частично-пересекающиеся паттерны разной длинны. Т.е. например в упаковываемом файле 110к слов "email" и 100к слов "mail", при том что большая часть слов mail является фрагментами 110к слов email Проблемы с тем, чтобы расставить приоритетность паттернов в таблице с виду нет, умножаем (количество сэкономленных байт на фрагменте)*(количество таких фрагментов в файле). Но после того, как мы "заархивируем" первое слово из таблицы, заменив его чем-либо коротким - изменятся количества байт, которые сэкономят некоторые другие записи в таблице, частью которых была первая запись(или к-рые сами были её частью) Т.е. для каждой (хотя бы из верхних) записей в таблице в идеале нужно делать новый прогон файла. В принципе реально.. конечно. Но я думаю над какой-нибудь логической уловкой для того чтобы сделать этот процесс менее топорным Кроме прочего (если подходить к проблеме серьёзно) - существует и проблема определения стартового паттерна. Считать стартовым самый длинно-частый (тот, к-рый сам по себе экономит максимум байт) - конечно отдалённо правильно, но окажется далеко не всегда оптимальным. ps. Хотя пока писал это - пришла идея. Первым прогоном создать таблицу, выделить несколько комбинаций символов(допустим 4), и вторым прогоном создать сразу 4 таблицы - где каждый из них первый. А во время третьего прогона - не создавать новых паттернов, используя и выбирая из существующих в таблицах, например так, чтобы суммарный вес каждых 256 байт(может больше или меньше) оказывался наименьшим. В результате должно получиться несколько таблиц, которые хотя бы не потребуют дальнейшей обработки. ... в общем если я пишу непонятно - прошу меня извинить. Но если у кого есть идеи по тому, как более эффективно составлять таблицу соответствия (не жалея ОЗУ, процессорных мощностей и прогонов) - пишите как придумали вы. ps. rar макс.архивирование со текстовыми настройками и буфферами по максимуму и жмёт действительно на половину лучше и в 2 раза дольше дефолтного макс-зипа.
При максимальной компресии, можно сжать и до 1 ТБ. RAR, WINZIP(с его множественными форматами сжатия) Тести на 1 ГБ текстовиках, смотри где будет результативней.
