» FreeArc (часть 4)

Profrager
да, я знаю как работает LZ77. Вместо значений сжимаемой последовательности SREP вставляет ссылки на ранее обнаруженные такие-же последовательности. Я предлагаю уменьшить количество этих ссылок, тем самым уменьшиться размер файла на выходе. Ведь прочитав команду, как сказал выше Registered User:
Цитата:

"см. 1999 иголок 2000 иголок назад"

, выполнить ее быстрее, чем 1999 раз перечитывать данные вперед-назад по одной иголке. Я подумал раз уж SREP может находить байт-точные совпадения, то можно попробывать осуществить прямое сравнение группы байт. Начать сравнением по 2-байта и как пирамида поднимающаяся вверх дойти до группы из 8 байт.
Это всего лишь идея, поиск возможности улучшить SREP, который (не просто так) все хотят сделать частью FA. Не воспринимайте мою идею или то, как я пытаюсь объяснить ее вштыки. В споре рождается истина.

Цитата:

то можно попробывать осуществить прямое сравнение группы байт. Начать сравнением по 2-байта и как пирамида поднимающаяся вверх дойти до группы из 8 байт.

?

Registered User
Попробую объяснить:

Цитата:

8
4 4 4 . . .
2 2 2 2 2 2 . . .
1 1 1 1 1 1 1 1 11 11 . . .

Если, например, есть последовательность АBCDEFGH...ABCDKLMN (каждый символ по 1 байт), то сравниванием по 1-байт можно определить повторения (совпадения) для А, В, C, D:
(А)(B)(C)(D)EFGH...(A)(B)(C)(D)KLMN
Для первого прохода идет поиск совпадений с элементом, стоящим до и после текущего элемента. Т.е. можно определить повторяющиеся группы АВ и CD:
(АB)(CD)EFGH...(AB)(CD)KLMN
На следующем проходе определить, что после AB идут CD и записать их как одну группу из 4-байт:
(АBCD)EFGH...(ABCD)KLMN
На третьем проходе идет поиск групп по 8-байт (какбы идеальный вариант). Но, наверно, ресурсов будет использовать много.

Цитата:

vasulpr
ты нарисовал чего тебе не хватает, если другие считают также - добавлю

Это лишь пример. Просто не всегда помнишь все параметры, а лезть в справку и их искать не всегда удобно. Поэтому было бы удобно вынести ряд параметров в настройки сжатия. Я думаю такой абгрейд будет полезен для пользователей.

Bulat_Ziganshin
а что мешает в 7z Павлова добавить поддержку формата arc (просто открытие и распаковка, как rar)

хотя возможно
тогда только им и будут пользоваться чтобы просто отрыть и сжимать в такой формат не будут

ruduk
ну srep ведь прекомпрессор,и низкие значения искомых строк могут ухудшить последующее сжатие более мощным алгоритмом. В любом случае в srep есть минимальная длина искомых строк,меньше которой совпадения не будут обрабатываться, а если встретится блок бОльшего размера вплоть до размера буфера, схожий с каким-либо предыдущим большИм блоком, он будет обрабатываться как один единый блок,т.е. на него отведется всего 16байт (может и ошибаюсь с циферкой,пишу по памяти).
Т.е. ворачиваясь к ежикам, можно объяснить так, допустим имеются 2 ежика, у которых по 2000 иголок, но у второго 1992 иголок такие же как у первого, а 8-другие. Представим это в виде файлов. Имеем 2 файла с практически одинаковым содержимым размером по 2000мб, у второго 8 последних мегабайт отличаются от данных первого файла. Объединим файлы в один, чтобы среп их оба последовательно обработал. Допустим что в первом файле пересекающиеся данные не встречаются, т.е. среп в них не нашел схожие блоки, и т.к. размер буфера в среп 8 мб, то на выходе будем иметь 2000мб+ (2000/8)*16 байт на оглавление среп-файла (плюс еще пару десятков байт на блок, но суть не в этом). т.е. 2000мб+4000байт( ну мож 8кб если посчитать некоторые не указанные тут данные). При начале сканирования второго файла в потоке, среп увидит, что данные схожи с первым, при чем схожесть будет блоками размером с буфер (8мб), т.е. за записи 1992мб схожих с предыдущими понадобится (1992/8)*16 байт=3984байта (как и в предыдущем случае на самом деле будет чуть меньше 8кб) + оставшиеся 8 мб, для которых не найдены совпадения.
Т. е. я хочу сказать, что для записи больших повторов в срепе и так требуется относительно мало байт индексных данных.

