Перейти к содержимому
Doob

Задачка (алгоритм: ASCII-компрессор)

Рекомендуемые сообщения

Люди хoтят решать задачки? Чтo-ж, раз нечегo делать, тo лучше делать чтo-тo пoлезнoе. У меня есть прoстая задача, нo гoтoвых реализаций не встречал. Интереснo, какие есть спoсoбы решения, если приoритет алгoритма декoмпрессии - кoмпактнoсть, а кoмпрессии - скoрoсть (сo скoрoстью у меня прoблемы).

Алгoритм сжатия ASCII текста (oчень хoрoшo пoдхoдит для упакoвки Lua-кoда, степень сжатия как deflate, нo кoд намнoгo кoмпактней):

1. Сoздать пустoй слoварь
2. Найти в тексте пoвтoряющиеся слoва длинны L
    Если есть сoвпадения, тo:
        Если длинна слoваря <= 127:
            Внести слoвo в слoварь.
            Заменить в исхoднoм тексте слoва на симвoл с кoдoм [длинна_слoваря+128]
    Иначе:
        L--
        Если L == 2:
            Перехoд к шагу 3
        Иначе:
            Пoвтoрить шаг 2
3. Присoединить слoварь к тексту.
4. Вернуть текст.

Алгoритм декoмпрессии:

 

1. Отделить слoварь oт текста.
2. Взять oчереднoе слoвo из слoваря.
3. Найти в тексте ссылку на слoвo из слoваря (найти симвoл с кoдoм [индекс_текущегo_слoва+128]).
4. Заменить ссылку на слoвo.
5. Если еще не все ссылки заменены, тo:
    Перехoд к шагу 3
   Иначе, если индекс текущегo слoва != длинне слoваря:
    Перехoд к шагу 2
   Иначе:
    Вернуть текст.

 

Число 128 используется, потому-что коды текстовых символов в ASCII влезают в 7 бит, остальные символы можно использовать в качестве индексов словаря в сжатом тексте.

Псевдокод вроде-бы четкий, но и без подсказок.

Изменено пользователем Doob

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

 

 

Число 128 используется, потому-что коды текстовых символов в ASCII влезают в 7 бит, остальные символы можно использовать в качестве индексов словаря в сжатом тексте.
А как же кириллица?  Она же >127, или нет?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

сo скoрoстью у меня прoблемы

Потому что

Заменить в исхoднoм тексте слoва на симвoл с кoдoм

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

 

 

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

 

К примеру, нужно склеить символы 1 2 3 4 5 6 7 8. Имеем строки:

1, 12, 123, 1234, 12345, 123456, 1234567, 12345678 при линейной конкатенации и

12, 34, 56, 78, 1234, 5678, 12345678 при двоичной.

Разница в длинах заметна на глаз даже для итоговой строки длиной в 8 символов.

 

Код, выполнявшийся на двух планках памяти T3.5, говорит сам за себя:

-- тестирование конкатенации строк

local time = require("computer").uptime

-- линейная конкатенация
local time0 = time()
local s=""
for i=1,1024*32 do s=s.."." end
print(string.format("time: %.2f sec", time()-time0 ))
-- 8k: 0.15-0.25sec, 16k: 0.55-1.05sec, 32k: 1.5-2.95sec, 64k: TLWY

os.sleep(0) -- для избежания TLWY

-- двоичная конкатенация
local time0 = time()
local tbl={}
for i=1,1024*128 do tbl[#tbl+1]="." end
while #tbl>1 do local tb_={} for i=1,#tbl-1,2 do tb_[#tb_+1]=tbl[i]..tbl[i+1] end tbl=tb_ end
local s=tbl[1]
print(string.format("time: %.2f sec", time()-time0 ))
-- 128k: 0.30 sec, 256: not enough memory

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

 

 

Заменить в исхoднoм тексте слoва на симвoл с кoдoм
А если для этого использовать не конкатенацию а функцию gsub?
string.gsub("abrakadabra","ab","AB") --> ABrakadABra 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

А как же кириллица?  Она же >127, или нет?

 

А какая польза от кириллицы в Lua? Как по мне, только вред - кодировка может слететь и файл будет забиваться мусором.

 

P. S. Если я правильно помню, Lua используются только 92 символа, а в таблице их 256.

P. P. S. Советую предварительно погуглить алгоритмы сжатия или парсинга.

Изменено пользователем Doob

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

А какая польза от кириллицы в Lua? Как по мне, только вред - кодировка может слететь и файл будет забиваться мусором.

А я вот недавно просматривал код одного автора, так там кириллица совсем не вредит, а очень даже к стати.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

 

P. S. А во времена DOS комменты писались транслитом.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Потому-что код писался в одном файле, за один проход. Если код изменяется, переносится из одного редактора в другой, то слетевшая кодировка просто удаляется, потому-что переписывать комментарии, если и так понятно, как оно работает очень утомительно.

 

Есть мнение, что комментарий стоит писать, когда он поясняет что-то не понятное, или не очевидное из кода.  :)

 

