форум группы Chief-Net :: Версия для печати :: Оптимальное сжатие в запаковщике

1. Ace Lightning - 20 Февраля, 2016 - 10:47:53 - перейти к сообщению

Всем привет.

Возник вот такой вот вопрос, касающийся некоторых алгоритмов сжатия. Задача ромхакера, в случае запакованных данных в игре, сводится к тому, чтобы
1) определить расположение пожатых данных в роме;
2) разобраться в алгоритме распаковки;
3) написать распаковщик;
4) написать упаковщик, который максимально эффективно сожмет данные.

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

2. Марат - 20 Февраля, 2016 - 11:51:01 - перейти к сообщению

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

3. Ace Lightning - 20 Февраля, 2016 - 12:03:38 - перейти к сообщению

Ну вот, чтобы не лезть во всякие LZ, есть такой простой пример. Есть текст, в котором некоторыми байтами, например с $30 до $FF указывается номер записи в словаре. Как оптимизировать запаковку текста по такой схеме? Ясно, что последовательность равную одному байту запаковывать нет смысла. Тогда уже будем искать только повторяющиеся последовательности размером больше одного байта. Можно отсортировать по количеству совпадений последовательности в тексте и запаковать все самые часто встречающиеся, пока не будет привешена длина словаря. Но! Например в конце будет очень длинная последовательность, которая встречается в тексте очень малое количество раз и алгоритм до нее просто не дойдет, но логически понятно, что загнать ее в словарь будет самое то.

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

4. Марат - 20 Февраля, 2016 - 19:11:02 - перейти к сообщению

Ты говоришь об MTE. В этом случае нужно делать двухпроходной алгоритм. На первом шаге алгоритм ищет наиболее часто встречающиеся последовательности(строку символов). А на втором замещает строку номером этой строки из словаря. Ну, с MTE я почти не работал. По MTE у нас alex_231 спец. Может, он что подскажет.

5. Mefistotel - 22 Февраля, 2016 - 03:28:10 - перейти к сообщению

Марат пишет:

Ты говоришь об MTE. В этом случае нужно делать двухпроходной алгоритм. На первом шаге алгоритм ищет наиболее часто встречающиеся последовательности(строку символов). А на втором замещает строку номером этой строки из словаря. Ну, с MTE я почти не работал. По MTE у нас alex_231 спец. Может, он что подскажет.

MTE/DTE применяется же только для текста (DTE кодирует одним байтом 2 буквы, MTE одним байтом (может и двумя в зависимости от размера словаря) более 2 букв). И есть программы, позволяющие отследить количество повторяющихся слогов/слов и составить оптимальный словарь.
Но MTE/DTE не считается сжатием в привычном нам понимании. Это скорее оптимизация хранения текста с целью экономии места.
Я использую программу во вложении для составления MTE словаря. Она была платная, поэтому архив под паролем (123).
P. S. Бывает так в играх на старых платформах, что места под текст нет и перенести в другой банк весьма проблематично. Можно прикрутить MTE/DTE, чтобы русский текст уместился (нечто подобное делает Алекс для Sylvan Tale) или Хаффман (Джинни внедрила алгоритм для русского перевода Saint Seiya - Ougon Densetsu Kan ketsu Hen (J).nes ).

6. Ace Lightning - 29 Февраля, 2016 - 12:52:31 - перейти к сообщению

Mefistotel
Спасибо за программу Улыбка

7. Mefistotel - 02 Марта, 2016 - 13:34:35 - перейти к сообщению

Та програмка для целых слов, то есть MTE словаря.
А есть ещё для слогов, то есть DTE словаря. Вложил. Улыбка

8. Ace Lightning - 02 Марта, 2016 - 14:30:11 - перейти к сообщению

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

Давайте запакуем последовательность 72 72 72 72 72 72 72 72 72 108 108 111 72 101 108 91.

1) В начале словарь пуст.
S: 72 72 72 72 72 72 72 72 72 108 108 111 72 101 108 91
D: -

2) Находим последовательность большую или равную 2 байтам, которая имеет наибольшее количество вхождений. Эта последовательность: 72 72.
[72 72] [72 72] [72 72] [72 72] 72 108 108 111 72 101 108 91

3) Теперь в словаре появляется одна запись
S: 00 00 00 00 72 108 108 111 72 101 108 91
D: 72 72 254

Как видим, что если у нас изначально было 16 байт, то стало 15 (включая словарь). Если запаковать еще последовательность 00 00, которая встречается два раза, то запакованная последовательность вместе со словарем будет занимать 16 байт, собственно, как и в самом начале, поэтому это будет неэффективно.