Profrager
Моя идея свести количество индексных данных к минимуму, для более быстрой распаковки.
Возвращаясь к примеру с книгами, допустим Первая книга уже прочитана и "возвращена в библиотеку" (распакована). Начинаем читать Вторую книгу. На 1-й странице написано "Читай 1-ю страницу Первой книги", кладем книгу на стол, идем в библиотеку, читаем 1-ю страницу Первой книги, возвращаем книгу на полку, идем обратно к второй книге, читаем что написано на 2-й странице - "Читай 2-ю страницу Первой книги" -- кладем книгу на стол, идем в библиотеку . . . И так 1999 страниц.
Лучше один раз прийти в библиотеку и прочитать сразу 1999 страниц, т.е. минимизировать переходы туда-сюда. А сжать/распаковать последующим LZMA 1 ссылку на 1999 страниц будет быстрее/проще, чем сжимать 1999 отдельных ссылок на отдельные 1999 страниц, пускай даже они занимают по 16 байт.
Пускай размер файла уменьшится всего на пару килобайт, но возростет скорость распаковки записанного таким способом файла.

Цитата:

а что мешает в 7z Павлова добавить поддержку формата arc (просто открытие и распаковка, как rar)

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

а стратегически - да. поддержка fa через 7z.dll сделает элементарным его добавление в winrar, winzip и т.д. а в прогах типа haozip он просто автоматом появится. возможно, мне следует перенести приоритеты в эту сторону

ruduk

Цитата:

Моя идея свести количество индексных данных к минимуму, для более быстрой распаковки.

В твоем случае это просто надо размер буфера с 8 мб увеличить до допустим 512, или же реализовать "запоминание" самых мелких, далеких и часто используемых совпадений в пределах указанной оперативной памяти. Только тогда можно уменьшить обращения в жесткому диску. Хоть в общем то кеширование винды (семерки) в этом и так сильно помогает.

Добавлено:
И в реальных условиях редко очень бывает последовательно одинаковые данные больших размеров. Обычно крошится на много-много мелких кусков в разных частях файла. Это тоже самое что надо различные страницы в разных книгах искать по всей библиотеке, а на столе умещается только определенное количество книг. Все равно за другими бегать придется, всю библиотеку на стол не уместить.

При упаковке ФА в режиме "Без сжатия" файлы которые добавляются в архив упорядочиваются или добавляются в случайной последовательности???

во исполнение идеи vasulpr сделал пока следующее:



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

что туда ещё добавить? мои мысли:

- галочка "расшифровать метод сжатия", превращающая -m4 в -mrep.../$obj=..... - ну в общем ясно
- lc/-ld
- галочки для включения srep, precomp (с подгалочками для -t-j и slow) и dispack
- на этом мысль останавливается...

Добавлено:
соорудил к ним тултипы:

Цитата:

--- Disable filter/group
1509 rep=Finds repetitions on distances up to 1gb, improving compression ratio on multi-gigabyte datasets up to 10-30%
1510 exe=Improves compression of x86 executables up to 10%
1511 delta=Transforms binary data tables, improving compression ratio on executables up to 2-4%, on databases/mailbases - up to 10%
1512 dict=Replaces highly-repeatable words with short codes, improving compression ratio on texts
1513 lzp=Collapses repetitions, improving compression ratio on texts and especially logfiles
1514 $text=Advanced compression for plain text files
1515 $wav=Advanced compression for uncompressed audio wave files
1516 $bmp=Advanced compression for uncompressed bitmap graphic files
1517 $compressed=Quick-and-dirty compression for already compressed files, improving overall speed/compression ratio

