форум группы Chief-Net форум группы Chief-Net
Перевод приставочных игр и не только!
drako site Перейти на сайт группы     Наш чат      Помощь      Поиск      Пользователи


 Страниц (2): [1] 2 »   

> Без описания
Ace Lightning Пользователь
Отправлено: 20 Февраля, 2016 - 10:47:53
Post Id



VIP


Покинул форум
Сообщений всего: 480
Дата рег-ции: Июнь 2015  





Всем привет.

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

На 4 этапе возникает проблема, решение которой мне кажется достаточной далеким и туманным. Эта проблема возникала у меня каждый раз, когда я подходил к 4 пункту. Собственно, это проблема единственная, которая мешает мне выпустить два практически готовых перевода. Может быть есть тот, кто понимает о чем я говорю и решил эту проблему.
 
 Top
Марат Супермодератор
Отправлено: 20 Февраля, 2016 - 11:51:01
Post Id



Chief-Net


Покинул форум
Сообщений всего: 2183
Дата рег-ции: Окт. 2014  
Откуда: Казахстан





Обычно, если пакер сжимает данные на уровне оригинального, то этого достаточно. Превзойти коэффициент сжатия оригинала, обычно, редко получается.
 
 Top
Ace Lightning Пользователь
Отправлено: 20 Февраля, 2016 - 12:03:38
Post Id



VIP


Покинул форум
Сообщений всего: 480
Дата рег-ции: Июнь 2015  





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

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

(Отредактировано автором: 20 Февраля, 2016 - 12:18:23)

 
 Top
Марат Супермодератор
Отправлено: 20 Февраля, 2016 - 19:11:02
Post Id



Chief-Net


Покинул форум
Сообщений всего: 2183
Дата рег-ции: Окт. 2014  
Откуда: Казахстан





Ты говоришь об MTE. В этом случае нужно делать двухпроходной алгоритм. На первом шаге алгоритм ищет наиболее часто встречающиеся последовательности(строку символов). А на втором замещает строку номером этой строки из словаря. Ну, с MTE я почти не работал. По MTE у нас alex_231 спец. Может, он что подскажет.
 
 Top
Mefistotel Администратор
Отправлено: 22 Февраля, 2016 - 03:28:10
Post Id



Chief-Net


Покинул форум
Сообщений всего: 7127
Дата рег-ции: Окт. 2014  
Откуда: МАГАДАН





Марат пишет:
Ты говоришь об 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 ).
Скачать файл: program.7z
Скачан раз: 304


-----
"Перевод старых игр - отличная возможность понять, как устроены программы, подучить иностранный язык и поднять уровень владения родным. Ну и конечно, это просто возможность "общения" со своей любимой игрой детства." © Dimouse
 
 Top
Ace Lightning Пользователь
Отправлено: 29 Февраля, 2016 - 12:52:31
Post Id



VIP


Покинул форум
Сообщений всего: 480
Дата рег-ции: Июнь 2015  





Mefistotel
Спасибо за программу Улыбка
 
 Top
Mefistotel Администратор
Отправлено: 02 Марта, 2016 - 13:34:35
Post Id



Chief-Net


Покинул форум
Сообщений всего: 7127
Дата рег-ции: Окт. 2014  
Откуда: МАГАДАН





Та програмка для целых слов, то есть MTE словаря.
А есть ещё для слогов, то есть DTE словаря. Вложил. Улыбка
Скачать файл: Martial.7z
Скачан раз: 291


-----
"Перевод старых игр - отличная возможность понять, как устроены программы, подучить иностранный язык и поднять уровень владения родным. Ну и конечно, это просто возможность "общения" со своей любимой игрой детства." © Dimouse
 
 Top
Ace Lightning Пользователь
Отправлено: 02 Марта, 2016 - 14:30:11
Post Id



VIP


Покинул форум
Сообщений всего: 480
Дата рег-ции: Июнь 2015  





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

Давайте запакуем последовательность 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.
И все это до тех пор, пока не займется все свободное место, отведенное под словарь и под текст, или пока не закончатся подходящие последовательности для запаковки.

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

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

(Отредактировано автором: 02 Марта, 2016 - 15:45:20)

 
 Top
Mefistotel Администратор
Отправлено: 02 Марта, 2016 - 14:42:25
Post Id



Chief-Net


Покинул форум
Сообщений всего: 7127
Дата рег-ции: Окт. 2014  
Откуда: МАГАДАН





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

Скачать файл: konaenc.7z
Скачан раз: 280


-----
"Перевод старых игр - отличная возможность понять, как устроены программы, подучить иностранный язык и поднять уровень владения родным. Ну и конечно, это просто возможность "общения" со своей любимой игрой детства." © Dimouse
 
 Top
