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

[Doob 2 749]

Люди х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 бит, остальные символы можно использовать в качестве индексов словаря в сжатом тексте.

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

Изменено 10 июля, 2016 пользователем Doob

[Zer0Galaxy 2 187]

 

 

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

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

[eu_tomat 2 155]

с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

[Zer0Galaxy 2 187]

 

 

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

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

string.gsub("abrakadabra","ab","AB") --> ABrakadABra 

[Doob Автор темы 2 749]

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

 

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

 

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

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

Изменено 12 июля, 2016 пользователем Doob

[Zer0Galaxy 2 187]

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

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

[Doob Автор темы 2 749]

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

 

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

[Totoro 3 563]

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

 

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

 

[Doob Автор темы 2 749]

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

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

[Zer0Galaxy 2 187]

Предлагаю для маркирования слова использовать не произвольный символ с кодом >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 – количество вхождений слова в текст (если слово встречается в тексте только один раз, внесение его в словарь не даст эффекта).

Изменено 12 июля, 2016 пользователем Zer0Galaxy

[Doob Автор темы 2 749]

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

[Zer0Galaxy 2 187]

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

 

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

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

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

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

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

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

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

[Doob Автор темы 2 749]

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

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

[Zer0Galaxy 2 187]

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

[Doob Автор темы 2 749]

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

[eu_tomat 2 155]

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

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

 

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

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

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

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

[Doob Автор темы 2 749]

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

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

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

[eu_tomat 2 155]

@@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 байт

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

[Doob Автор темы 2 749]

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

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

 

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

Изменено 18 июля, 2016 пользователем Doob

[Larban 15]

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

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 байт (и его можно еще уменьшить,я не стал уменьшать еще потому что код станет совсем не читаемым)

Изменено 12 сентября, 2016 пользователем Larban