Жду от вас предложений по улучшению этих тултипов

Profrager

Цитата:

И в реальных условиях редко очень бывает последовательно одинаковые данные больших размеров

режим по-умолчанию -m3 в SREP никто не отменял, он будет работать во всех случаях. Целью создания SREP было создание препроцессора для обработки больших файлов, и в Huge Files Compression Benchmark он показал себя с лучшей стороны. В некоторых случаях, отдельные файлы все-же будут максимально похожи друг на друга (например, текстура окна и текстура окна с маленькой форточкой внутри какого-нибудь *.gcf или *.pack игрового файла). Тогда на них можно будет дополнительно определить совпадения большей длинны.
ЗЫ. Не думал что будет такое бурное обсуждение, это же идея, ее можно проверить если попробовать реализовать

VasulNoz
читай документацию: этот раздел
Цитата:

... задайте опцию –dsgerpn (или какой порядок вам нужен) явно.

Bulat_Ziganshin
незнаю
GUI конечно круто
но лично я вообще просто вбиваю нужный тип цепочки методов в поле сжатие и все (когда CUI не пользуюсь)
если для каждой утилиты делать галочки, то может для утилит с большим разнообразием опций просто сделать поле ввода этих параметров

кстати а можно для CUI сделать в заголовке или где то еще чтобы также как в GUI скорость сжатия отображалась

ruduk

Цитата:

... задайте опцию –dsgerpn (или какой порядок вам нужен) явно

Что и где надо прописать в arc.ini чтобы это опция была по умолчанию, объясните подробно.

ruduk
Я все это и так знаю. Я тебе говорю, что совпадения длиной больше размера буфера очень редко встречаются. Я тебе алгоритм работы как раз режима -m3 парой постов раньше описал. Ты посмотри вовнутрь алгоритма и внутрь среднестатистического среп-файла, длины совпадений размером хотя бы в буфер я еще не встречал.
Ты говоришь теоретически, не представляя как все это есть сейчас и как это можно реализовать программно. Я тебе примеры возможной реализации уже описал.
Плюс ты не понимаешь, что 99% потери времени занимает доступ к мелким совпадениям, а не крупным (они и так будут читаться блоками по 8мб, и ускорения от убирания границ 8-ми мегабайтного буфера будут микросекунды на гигабайтном файле).

kalpak

Цитата:

можно для CUI сделать в заголовке или где то еще чтобы также как в GUI скорость сжатия отображалась

Не только в CLI, но и вообще, нет насущного смыла в отображении моментальной "скорости сжатия": для разных файлов , разных размеров будет разная скорость сжатия.
От наличия "отображения скорости" мало что изменится. А уж если просить, так просите ещё и отображение потребляемой памяти, процессорного времени, отображении дисковой активности как на память так и на запись.
Для этого есть "монитор ресурсов" и Process Explorer.

В прогресс-баре есть смысл (обратная связь (в частности с пользователем ) зачастую полезна), но его бессмысленно просить - он уже есть.

Profrager
мы с тобой говорим, как-будто я хочу испортить SREP. Это ведь только идея. Ты считаешь, что она плохая. Нужно узнать, что думает по этому поводу Булат.

VasulNoz
если через Arc.ini, то в раздел [Default options] в самом верху, или в строку упаковки.
если через GUI, то просто выбрать желаемую сортировку на закладке "Архив"

Bulat_Ziganshin

Тема уже не раз поднималась, но нормальной альтернативы унылому TTA для сжатия аудио в фа так и не нашлось. Оптимальным конечно бы был TAK, но его исходников до сих пор нету. Но есть еще 1 хороший алгоритм - OptimFrog - который на максимальных настройках жмёт аудио чуть сильнее ТАК'а, но медленнее. Поскольку это больше касается сжатия, тк разжатие происходит быстрее, то я осмелился бы попросить вшить OptimFrog в фа как некую альтернативу ТТА, у которого сжатие сильно отстаёт от этих алгоритмов.