А сам алгоритм запаковки прост:
1) Проходимся по всему тексту и ищем последовательность, повторяющуюся наибольшее количество раз.
2) Помещаем ее в словарь.
3) Запаковываем.
4) Переходим к пункту 1.
И все это до тех пор, пока не займется все свободное место, отведенное под словарь и под текст, или пока не закончатся подходящие последовательности для запаковки.

Я может быть рассуждаю о вещах, которые некоторым покажутся простыми, но возможно кому-то это поможет.

Так что вот, буду отлаживать запаковщик.

9. Mefistotel - 02 Марта, 2016 - 14:42:25 - перейти к сообщению

Такие последовательности отлично сжимаются методом RLE (Run Length Encoding) без всяких словарей и прочего.
Ты же читал эту тему?
Архивы и алгоритмы сжатия
Вложил также исходники для RLE Konami кодера.

10. Марат - 02 Марта, 2016 - 15:00:03 - перейти к сообщению

Ace Lightning пишет:

А сам алгоритм запаковки прост:
1) Проходимся по всему тексту и ищем самую длинную последовательность.
2) Помещаем ее в словарь.
3) Запаковываем.
4) Переходим к пункту 1.

Не согласен.
Если просто отбирать самые длинные слова и помещать их в словарь, то он быстро переполнится. Слово может занимать 15 байт, но встречаться всего лишь один раз, в то время как другие более короткие слова могут быть длиной меньше, например, 5 байт, но встречаться раз 20 в тексте. Поэтому нужно длину слова умножать на количество вхождений и тогда ты узнаешь истинный вес этого слова. В общем, нюансов много и их надо учитывать.

11. Ace Lightning - 02 Марта, 2016 - 15:42:44 - перейти к сообщению

Марат пишет:

Ace Lightning пишет:

А сам алгоритм запаковки прост:
1) Проходимся по всему тексту и ищем самую длинную последовательность.
2) Помещаем ее в словарь.
3) Запаковываем.
4) Переходим к пункту 1.

Не согласен.
Если просто отбирать самые длинные слова и помещать их в словарь, то он быстро переполнится. Слово может занимать 15 байт, но встречаться всего лишь один раз, в то время как другие более короткие слова могут быть длиной меньше, например, 5 байт, но встречаться раз 20 в тексте. Поэтому нужно длину слова умножать на количество вхождений и тогда ты узнаешь истинный вес этого слова. В общем, нюансов много и их надо учитывать.

ой, ошибся, конечно, не самую длинную последовательность, а ту, которая встречается в тексте больше всего раз. Прошу прощения.

Марат пишет:

Поэтому нужно длину слова умножать на количество вхождений и тогда ты узнаешь истинный вес этого слова.

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

12. Ace Lightning - 02 Марта, 2016 - 15:43:48 - перейти к сообщению

Mefistotel пишет:

Такие последовательности отлично сжимаются методом RLE (Run Length Encoding) без всяких словарей и прочего.
Ты же читал эту тему?
Архивы и алгоритмы сжатия
Вложил также исходники для RLE Konami кодера.

Никто же не спорит Улыбка

Но в игре используется словарная система, вот под нее и пишу запаковщик.

13. Mefistotel - 02 Марта, 2016 - 17:17:57 - перейти к сообщению

Что хоть за игра)))?

14. Ace Lightning - 03 Марта, 2016 - 07:25:01 - перейти к сообщению

Mefistotel пишет:

Что хоть за игра)))?

The Flintstones. The Rescue of Dino and Hoppy.

15. Mefistotel - 03 Марта, 2016 - 07:51:38 - перейти к сообщению

На форуме есть тема по этой игре.
В случае чего вопросы можно задавать там.

16. Guyver - 03 Марта, 2016 - 12:02:17 - перейти к сообщению

Ага, как же, есть Ха-ха

Перекинул тему со старого форума: http://chief-net.ru/forum/topic....m=4&topic=65

17. Mefistotel - 03 Марта, 2016 - 12:21:49 - перейти к сообщению

Голова уже кругом идёт от переноса: Улыбка

18. Guyver - 03 Марта, 2016 - 12:33:19 - перейти к сообщению

Я бы помог - на у меня трафик - 300 мб на месяц. Да вот... Осталось 12 Мб - и всё...

19. Марат - 03 Марта, 2016 - 12:37:46 - перейти к сообщению

Касательно кодировки Флинстоунов можно прочитать здесь https://en.wikipedia.org/wiki/Byte_pair_encoding .

