BWT - ArchonX2

kvark

Ищу признания своему детищу: АрхонуX2. Эта прога реализует мой алгоритм БВТ, содержащий много новаторских идей, требующих описания.

Я перепробовал множество методов

(разве только кроме суффиксных деревьев), генерил и там интересные техники, но вершина сего творения именно АрхонХ2. Начало развитию алгоритму дал метод Itoh-Tanaka, описанный Deorovich'ем в его диссертации. Дальше я много работал над ним, добился _значительного_ улучшения результатов (часть которых, впрочем, была достигнута до меня, но я об этом не знал). После этого я разработал некоторые техники, которые можно применять совместно с другими алгоритмами БВТ и соединил всё это в Архоне.

После уже более чем 2-хлетнего развития представляю вниманию Archon-2.5. Это версия, специально разработанная для тестирования (блок всегда 4Мб).:
http://kvark.at.tut.by/ArchonT.exe

Также желающим попробовать его на БОЛЬШИХ блоках предоставляю "необрезанную" версию с возможностью задавания размера блока:
http://kvark.at.tut.by/ArchonX2.exe

Предыдущие версии участвовали в неофициальном тестировании Вадима Юкина и показали там себя весьма внушительно (претендовали на лидерство). С нетерпением жду последних результатов с набором файлов по-больше, чем в стандартном наборе Вадима. Буду рад любым результатом тестов от каждого.

Поведение:
- Память: 5N, где N - размер блока :twisted:
- Ассимптотика: ~N*N*logN, но к счастью она совершенно не отражает реальной ситуации. Скорость практически не меняется от размера блока - проверьте сами. :wink:

- Устойчивость: высокая, но если _очень_ постараться, то можно найти 85-метровый файл, на котором Архон с 32хметровым блоком будет работать больше 10-минут :shock:

Гость

Я попробовал воспользоваться программой.
Взял файл pop.txt:
pop.txt│17652492

Моя программка сделала bwt от всего файла (фактически, один блок размером 17652492) за 2 минуты 50 секунд. (Кстати, если я правильно посчитал, ее скорость N*logN, причем она СОВСЕМ не зависит от средней длины повторений)

Програма Архон с параметром "-b24" (16 мегабайт)
уже 30 минут работает. (И конца-края не видно)
Высылаю "скрин-шот"

ArchonX2.exe -b24 pop.txt pop.arc

Archon X2 (C)kvark, 2005
Progress:
An error 2 accured!
Call format:
archonx2 [e|d] [-bLog] <source> <dest>
Default block size = '-b22' = 4Mb
D:\david\Kharabadze\Compression\archonx2>ArchonX2.exe e -b24 pop.txt pop.arc

Archon X2 (C)kvark, 2005
Progress: D

В принципе, могу выложить "проблемный" файл.

Гость

У меня уже 50 минут работает...
В общем, выкладываю начало файла pop.txt:

У попа была собака,
Он её любил.
Она съела кусок мяса,
Поп её убил.

Вырыл яму, закопал
И на камне написал:

У попа была собака,
Он её любил.
Она съела кусок мяса,
Поп её убил.

Вырыл яму, закопал
И на камне написал:

У попа была собака,
Он её любил.
Она съела кусок мяса,
Поп её убил.

Вырыл яму, закопал
И на камне написал:

(И так далее на 16 мегабайт

)

Гость

Уже час... Наверное, программа зависла...
Так что, устойчивости к избыточным данным нет...
(Если я правильно понимаю "устойчивость")

VadimV

И правда, прикольный файл. Очень многие сортировщики на нем виснут. Неплохо справился с ним MSufSort, впятеро медленнее - StrongBWT Ильи Гребнова. Кстати, libdivsufsort, в котором используются примерно те же идеи, что и в Архоне, тоже выступил неплохо - всего вдвое медленнее MSufSort.

Вот табличка замеров (без учета данного файла).

Код:

                        book1  book2  aaa    xls    exe
GR fast                 0.88   -      -      0.61   0.77     
GR combined             0.88   5.72   0.82   0.61   0.82     
GR strong               1.42   3.84   0.65   0.99   0.71     
bsm10                   0.93   -      0.22   2.31   0.55     
dc                 6n   0.99   -      -      0.71   0.65     
deep shallow            1.04  16.97   0.38   0.71   0.60     
cache0                  1.15   3.95   0.33   0.60   0.43     
copy0                   0.88   -      0.27   2.58   0.44     
archonX2                0.95   2.25   0.45   0.72   0.61
archon 2.5              0.85   2.03   0.42   0.66   0.60
bs                      1.26   3.24   -      0.82   0.81    
bssc 0.95               1.38   6.32   6.87   1.26   0.93
abcsort (18.01.05)      1.26   -      0.44   -      -
ranksort (0.1.1)        1.31   3.96   0.49   0.55   0.77
iabcsort                2.47   5.87   0.88   1.04   1.32
abcdsort (0.1.0, -O2)   1.70   4.01   0.55   0.55   0.77
m03test                 1.53   9.67   0.38   0.66   0.77
itssort  (-O2)          0.93   -      0.22   4.67   0.49
MSufSort  2.1           1.48   4.72   0.71   1.27   0.99
cachesort          6n   1.48   6.85   0.66   0.87   0.76     
ybs                8n   1.54   6.26   0.60   0.83   0.88     
copysort                1.64   -      0.60  21.04   0.99     
it99                    1.65   -      -      -      1.10     
kao                     1.75   -      0.77  14.06   0.98    
difference cover        2.14   6.42   7.91   0.82   0.88   
modified ls             3.13   8.46   5.82   1.59   1.81    
larsson sadakane        3.68  27.25   4.66   3.02   1.92    
kluykov forward   14n   4.83   5.00   0.33   2.74   2.63    
ko/aluru          16n   6.92  14.67   1.59   2.80   4.39    
karkkanen/sanders 16n  10.05  22.02   4.06   4.67   7.19