1446443205122931992.jpg

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

А опытным дяденькам и код не нужен, ибо он уже есть в их головах.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Предлагаю для маркирования слова использовать не произвольный символ с кодом >127, а строго определенный символ, который никогда не встречается в lua-тексте или встречается крайне редко, например, символ с кодом 255. Правда, в этом случае слово в тексте будет замещаться не одним байтом, а двумя 255+<номер слова>. Это позволит сжимать тексты с кириллицей к тому же длина словаря увеличивается до 256 слов

Тогда алгоритм сжатия выглядит как-то так:

1. Сoздать пустoй слoварь
2. Найти в тексте слово с максимальным показателем сжатия P
    Если P<1 переход к шагу 3    -- нет слов для сжатия
    Заменить в исхoднoм тексте слoва на симвoл с кодом 255 + символ с кoдoм [длинна_слoваря]
    Внести слoвo в слoварь.
    Если длинна слoваря > 255 переход к шагу 3  -- словарь заполнен
    Иначе переход к шагу 2
3. Присoединить слoварь к тексту.
4. Вернуть текст.

Упомянутый показатель сжатия P показывает как сжимается текст в результате внесения слова в словарь. Очевидно, что он тем больше чем длиннее слово и чем чаще оно встречается в тексте. Показатель сжатия можно оценить как:

P=(L-2)*(N-1)

где L – длина слова (слова длинной <=2 не сжимаются);

N – количество вхождений слова в текст (если слово встречается в тексте только один раз, внесение его в словарь не даст эффекта).

Изменено пользователем Zer0Galaxy

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Тут уже возникают вопросы стандартизации, если я не использую UTF8, то использую Windows-1251, а тут символ 255 - "я". К тому-же надо использовать два символа, например 254 и 255 для обозначения диапазона закодированного символа. Дополнительно, для отделения словаря от текста надо использовать еще один символ, например, 253. Либо выкидываем 3 последних символа алфавита, если попадается текст с кодировкой W1251, либо подбираем такие символы, которые не будем использовать в комментариях во всех популярных кодировках.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

На счет использования символа 255 в разных кодировках говорить не буду, не изучал. Да и привел его лишь для примера. Не нравится этот, можно выбрать другой. К тому же вхождение символа 255 (или любого другого) в исходный текст не исключает использования его в качестве служебного. Достаточно завести под него слово в словаре. Определяем слово под номером ноль, состоящее из одного символа 255, а в исходном тексте все символы 255 заменяем на комбинацию символов 255+0. Главное, чтобы служебный символ встречался в несжатом тексте не слишком часто.

 

Что же касается дополнительных служебных символов 254 и 253, думаю можно обойтись без них если принять такой формат сжатого файла:

1) длина словаря - 1 байт. Поскольку словарь не может содержать более 256 слов, одного байта будет достаточно.

2) Словарь. Каждое слово в словаре представлено в виде:

    2.1) длина слова - 1 байт (это накладывает ограничение на максимальную длину слова в 256 символов)

    2.2) собственно слово.

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

3) Сжатый текст. Вот тут каждый встреченный служебный символ вместе с последующим за ним должны быть заменены на соответствующее слово из словаря.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Кажется, это уже другой алгоритм. Я не использую управляющие символы, т. к. если они попадают в IO - закодированный текст повреждается, при тестировании я использовал такую схему:

слово1[FF]слово2[FF]слово3[FF]слово4[FF]тексттекст[80]тексттексттек[81]сттекст[82][83]тексттекст[84]
т. е. словарь отделен от текста символом [FF] и слова отделены друг от друга тем же символом (либо символом [FE], чтобы легче было отделять словарь)

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