20. Ace Lightning - 03 Марта, 2016 - 12:42:47 - перейти к сообщению

Guyver пишет:

Ага, как же, есть Ха-ха

Перекинул тему со старого форума: http://chief-net.ru/forum/topic....m=4&topic=65

Только игра не на GameBoy, а на NES, а в заголовке написано GB.

21. Guyver - 03 Марта, 2016 - 12:47:17 - перейти к сообщению

Заголовок полностью скопирован с оригинала... Какой был - такой и остался. Не?

http://chiefnet.1bb.ru/viewtopic.php?id=593

22. Ace Lightning - 03 Марта, 2016 - 12:52:21 - перейти к сообщению

Guyver пишет:

Заголовок полностью скопирован с оригинала... Какой был - такой и остался. Не?

http://chiefnet.1bb.ru/viewtopic.php?id=593

Да нет, я не с претензиями. Я просто прошу поправить, так как игра и правда на NES, а не на GB. Наверное я ошибся, когда создавал тему.

Марат пишет:

Касательно кодировки Флинстоунов можно прочитать здесь https://en.wikipedia.org/wiki/Byte_pair_encoding .

Спасибо за статью Улыбка

23. Марат - 14 Июня, 2016 - 22:20:10 - перейти к сообщению

Начал работать над генератором словаря mte.
На данный момент генератор из текста игры Tiny Toon 2 выдаёт следующий список слов:

Спойлер (Отобразить)

CODE:

Total space = 80 Space economy = 59 Total count = 16 String = _THE_ String length = 5
Total space = 72 Space economy = 54 Total count = 6 String = THIS_IS_THE_ String length = 12
Total space = 70 Space economy = 53 Total count = 10 String = _TICKET String length = 7
Total space = 108 Space economy = 52 Total count = 54 String = _T String length = 2
Total space = 81 Space economy = 51 Total count = 27 String = _TH String length = 3
Total space = 90 Space economy = 43 Total count = 45 String = E_ String length = 2
Total space = 55 Space economy = 39 Total count = 11 String = ICKET String length = 5
Total space = 56 Space economy = 38 Total count = 4 String = SECRET_ADMIRER String length = 14
Total space = 57 Space economy = 35 Total count = 19 String = IS_ String length = 3
Total space = 54 Space economy = 33 Total count = 18 String = YOU String length = 3
Total space = 45 Space economy = 31 Total count = 5 String = _TICKETS. String length = 9
Total space = 42 Space economy = 29 Total count = 6 String = THIS_IS String length = 7
Total space = 44 Space economy = 29 Total count = 4 String = SECRET_ADMI String length = 11
Total space = 60 Space economy = 28 Total count = 30 String = OU String length = 2
Total space = 40 Space economy = 27 Total count = 8 String = TRAIN String length = 5
Total space = 56 Space economy = 26 Total count = 28 String = ER String length = 2
Total space = 40 Space economy = 26 Total count = 10 String = YOU_ String length = 4
Total space = 54 Space economy = 25 Total count = 27 String = IN String length = 2
Total space = 54 Space economy = 25 Total count = 27 String = IS String length = 2
Total space = 35 Space economy = 23 Total count = 7 String = THIS_ String length = 5
Total space = 35 Space economy = 23 Total count = 5 String = FUN_HOU String length = 7
Total space = 36 Space economy = 23 Total count = 4 String = SECRET_AD String length = 9
Total space = 36 Space economy = 23 Total count = 4 String = FUN_HOUSE String length = 9
Total space = 36 Space economy = 21 Total count = 12 String = ICK String length = 3
Total space = 32 Space economy = 20 Total count = 4 String = _TICKETS String length = 8
Total space = 32 Space economy = 20 Total count = 4 String = SECRET_A String length = 8
Total space = 30 Space economy = 19 Total count = 6 String = _YOU_ String length = 5
Total space = 30 Space economy = 19 Total count = 5 String = _THIS_ String length = 6
Total space = 30 Space economy = 19 Total count = 5 String = _HAVE_ String length = 6
Total space = 42 Space economy = 19 Total count = 21 String = EN String length = 2
Total space = 30 Space economy = 17 Total count = 10 String = _TO String length = 3
Total space = 36 Space economy = 16 Total count = 18 String = ET String length = 2
Total space = 27 Space economy = 15 Total count = 9 String = ENT String length = 3
Total space = 25 Space economy = 15 Total count = 5 String = FUN_H String length = 5
Total space = 34 Space economy = 15 Total count = 17 String = CK String length = 2
Total space = 32 Space economy = 14 Total count = 16 String = TH String length = 2
Total space = 24 Space economy = 14 Total count = 6 String = _THE String length = 4
Total space = 24 Space economy = 14 Total count = 6 String = STER String length = 4
Total space = 24 Space economy = 14 Total count = 4 String = SECRET String length = 6
Total space = 24 Space economy = 13 Total count = 8 String = TRA String length = 3
Total space = 30 Space economy = 13 Total count = 15 String = RA String length = 2
Total space = 30 Space economy = 13 Total count = 15 String = _A String length = 2
Total space = 24 Space economy = 13 Total count = 8 String = ER_ String length = 3
Total space = 26 Space economy = 11 Total count = 13 String = ST String length = 2
Total space = 21 Space economy = 11 Total count = 7 String = IDE String length = 3
Total space = 26 Space economy = 11 Total count = 13 String = _H String length = 2
Total space = 20 Space economy = 11 Total count = 5 String = E_TO String length = 4
Total space = 20 Space economy = 11 Total count = 5 String = YOUR String length = 4
Total space = 26 Space economy = 11 Total count = 13 String = _B String length = 2
Total space = 20 Space economy = 11 Total count = 5 String = _HAV String length = 4
Total space = 26 Space economy = 11 Total count = 13 String = ON String length = 2
Total space = 20 Space economy = 11 Total count = 4 String = MPER_ String length = 5
Total space = 24 Space economy = 10 Total count = 12 String = OR String length = 2
Total space = 24 Space economy = 10 Total count = 12 String = SE String length = 2
Total space = 18 Space economy = 9 Total count = 6 String = _BU String length = 3
Total space = 18 Space economy = 9 Total count = 6 String = ING String length = 3
Total space = 18 Space economy = 9 Total count = 6 String = _HA String length = 3
Total space = 22 Space economy = 9 Total count = 11 String = AR String length = 2
Total space = 16 Space economy = 8 Total count = 4 String = _IS_ String length = 4
Total space = 16 Space economy = 8 Total count = 4 String = SECR String length = 4
Total space = 20 Space economy = 8 Total count = 10 String = S. String length = 2
Total space = 18 Space economy = 7 Total count = 9 String = H_ String length = 2
Total space = 15 Space economy = 7 Total count = 5 String = RER String length = 3
Total space = 15 Space economy = 7 Total count = 5 String = FUN String length = 3
Total space = 18 Space economy = 7 Total count = 9 String = LL String length = 2
Total space = 18 Space economy = 7 Total count = 9 String = ED String length = 2
Total space = 18 Space economy = 7 Total count = 9 String = ID String length = 2
Total space = 18 Space economy = 7 Total count = 9 String = EA String length = 2
Total space = 16 Space economy = 6 Total count = 8 String = FU String length = 2
Total space = 14 Space economy = 5 Total count = 7 String = AN String length = 2
Total space = 14 Space economy = 5 Total count = 7 String = CO String length = 2
Total space = 12 Space economy = 5 Total count = 4 String = COM String length = 3
Total space = 12 Space economy = 5 Total count = 4 String = SE_ String length = 3
Total space = 12 Space economy = 5 Total count = 4 String = _OF String length = 3
Total space = 12 Space economy = 5 Total count = 4 String = FOR String length = 3
Total space = 14 Space economy = 5 Total count = 7 String = OF String length = 2
Total space = 14 Space economy = 5 Total count = 7 String = __ String length = 2
Total space = 12 Space economy = 5 Total count = 4 String = COA String length = 3
Total space = 14 Space economy = 5 Total count = 7 String = ES String length = 2
Total space = 12 Space economy = 5 Total count = 4 String = CAR String length = 3
Total space = 12 Space economy = 5 Total count = 4 String = EED String length = 3
Total space = 12 Space economy = 4 Total count = 6 String = MI String length = 2
Total space = 12 Space economy = 4 Total count = 6 String = _R String length = 2
Total space = 12 Space economy = 4 Total count = 6 String = IG String length = 2
Total space = 12 Space economy = 4 Total count = 6 String = MA String length = 2
Total space = 12 Space economy = 4 Total count = 6 String = IT String length = 2
Total space = 12 Space economy = 4 Total count = 6 String = _T_T. String length = 2
Total space = 10 Space economy = 3 Total count = 5 String = CR String length = 2
Total space = 10 Space economy = 3 Total count = 5 String = HA String length = 2
Total space = 8 Space economy = 2 Total count = 4 String = _P String length = 2
Total space = 8 Space economy = 2 Total count = 4 String = TO String length = 2
Total space = 8 Space economy = 2 Total count = 4 String = WA String length = 2
Total space = 8 Space economy = 2 Total count = 4 String = MP String length = 2

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