book2 - book1 concatenated to book1,
aaa - 1 million symbols 'a',
xls, exe - files from my test fileset CCT.
Block size is equal to file size.
Somewhere a used memory is showed :)
Minus means I cannot wait for sorting completion :)

VadimV

Сорри, из таблички выпал последний divsufsort:

Код:

divsufsort 1.26 7.42 0.22 0.55 0.61

Результаты в таблице не отсортированы. Но на мой взгляд, Архон показал более, чем впечатляющие результаты, я бы даже сказал, лучшие. С попом и его собакой, уверен, Дима в ближайшее время справится

kvark

Я не очень удивлён таким исходом дела с зависанием. У меня есть потрясная новость: готов Archon 2.7 alfa. Не релиз, потому, что можно кое-что ещё доделать, но работает на ура :twisted: . Требования к памяти по-прежнему 5N, что необходимо отметить в таблице.

htpp://kvark.at.tut.by/Archon2_7.exe
Плюс то же, но с 16-имеговым блоком (требует 80метров ОЗУ):
htpp://kvark.at.tut.by/Archon2_7_16M.exe

Изменения. В Archon 2.5 была защита версии 1.0. В Archon 2.7 её версия уже 2.3

. И это не пустые цифры. На разработку метода защиты, его реализацию и отладку ушло 30 :!:

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

Исходный код в объёме увеличился в 1.5 раза. Алгоритм усложнился настолько, что завтра я уже забуду как работает его большая часть. :shock:

Хотя это усложнение не мешает основной чати работать как и раньше. Защита в основном касается многократных повторений данных, на чём можно подловить большинство конкурентов. На сегодняшний день я не могу найти данные, на которых Archon 2.7 бы показал хоть какую-то слабость.

Уверен на 95%, что с попом и его собакой всё теперь ОК. Кажется, новый Архон как-раз вовремя. Интересно узнать его результаты и на старых тестах (как в таблице), так как общая скорость тоже должна немного подняться.

kvark

Скорей бы новый тестовый корпус составить. Для Вадима файлы, которые выбрал я: http://kvark.at.tut.by/Kvark.zip
В них bighard.bin есть собственно камень для конкурентов. Бинарная естесственная структура (в отличие от Попа с собакой), множество повторов. Надеюсь, понравится :wink:

Напомню, что предыдущие версии Архона (скажем, 2.3) намного быстрее справлялись с маленькими бинарниками:

Код:

archon 2.3a 0.99 2.47 0.26 0.54 0.45

Замедление проявляется исключительно на маленьких файлах и файлах с чрезвычайно простой структурой (как aaa), поэтому я и хочу провести "более крупный разбор полётов" :twisted:. Хотя в ближайшее время я всё же попытаюсь совместить лучшие черты старых версий в Архоне 2.7. В моём наборе все файлы имеют естесственное происхождение, что для меня важно. Как это отражает реальную ситуацию - отдельная тема, но в целом такой тест несомненно полезен :wink:

Пожелания к Вадиму насчёт результатов:
1) Конечно, новый тестовый корпус.
2) Для всех написать требования к памяти.
3) Добавить столбец - компилятор (тоже важно)
4) Отсортировать по book1
5) И добавить Архон 2.7

)

kvark

Теперь сортировка "Попа ..." заняла около минуты. В принципе, и так неплохо, можно даже кое-что подправить, чтобы время было около 20 сек, но это не наш метод. Напрашивается версия защиты 2.4 и 2.5. Буду работать дальше:) видимо 30 часов - ещё не предел%)

Гость, а что у тебя за сортировщик? Представь его на всеобщее обозрение: интересно посмотреть как бегает твоя "тёмная лошадка" на тестах :wink:

Kharabadze D.E.

kvark писал(а):

Гость, а что у тебя за сортировщик? Представь его на всеобщее обозрение: интересно посмотреть как бегает твоя "тёмная лошадка" на тестах :wink:

Я же написал: скорость сортировщика не зависит от средней длины повторений. Поэтому скорость работы будет около 3-х минут почти на любом 16-Мб файле.
(на P4-2.400)
(Что очень медленно.)
Кроме того, он откажется сортировать файл, состоящий из одинаковых символов (это не баг, это фича

- предполагалось, что в этом случае файл будет кодироваться числом повторений).

Скорость работы: N*log(N)
Алгоритм: суффиксно-поразрядная сортировка
Требования к памяти: 17*N (N- размер файла)
Размер блока: равен размеру файла
Объем исходного кода: 5239 байт
Написание алгоритма заняло 1 выходной день.

Так что, не волнуйтесь, ничего особенного в программе нет.
(За исключением того, что у него нет зависимости от средней длины повторений. Хотя в книге Д.Ватолина и др. писали, что скорость суффиксной сортировки растет как log(N), по моим оценкам она никак не связана с длиной повторений.)

RSK

Ну раз пошла такая пьянка, то вот вам и мои версии USORT на тесты:
http://rsdn.ru/File/42491/usorts.rar
Версия 2.33 (удачная замена ранней версии "kluykov forward";) - используется ускоренное добавление в PATRICIA trie, 14N, Intel C++ 6, размер блока неограничен.
Версия 3.00 - строит суффиксное дерево на основе PATRICIA trie, 18N, MSVC 7.1, размер блока неограничен.
Обе версии очень хорошо отрабатывают "попа с собакой", 3.00 также быстро сортирует bighard.bin. Но есть файлы, на которых обе программы могут задуматься и надолго... :(

RSK

RSK писал(а):

Но есть файлы, на которых обе программы могут задуматься и надолго...

Обновил архив до версии 3.10. Теперь это действительно O(N)-сортировка. По крайней мере, я затрудняюсь подобрать файл, на котором бы эта программа затормозила.

Kharabadze D.E.

Kharabadze D.E. писал(а):

kvark писал(а):

Гость, а что у тебя за сортировщик? Представь его на всеобщее обозрение: интересно посмотреть как бегает твоя "тёмная лошадка" на тестах :wink:

Благодаря сайту newmail выложил сортировщик:
http://141120.nm.ru/bwt.rar
Будет приятно, если потестируете.
(И неприятно, если он упадет на каком - либо файле.)

kvark

>Ну раз пошла такая пьянка...
Третьим будешь? Я рад, что тема алгоритмов сортировки всё-таки интересна и важна людям!

Хорошо ещё, что Вадим пока не выложил новые результаты (возможно, после моих предложений они будут не скоро), так как тепер Архон 2.7 уже не альфа, а здоровый законченный вариант( не путать Archon 2.7-alfa и Archon 2.7a ). Уровень защиты поднялся до версии 2.4. Защита нового уровня (2.5 или 3.0) ещё не готова и ждёт своего часа (скорей бы:))
http://kvark.at.tut.by/Archon2_7a.exe

Было замечено, что версия 2.7 в целом намного быстрее справляется с набором Вадима, жду результатов с нетерпением!
Есть один казус... Я тут у себя тестил Archon2_3a и обнаружил, что он нигде(!) не оказался шустрее Archon2_5. А версия Archon2_7 вообще уходит вперёд

По замерам Вадима на файлах aaa, xls, exe старая версия справилась несравнимо лучше...

Чем это объяснить?
Версия1-софт: во время старых замеров у Вадима была другая (более лёгкая) програмная загруженность. В этом случае надо все рузультаты проверить на одной програмной конфигурации компа (насколько я вижу, это проблемно).
Версия2-железо: по каким-то неведомым мне причинам железо Вадима реагирует на мой код совсем иначе, чем моё. Хотя я компилю под 486х (только вспомнил, на этом тоже можно выйграть:))

З.Ы. Поп с собакой уже не проблема:)

Цитата:

Объем исходного кода: 5239 байт
Написание алгоритма заняло 1 выходной день.
Так что, не волнуйтесь, ничего особенного в программе нет.

Исходный код Архона 2.5 - 5.3кб, время написания - пять лет

kvark

Прошу прощения за полубитую ссылку. Сервис tut.by подводит. Вместо той вылаживаю новый Archon 2.8. В нём реализована недоделанная защита версии 2.5. Недоделанная, потому что в голову стукнула гениальная идея по приведению исходной идеи защиты к совершенному и законченному виду. Так что сейчас идёт активная разработка (а точнее уже отладка) революционного Архона 3.0 с защитой версии соответственно 3.0. Это будет логическое завершение Архона, что приведёт к выпуску ArchonX3 или к полной остановке работы над Архоном.

http://kvark.at.tut.by/Archon2_8.exe


	Форум сервера "Все о сжатии" >> Сайт о сжатии >> Новинки \| О сервере \| Статистика Книга "Методы сжатия" >> Без потерь \| Изображений \| Видео >> Cтатьи+исходники \| Видео \| Arctest \| Ссылки \| Ru.compress

BWT - ArchonX2

Кто сейчас на конференции