Без описания |
Поиск в теме | Версия для печати |
Ace Lightning |
Отправлено: 20 Февраля, 2016 - 10:47:53
|
VIP
Покинул форум
Сообщений всего: 480
Дата рег-ции: Июнь 2015
|
Всем привет.
Возник вот такой вот вопрос, касающийся некоторых алгоритмов сжатия. Задача ромхакера, в случае запакованных данных в игре, сводится к тому, чтобы
1) определить расположение пожатых данных в роме;
2) разобраться в алгоритме распаковки;
3) написать распаковщик;
4) написать упаковщик, который максимально эффективно сожмет данные.
На 4 этапе возникает проблема, решение которой мне кажется достаточной далеким и туманным. Эта проблема возникала у меня каждый раз, когда я подходил к 4 пункту. Собственно, это проблема единственная, которая мешает мне выпустить два практически готовых перевода. Может быть есть тот, кто понимает о чем я говорю и решил эту проблему. |
|
|
Ace Lightning |
Отправлено: 20 Февраля, 2016 - 12:03:38
|
VIP
Покинул форум
Сообщений всего: 480
Дата рег-ции: Июнь 2015
|
Ну вот, чтобы не лезть во всякие LZ, есть такой простой пример. Есть текст, в котором некоторыми байтами, например с $30 до $FF указывается номер записи в словаре. Как оптимизировать запаковку текста по такой схеме? Ясно, что последовательность равную одному байту запаковывать нет смысла. Тогда уже будем искать только повторяющиеся последовательности размером больше одного байта. Можно отсортировать по количеству совпадений последовательности в тексте и запаковать все самые часто встречающиеся, пока не будет привешена длина словаря. Но! Например в конце будет очень длинная последовательность, которая встречается в тексте очень малое количество раз и алгоритм до нее просто не дойдет, но логически понятно, что загнать ее в словарь будет самое то.
Хочется какой-то компромисс программно сделать, чтобы сжатие было эффективно.(Отредактировано автором: 20 Февраля, 2016 - 12:18:23) |
|
|
Mefistotel |
Отправлено: 22 Февраля, 2016 - 03:28:10
|
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 ).
----- "Перевод старых игр - отличная возможность понять, как устроены программы, подучить иностранный язык и поднять уровень владения родным. Ну и конечно, это просто возможность "общения" со своей любимой игрой детства." © Dimouse |
|
|
Ace Lightning |
Отправлено: 02 Марта, 2016 - 14:30:11
|
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) |
|
|
Ace Lightning |
Отправлено: 02 Марта, 2016 - 15:42:44
|
VIP
Покинул форум
Сообщений всего: 480
Дата рег-ции: Июнь 2015
|
Марат пишет:Ace Lightning пишет:А сам алгоритм запаковки прост:
1) Проходимся по всему тексту и ищем самую длинную последовательность.
2) Помещаем ее в словарь.
3) Запаковываем.
4) Переходим к пункту 1.
Не согласен.
Если просто отбирать самые длинные слова и помещать их в словарь, то он быстро переполнится. Слово может занимать 15 байт, но встречаться всего лишь один раз, в то время как другие более короткие слова могут быть длиной меньше, например, 5 байт, но встречаться раз 20 в тексте. Поэтому нужно длину слова умножать на количество вхождений и тогда ты узнаешь истинный вес этого слова. В общем, нюансов много и их надо учитывать.
ой, ошибся, конечно, не самую длинную последовательность, а ту, которая встречается в тексте больше всего раз. Прошу прощения.
Марат пишет:Поэтому нужно длину слова умножать на количество вхождений и тогда ты узнаешь истинный вес этого слова.
А вот это очень интересно, можно попробовать запаковывать именно по такому принципу. Хотя тут тоже есть над чем подумать.(Отредактировано автором: 02 Марта, 2016 - 15:52:42) |
|
|
|
Поиск в теме | Версия для печати |
Страниц (2): [1] 2 » |
Сейчас эту тему просматривают: 1 (гостей: 1, зарегистрированных: 0) |
« Программирование » |
Все гости форума могут просматривать этот раздел. Только зарегистрированные пользователи могут создавать новые темы в этом разделе. Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.
|
|
|