Марат Супермодератор
Отправлено: 02 Марта, 2016 - 15:00:03
Post Id



Chief-Net


Покинул форум
Сообщений всего: 2183
Дата рег-ции: Окт. 2014  
Откуда: Казахстан





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

Не согласен.
Если просто отбирать самые длинные слова и помещать их в словарь, то он быстро переполнится. Слово может занимать 15 байт, но встречаться всего лишь один раз, в то время как другие более короткие слова могут быть длиной меньше, например, 5 байт, но встречаться раз 20 в тексте. Поэтому нужно длину слова умножать на количество вхождений и тогда ты узнаешь истинный вес этого слова. В общем, нюансов много и их надо учитывать.
 
 Top
Ace Lightning Пользователь
Отправлено: 02 Марта, 2016 - 15:42:44
Post Id



VIP


Покинул форум
Сообщений всего: 480
Дата рег-ции: Июнь 2015  





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

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

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

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

(Отредактировано автором: 02 Марта, 2016 - 15:52:42)

 
 Top
Ace Lightning Пользователь
Отправлено: 02 Марта, 2016 - 15:43:48
Post Id



VIP


Покинул форум
Сообщений всего: 480
Дата рег-ции: Июнь 2015  





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

Никто же не спорит Улыбка
Но в игре используется словарная система, вот под нее и пишу запаковщик.
 
 Top
Mefistotel Администратор
Отправлено: 02 Марта, 2016 - 17:17:57
Post Id



Chief-Net


Покинул форум
Сообщений всего: 7127
Дата рег-ции: Окт. 2014  
Откуда: МАГАДАН





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

-----
"Перевод старых игр - отличная возможность понять, как устроены программы, подучить иностранный язык и поднять уровень владения родным. Ну и конечно, это просто возможность "общения" со своей любимой игрой детства." © Dimouse
 
 Top
Ace Lightning Пользователь
Отправлено: 03 Марта, 2016 - 07:25:01
Post Id



VIP


Покинул форум
Сообщений всего: 480
Дата рег-ции: Июнь 2015  





Mefistotel пишет:
Что хоть за игра)))?

The Flintstones. The Rescue of Dino and Hoppy.
 
 Top
Mefistotel Администратор
Отправлено: 03 Марта, 2016 - 07:51:38
Post Id



Chief-Net


Покинул форум
Сообщений всего: 7127
Дата рег-ции: Окт. 2014  
Откуда: МАГАДАН





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

-----
"Перевод старых игр - отличная возможность понять, как устроены программы, подучить иностранный язык и поднять уровень владения родным. Ну и конечно, это просто возможность "общения" со своей любимой игрой детства." © Dimouse
 
 Top
Guyver Администратор
Отправлено: 03 Марта, 2016 - 12:02:17
Post Id



Chief-Net


Покинул форум
Сообщений всего: 10117
Дата рег-ции: Окт. 2014  
Откуда: Магадан





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

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

-----
Я не волшебник - я только учусь...
 
 Top
Mefistotel Администратор
Отправлено: 03 Марта, 2016 - 12:21:49
Post Id



Chief-Net


Покинул форум
Сообщений всего: 7127
Дата рег-ции: Окт. 2014  
Откуда: МАГАДАН





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

-----
"Перевод старых игр - отличная возможность понять, как устроены программы, подучить иностранный язык и поднять уровень владения родным. Ну и конечно, это просто возможность "общения" со своей любимой игрой детства." © Dimouse
 
 Top
Guyver Администратор
Отправлено: 03 Марта, 2016 - 12:33:19
Post Id



Chief-Net


Покинул форум
Сообщений всего: 10117
Дата рег-ции: Окт. 2014  
Откуда: Магадан





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

-----
Я не волшебник - я только учусь...
 
 Top
Марат Супермодератор
Отправлено: 03 Марта, 2016 - 12:37:46
Post Id



Chief-Net


Покинул форум
Сообщений всего: 2183
Дата рег-ции: Окт. 2014  
Откуда: Казахстан





Касательно кодировки Флинстоунов можно прочитать здесь https://en.wikipedia.org/wiki/Byte_pair_encoding .
 
 Top
Ace Lightning Пользователь
Отправлено: 03 Марта, 2016 - 12:42:47
Post Id



VIP


Покинул форум
Сообщений всего: 480
Дата рег-ции: Июнь 2015  





Guyver пишет:
Ага, как же, есть Ха-ха

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

Только игра не на GameBoy, а на NES, а в заголовке написано GB.
 
 Top
Guyver Администратор
Отправлено: 03 Марта, 2016 - 12:47:17
Post Id



Chief-Net


Покинул форум
Сообщений всего: 10117
Дата рег-ции: Окт. 2014  
Откуда: Магадан





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

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

-----
Я не волшебник - я только учусь...
 
 Top