И всё же я бы не рекомендовал ограничивать исходный текст 128-ю символами. И дело даже не в кириллице. Вот в твоем скринсейвере используется символ "▄". А одного такого символа уже достаточно чтобы архив стал нераспаковываемым.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

А если для этого использовать не конкатенацию а функцию gsub?

Точно. gsub в твоем алгоритме эффективен. Зациклился на классических алгоритмах. Кстати, они мне кажутся более уместыми, как по причине большего объема словаря, так и по всеядности. Ну, ладно, твой выбор понятен.

 

Мне непонятны условия задачи.

1. Сначала ты говоришь об ASCII, потом говоришь, что не используешь управляющие символы ASCII, т.к. они повреждают текст. При этом перевод строки и табуляция текст не повреждают, хотя и являются управляющими символами. Какие символы во входящем потоке являются допустимыми для твоего алгоритма? Определившись с ними, можно будет еще до сжатия проверить поток на запрещенные символы.

2. Также не ясно, какие символы допустимы в исходящем потоке.

3. Ты сравниваешь сжатие своим алгоритмом с deflate. На каких данных проводилось тестирование? Насколько объемен входящий код? Насколько я понимаю, степень сжатия заметно уменьшится при недостаточном объеме словаря.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

1. Подготовленный к сжатию Lua код не содержит табуляций и переносов. Тут я беспокоюсь о конечных пользователях, которые скопируют сжатый текст CTRL+C>CTRL+V и скажут "НИРАБОТАИТ11!". Для исходников хватит диапазона 20-7E (символы 09 0A можно перенести на 24 и 7F, соответственно. Можно даже использовать управляющие символы, но это уже расширенная версия алгоритма)

2. Все текстовые и вторая половина таблицы.

3. Изначально, я составил словарь используемых в Lua выражений и сжимал подготовленные тексты этим алгоритмом и универсальными, deflate догоняет этот алгоритм на исходных текстах более 1 КБ (но это зависит от типа кода, если в коде много вычислений - мало повторяющихся последовательностей, то deflate может и лучше, но он все-равно хуже из-за объема собственного исходного кода)

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

@@Doob,

Подготовленный к сжатию Lua код не содержит табуляций и переносов. Тут я беспокоюсь о конечных пользователях, которые скопируют сжатый текст CTRL+C>CTRL+V и скажут "НИРАБОТАИТ11!". Для исходников хватит диапазона 20-7E (символы 09 0A можно перенести на 24 и 7F, соответственно.

А почему тебя не заботит то, что исходящий поток содержит символы за пределами ASCII? Вдруг пользователь не в той кодировке скопирует? Правильным было бы либо разрешить все символы, либо везде ограничиться печатными символами ASCII.

 

deflate догоняет этот алгоритм на исходных текстах более 1 КБ

Что-то я еще более запутался. В чем смысл жать исходники начальным размером менее 1КБ? Проблема, как правило, впихнуть в BIOS код более 4КБ. Давай разберем на примере.

 

Есть библиотека filesystem из OpenOS:

http://pastebin.com/xfM5yrsu оригинал filesystem.lua, 13457 байт

http://pastebin.com/S1uscQ8t результат работы минификатора, 8615 байт

До какого размера жмет твой компрессор оба этих кода, и каков размер декомпрессора?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Я использую пропущенный через минификатор - слов меньше, получается 3951 байт.

Самый примитивный декомпрессор - 152 байта, но он не эффективен, т. к. работает в несколько проходов.

 

P.S. извиняюсь, невнимательно скопировал, декомпрессор занимает 305 байт.

Изменено пользователем Doob

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

самый примитивный декомпрессор

function dec(c,s)
d={}
g=string.gsub
g(s..",","[^%,]+%,",load("n={...};table.insert(d,string.sub(n[1],1,#n[1]-1))"))
for i=1,#d,2 do
c=g(c,d[i],d[i+1])
end
return c
end 

занимает 176 байт (и его можно еще уменьшить,я не стал уменьшать еще потому что код станет совсем не читаемым)

Изменено пользователем Larban

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.

Гость
Ответить в тему...

×   Вы вставили отформатированное содержимое.   Удалить форматирование

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отобразить как ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.


×
×
  • Создать...