24. Mefistotel - 15 Июня, 2016 - 07:17:47 - перейти к сообщению

Всегда не хватало нормального генератора с настройками. Улыбка

25. Mefistotel - 15 Декабря, 2016 - 02:22:11 - перейти к сообщению

Марат пишет:

Начал работать над генератором словаря mte.
На данный момент генератор из текста игры Tiny Toon 2 выдаёт следующий список слов:

Марат, что там с твоим генератором? Для сайта такая программка бы не помешала.
Нашёл в инете онлайн-калькулятор слов:
http://webscript.ru/cgi-bin/text/text.cgi
В принципе, для нужд перевода вполне устраивает.

26. Марат - 15 Декабря, 2016 - 19:40:00 - перейти к сообщению

Она ещё не доработана. Я её собирался переносить на дельфи в GUI. Но так и не брался за нее.

27. Марат - 20 Января, 2019 - 15:42:25 - перейти к сообщению

Mefistotel пишет:

Марат, что там с твоим генератором? Для сайта такая программка бы не помешала.

Решил снова начать работу над генератором. Уже есть кое-какие успехи.
Тестировал на перводе Тини Туна. В результате съэкономлено 105 байт.

CODE:

ДОБРО ПОЖАЛОВАТЬ - частота = 3; Экономия места - 29
БИЛЕ - частота = 10; Экономия места - 26
- частота = 26; Экономия места - 24
Е - частота = 25; Экономия места - 23
«ДВОРЕЦ СМЕХА - частота = 3; Экономия места - 23
ТО - частота = 24; Экономия места - 22
ТАЙНЫЙ ФАНАТ - частота = 3; Экономия места - 21
НА - частота = 18; Экономия места - 16
И - частота = 17; Экономия места - 15
РО - частота = 17; Экономия места - 15
ВО - частота = 16; Экономия места - 14
РА - частота = 15; Экономия места - 13
ПО - частота = 13; Экономия места - 11
ЭТО - частота = 7; Экономия места - 11
ГО - частота = 12; Экономия места - 10
СТ - частота = 12; Экономия места - 10
ВА - частота = 11; Экономия места - 9
МО - частота = 11; Экономия места - 9
НО - частота = 11; Экономия места - 9
НЫ - частота = 11; Экономия места - 9
О - частота = 10; Экономия места - 8
С - частота = 10; Экономия места - 8
РЕ - частота = 10; Экономия места - 8
ЭТО БИЛЕТНАЯ КАСС - частота = 2; Экономия места - 8
П - частота = 9; Экономия места - 7
БАСТЕР - частота = 3; Экономия места - 7
КИ - частота = 8; Экономия места - 6
М - частота = 8; Экономия места - 6
ТА - частота = 8; Экономия места - 6
ТЬ - частота = 8; Экономия места - 6
РЕЧНЫЕ ПОРОГИ - частота = 2; Экономия места - 6
ЛОВУШЕК. - частота = 2; Экономия места - 6
РУССКИЕ ГОРКИ - частота = 2; Экономия места - 7
ВОЗВРАЩАЙТЕСЬ - частота = 2; Экономия места - 9
4 ЗОЛОТЫХ - частота = 2; Экономия места - 7
В - частота = 7; Экономия места - 5
ЕН - частота = 7; Экономия места - 5
НЕ - частота = 7; Экономия места - 5
СЯ - частота = 7; Экономия места - 5
Т - частота = 7; Экономия места - 5
БИЛЕТОВ - частота = 4; Экономия места - 5
АРК - частота = 4; Экономия места - 5
ХОД - частота = 4; Экономия места - 5
АВТОД - частота = 3; Экономия места - 5
МОЖЕТ - частота = 3; Экономия места - 5
ПАРОВОЗИК - частота = 2; Экономия места - 5
БО - частота = 6; Экономия места - 4
ЗА - частота = 6; Экономия места - 4

28. Griever - 20 Января, 2019 - 21:45:36 - перейти к сообщению

Не забудь сравнить результат с каноничной MTE Search Tool .

29. Марат - 20 Января, 2019 - 22:52:36 - перейти к сообщению

Ещё немного подшаманил. Улучшил сжатие. Теперь уже 164 байт съэкономлено.

Спойлер (Отобразить)

30. Марат - 20 Января, 2019 - 23:27:53 - перейти к сообщению

Griever пишет:

Не забудь сравнить результат с каноничной MTE Search Tool .

Завтра надо будет сверить.