Ace Lightning Пользователь
Отправлено: 03 Марта, 2016 - 12:52:21
Post Id



VIP


Покинул форум
Сообщений всего: 480
Дата рег-ции: Июнь 2015  





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

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


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

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

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

(Отредактировано автором: 03 Марта, 2016 - 12:54:13)

 
 Top
Марат Супермодератор
Отправлено: 14 Июня, 2016 - 22:20:10
Post Id



Chief-Net


Покинул форум
Сообщений всего: 2183
Дата рег-ции: Окт. 2014  
Откуда: Казахстан





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


Сразу видно, что это пока не оптимальный вариант, так как нужно исключить дублирование слов и появление коротких слов, которые уже использованы в составе других.
 
 Top
Mefistotel Администратор
Отправлено: 15 Июня, 2016 - 07:17:47
Post Id



Chief-Net


Покинул форум
Сообщений всего: 7127
Дата рег-ции: Окт. 2014  
Откуда: МАГАДАН





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

-----
"Перевод старых игр - отличная возможность понять, как устроены программы, подучить иностранный язык и поднять уровень владения родным. Ну и конечно, это просто возможность "общения" со своей любимой игрой детства." © Dimouse
 
 Top
Mefistotel Администратор
Отправлено: 15 Декабря, 2016 - 02:22:11
Post Id



Chief-Net


Покинул форум
Сообщений всего: 7127
Дата рег-ции: Окт. 2014  
Откуда: МАГАДАН





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

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

-----
"Перевод старых игр - отличная возможность понять, как устроены программы, подучить иностранный язык и поднять уровень владения родным. Ну и конечно, это просто возможность "общения" со своей любимой игрой детства." © Dimouse
 
 Top
Марат Супермодератор
Отправлено: 15 Декабря, 2016 - 19:40:00
Post Id



Chief-Net


Покинул форум
Сообщений всего: 2183
Дата рег-ции: Окт. 2014  
Откуда: Казахстан





Она ещё не доработана. Я её собирался переносить на дельфи в GUI. Но так и не брался за нее.
 
 Top
Марат Супермодератор
Отправлено: 20 Января, 2019 - 15:42:25
Post Id



Chief-Net


Покинул форум
Сообщений всего: 2183
Дата рег-ции: Окт. 2014  
Откуда: Казахстан





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

 
 Top
Griever Пользователь
Отправлено: 20 Января, 2019 - 21:45:36
Post Id


VIP


Покинул форум
Сообщений всего: 457
Дата рег-ции: Июнь 2015  





Не забудь сравнить результат с каноничной MTE Search Tool .
 
 Top
Марат Супермодератор
Отправлено: 20 Января, 2019 - 22:52:36
Post Id



Chief-Net


Покинул форум
Сообщений всего: 2183
Дата рег-ции: Окт. 2014  
Откуда: Казахстан





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

Спойлер (Отобразить)
 
 Top
Марат Супермодератор
Отправлено: 20 Января, 2019 - 23:27:53
Post Id



Chief-Net


Покинул форум
Сообщений всего: 2183
Дата рег-ции: Окт. 2014  
Откуда: Казахстан





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

Завтра надо будет сверить.
 
 Top
Страниц (2): [1] 2 »
Сейчас эту тему просматривают: 4 (гостей: 4, зарегистрированных: 0)
« Программирование »


Все гости форума могут просматривать этот раздел.
Только зарегистрированные пользователи могут создавать новые темы в этом разделе.
Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.
 



> Похожие темы: Оптимальное сжатие в запаковщике
Темы Форум Информация о теме Обновление
Battle City [NES]
АРХИВНАЯ ТЕМА 2011 ГОДА
Переводы Ответов: 10
Автор темы: Ace Lightning
04 Октября, 2016 - 06:38:39
Автор: Mefistotel
Double Dribble [NES]
АРХИВНАЯ ТЕМА 2011 ГОДА
Переводы Ответов: 4
Автор темы: Ace Lightning
04 Октября, 2016 - 06:46:40
Автор: Mefistotel
Приколы
Флудильня Ответов: 9
Автор темы: Ace Lightning
15 Июня, 2018 - 02:11:59
Автор: bybyc9lc9l
Castlevania: Ledends [GB]
АРХИВНАЯ ТЕМА 2012 года
Переводы Ответов: 16
Автор темы: Ace Lightning
07 Сентября, 2016 - 09:49:14
Автор: Mefistotel
Castlevania: Legends (GB)
Разбор алгоритма LZSS
Экстрим хакинг Ответов: 71
Автор темы: Ace Lightning
03 Февраля, 2016 - 07:36:41
Автор: Mefistotel
 

Powered by ExBB
ExBB FM 1.0 RC1 by TvoyWeb.ru
InvisionExBB Style converted by Markus®