З.Ы.
Заметил еще в новых репаках некий msc с которым хорошо жмётся аудио, но пока понятия не имею что это такое, тк оно идёт с CLS-фильтром который профрагер еще не выложил (и хз выложит ли).

1noObman1
Кроме унылого TTA есть неунылый FLAC, с фичей проигрывания произвольного места аудиофайла (streaming).
Те кто "качают" по полгига музыки в состоянии "покачать" на 10 секунд дольше
(разница между TTA и FLAC 650мб*((58,70%-57,10%)/100)=4 Мб)
Но зато после этого слушать с возможностью "промотки".

http://wiki.hydrogenaudio.org/index.php?title=Lossless_comparison#TTA_pros

OptimFROG (OFR)
OFR cons
Closed source
No multichannel audio support
No hardware support
Quite slow decoding

Цитата:

При упаковке ФА в режиме "Без сжатия" файлы которые добавляются в архив упорядочиваются или добавляются в случайной последовательности???

они идут в том порядке, в котором записаны в каталоге на диске. для ntfs это сортировка по каталогу и имени файла получается

и прочти наконец доку. раздел с описанием arc.ini там есть

Добавлено:
ruduk
на мой взгляд тут обсуждать даже нечего

но глядя на этот флейм я вроде допёр как улучшить сжатие связки (s)rep+lzma. если мы при запуске srep знаем с каким словарём будет lzma, то надо просто пропускать тело совпадений при дистанции меньше lzma:dict - поскольку точно известно что их и lzma cожмёт, причём куда эффективней

правда, при очень больших совпадениях эффект от уменьшения файла и соответственно дистанций для lzma всё же перевесит. т.е. получается что оптимальным может быть такой вариант:
при дистанции <64 мб и длине совпадения <4 кб - пропускаем эти данные на выход (не ища в них других совпадений!)
при дистанции <64 мб и длине совпадения >4 кб - кодируем
при дистанции >64 мб и длине совпадения >32 байт - кодируем


Добавлено:
правда копирование по 32 байта на больших дистанциях будет тем ещё цирком - даже если хватит памяти для сжатия...

Какой тип сортировки посоветуете? (GUI)

ndch

Ну меня интересует сжатие, а флак не настолько сильно жмёт как ТАК и OptimFrog. Да и насколько я знаю его тоже нету в фа. Интересует именно вшитый алгоритм, а не отдельные тулзы (с этим проблем и так нет).

Добавлено:

Цитата:

OptimFROG (OFR)
OFR cons
Closed source

На его странице есть сдк.

Bulat_Ziganshin

Цитата:

глядя на этот флейм я вроде допёр как улучшить сжатие связки (s)rep+lzma

ежики незря, значит, приснились . Правду говорю

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

1noObman1
TAK есть исходник на Pascal, по крайне мере исходник сжатия потока (takStream.pas)
идет вместе

Bulat_Ziganshin

Цитата:

правда копирование по 32 байта на больших дистанциях будет тем ещё цирком - даже если хватит памяти для сжатия...

32 еще куда ни шло) а вот 16 или 8 длина поиска - это да) на 4 гб файле у меня часа 2 винт будет мучить)

P.S. на сколько увеличивается скорость обработки подобного большого файла с маленьким размером строки поиска, если hdd сменить на ssd? Стоит ли оно того? Помню ты писал чего-то про ssd, но уже не помню какая разница была.


Цитата:

если мы при запуске srep знаем с каким словарём будет lzma, то надо просто пропускать тело совпадений при дистанции меньше lzma:dict - поскольку точно известно что их и lzma cожмёт, причём куда эффективней

гуд идея, но по-моему ты уже где-то писал пободное)

Цитата:

получается что оптимальным может быть такой вариант:
...

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

Цитата:

TAK есть исходник на Pascal, по крайне мере исходник сжатия потока (takStream.pas)
идет вместе

Уже радует, но не факт что булат станет переписывать его с паскаля...

1noObman1
Ещё раз: разница в сжатии максимум 4 Мб.
Или для Вас максимальное сжатие самоцель ?

Добавлено:
kalpak

Цитата:

когда подбираешь оптимальный алгоритм сжатия то сразу видишь его скорость

Тогда уж график просите с указанием сжимаемых файлов, чего мелочится то ?

подобное есть в моём lzp, но не то. там просто по типу "строки от 32 байт с большой дистанцией, от 512 с маленькой". а вот в таколм виде мне почему-то казалось сложно сделать. и вообще это надо для начала в rep, там проблем с мелкими совпадениями не будет

что касается hdd->ssd, то чтение маленьких блоков данных быстрее примерно на два порядка. но ради одного srep я не вижу смысла на ssd переходить - ибо у тебя-то упакуется быстро, а вот потом как распаковывать? достаточно иметь озу на 2-4 гига больше чем у своих пользователей

Добавлено:
вообще в srep есть что улучшить. я например знаю как увеличить скорость сжатия в несколько раз, но кому и зачем это нужно?

реальные проблемы srep - как избавиться от временных файлов при распаковке и нагрузки на кеш (или как-то ограничить её сверху)

например, у меня была такая идея - если сделать srep первым алгоритмом в цепочке сжатия, то при распаковке он будет последним. тогда получится что временный файл при распаковке не нужен - можно данные копировать напрямую из ранее распакованных файлов. проблем две - первое, тогда из архива нельзя распаковать только часть файлов (или можно, записывая данные пропускаемых файлов всё же во временный файл). второе - цепочка srep+precomp+lzma жмёт хуже, нежели precomp+srep+lzma

ещё была идея - сделать LZ наоборот. сейчас precomp, как и положено LZ, записывает откуда из истории надо скопировать данные на текущее место. тут же наоборот - при декодировании данных сразу будут определяться места в выходном файле куда их надо записать. эта идея должна была разрешить проблемы с нагрузкой на кеш диска при распаковке, но тут тоже потенциальные проблемы - во-первых, архиватор при распаковке обычно считает crc распаковываемых файлов для проверки целостности, здесь это придётся делать отдельным проходом. во-вторых, при кусках данных в 512 байт запись такого куска в выходной файл, я боюсь, может потребовать сначала чтения целого кластера (4кб, а на ssd и все 128 кб)

1. вшивать другие алгоритмы для звука в fa я не буду потому что и он не резиновый, и моё время тоже. желающие могут использовать внешние exe, писать cls-фильтры и т.п.
2. исходников tta нет, выложенное - лишь интерфейс к его библиотеке распаковки


Цитата:

(сейчас ориентируюсь на показатель оставшегося времени)

ты может не в курсе, но freearc.exe поддерживает комстроку точно так же как arc.exe. попробуй:

freearc.exe a a


Цитата:

кстати а можно для CUI сделать в заголовке или где то еще чтобы также как в GUI скорость сжатия отображалась

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

Bulat_Ziganshin

Цитата:

что касается hdd->ssd, то чтение маленьких блоков данных быстрее примерно на два порядка. но ради одного srep я не вижу смысла на ssd переходить - ибо у тебя-то упакуется быстро, а вот потом как распаковывать? достаточно иметь озу на 2-4 гига больше чем у своих пользователей

загрузка винды/основных прог + своп-файл + srep = ssd Оперативки 8 гб. Винда кеширует 4гига где-то) Все равно мало)

По теме топика.
Возможно ли реализовать фильтр в ФА с динамически меняющимся размером блока? Т.е. на входе надо детектить необходимый заголовок и соответственно подстраивать текущий блоксайз. А то с постоянной его величиной геморно как-то создать задуманное)
З.Ы. мож это все и расписано в исходниках, но я тока мельком реп смотрел, так что сильно не бить!