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


Фотография

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

сжатие текста lua ascii compressing

  • Авторизуйтесь для ответа в теме
Сообщений в теме: 28

#1 Оффлайн   Doob

Doob
  • Пользователи
  • Сообщений: 814
  • Уровень сигнала: 17,03%
  • В игре: 146 час. 10 мин.

Награды

                                   

Отправлено 11 Июль 2016 - 00:01

Люди х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: 11 Июль 2016 - 00:03


#2 Оффлайн   Zer0Galaxy

Zer0Galaxy
  • Гуру
  • Сообщений: 1 230
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

   5                              

Отправлено 11 Июль 2016 - 11:22

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

#3 Онлайн   eu_tomat

eu_tomat
  • Хранители Кода
  • Сообщений: 935
  • Уровень сигнала: 5,93%
  • В игре: 50 час. 55 мин.

Награды

                          

Отправлено 11 Июль 2016 - 23:04

с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


#4 Оффлайн   Zer0Galaxy

Zer0Galaxy
  • Гуру
  • Сообщений: 1 230
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

   5                              

Отправлено 12 Июль 2016 - 10:09

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


#5 Оффлайн   Doob

Doob
  • Автор темы
  • Пользователи
  • Сообщений: 814
  • Уровень сигнала: 17,03%
  • В игре: 146 час. 10 мин.

Награды

                                   

Отправлено 12 Июль 2016 - 10:56

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

 

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

 

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

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


Сообщение отредактировал Doob: 12 Июль 2016 - 11:26


#6 Оффлайн   Zer0Galaxy

Zer0Galaxy
  • Гуру
  • Сообщений: 1 230
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

   5                              

Отправлено 12 Июль 2016 - 11:27

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

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



#7 Оффлайн   Doob

Doob
  • Автор темы
  • Пользователи
  • Сообщений: 814
  • Уровень сигнала: 17,03%
  • В игре: 146 час. 10 мин.

Награды

                                   

Отправлено 12 Июль 2016 - 11:35

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

 

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



#8 Оффлайн   Totoro

Totoro
  • Хранители Кода
  • Сообщений: 1 750
  • Уровень сигнала: 0,26%
  • В игре: 2 час. 13 мин.

Награды

                                      

Отправлено 12 Июль 2016 - 11:38

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

 

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

 

1446443205122931992.jpg



#9 Оффлайн   Doob

Doob
  • Автор темы
  • Пользователи
  • Сообщений: 814
  • Уровень сигнала: 17,03%
  • В игре: 146 час. 10 мин.

Награды

                                   

Отправлено 12 Июль 2016 - 11:46

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

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



#10 Оффлайн   Zer0Galaxy

Zer0Galaxy
  • Гуру
  • Сообщений: 1 230
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

   5                              

Отправлено 12 Июль 2016 - 12:03

Предлагаю для маркирования слова использовать не произвольный символ с кодом >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: 12 Июль 2016 - 12:05


#11 Оффлайн   Doob

Doob
  • Автор темы
  • Пользователи
  • Сообщений: 814
  • Уровень сигнала: 17,03%
  • В игре: 146 час. 10 мин.

Награды

                                   

Отправлено 12 Июль 2016 - 12:18

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



#12 Оффлайн   Zer0Galaxy

Zer0Galaxy
  • Гуру
  • Сообщений: 1 230
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

   5                              

Отправлено 12 Июль 2016 - 13:01

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

 

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

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

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

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

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

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

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



#13 Оффлайн   Doob

Doob
  • Автор темы
  • Пользователи
  • Сообщений: 814
  • Уровень сигнала: 17,03%
  • В игре: 146 час. 10 мин.

Награды

                                   

Отправлено 12 Июль 2016 - 13:20

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

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



#14 Оффлайн   Zer0Galaxy

Zer0Galaxy
  • Гуру
  • Сообщений: 1 230
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

   5                              

Отправлено 12 Июль 2016 - 13:43

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



#15 Оффлайн   Doob

Doob
  • Автор темы
  • Пользователи
  • Сообщений: 814
  • Уровень сигнала: 17,03%
  • В игре: 146 час. 10 мин.

Награды

                                   

Отправлено 12 Июль 2016 - 14:01

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



#16 Онлайн   eu_tomat

eu_tomat
  • Хранители Кода
  • Сообщений: 935
  • Уровень сигнала: 5,93%
  • В игре: 50 час. 55 мин.

Награды

                          

Отправлено 13 Июль 2016 - 10:45

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

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

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

#17 Оффлайн   Doob

Doob
  • Автор темы
  • Пользователи
  • Сообщений: 814
  • Уровень сигнала: 17,03%
  • В игре: 146 час. 10 мин.

Награды

                                   

Отправлено 14 Июль 2016 - 06:40

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

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

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



#18 Онлайн   eu_tomat

eu_tomat
  • Хранители Кода
  • Сообщений: 935
  • Уровень сигнала: 5,93%
  • В игре: 50 час. 55 мин.

Награды

                          

Отправлено 16 Июль 2016 - 19:18

@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 байт
До какого размера жмет твой компрессор оба этих кода, и каков размер декомпрессора?

#19 Оффлайн   Doob

Doob
  • Автор темы
  • Пользователи
  • Сообщений: 814
  • Уровень сигнала: 17,03%
  • В игре: 146 час. 10 мин.

Награды

                                   

Отправлено 16 Июль 2016 - 22:08

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

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

 

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


Сообщение отредактировал Doob: 18 Июль 2016 - 05:50


#20 Оффлайн   Larban

Larban
  • Пользователи
  • Сообщений: 25
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Отправлено 12 Сентябрь 2016 - 19:21

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

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: 12 Сентябрь 2016 - 20:05


#21 Онлайн   eu_tomat

eu_tomat
  • Хранители Кода
  • Сообщений: 935
  • Уровень сигнала: 5,93%
  • В игре: 50 час. 55 мин.

Награды

                          

Отправлено 26 Январь 2017 - 03:00

Я использую пропущенный через минификатор - слов меньше, получается 3951 байт. Самый примитивный декомпрессор - 152 байта, но он не эффективен, т. к. работает в несколько проходов.   P.S. извиняюсь, невнимательно скопировал, декомпрессор занимает 305 байт.

Выполнил я кое-какие расчеты на основе LZ77. Есть мнение, что файл из примера (8615 байт) после сжатия не будет превышать 3300 байт  :smile9: вместе с распаковщиком.
crunch, к примеру, жмет этот файл лишь до 4581 байт.

Вопрос: Насколько востребован такой упаковщик? И стоит ли его доводить до работоспособного состояния?

Сейчас я могу примерно оценить итоговый объем сжатого файла.
Можно довести и до выдачи сжатого кода.
Далее есть несколько участков кода, явно требующих оптимизации, т. к. сейчас всё писалось исключительно для проверки идеи.
В OpenComputers не запускал, и как будет тормозить упаковщик, даже не представляю.
Распаковщик вряд ли будет тормозить, т. к. поток распаковывается в один проход, и его алгоритм немногим сложнее того, что встроен в crunch.
Юникод, само-собой, поддерживается.

#22 Оффлайн   Doob

Doob
  • Автор темы
  • Пользователи
  • Сообщений: 814
  • Уровень сигнала: 17,03%
  • В игре: 146 час. 10 мин.

Награды

                                   

Отправлено 26 Январь 2017 - 05:53

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

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

 

Алгоритм взял не с потолка, сжимал код автозаменой в n++, потом сделал макрос и увидел, что нужен анализ всего словаря, затем каждого слова в отдельности. А все потому-что могут попасться схожие слова, с разной эффективностью, например end - 350 слов (1400 символов), end[пробел] - 300 слов (1200 символов), LZ сначала возьмет то слово, которое больше и эффективность сжатия этого места получится на 14% ниже. Поэтому надо для каждого совпадения проводить сравнение в словаре, чтобы исключать пересекающиеся слова с меньшим коэффициентом сжатия.


Сообщение отредактировал Doob: 26 Январь 2017 - 06:04


#23 Онлайн   eu_tomat

eu_tomat
  • Хранители Кода
  • Сообщений: 935
  • Уровень сигнала: 5,93%
  • В игре: 50 час. 55 мин.

Награды

                          

Отправлено 26 Январь 2017 - 10:03

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

Алгоритм взял не с потолка, сжимал код автозаменой в n++, потом сделал макрос и увидел, что нужен анализ всего словаря, затем каждого слова в отдельности. А все потому-что могут попасться схожие слова, с разной эффективностью, например end - 350 слов (1400 символов), end[пробел] - 300 слов (1200 символов), LZ сначала возьмет то слово, которое больше и эффективность сжатия этого места получится на 14% ниже. Поэтому надо для каждого совпадения проводить сравнение в словаре, чтобы исключать пересекающиеся слова с меньшим коэффициентом сжатия.


1) Разве всеядность LZ77 является недостатком? Вот, урезание диапазона входных данных это скорее минус, нежели плюс. Но если настаивать на нем как на «плюсе», то с его помощью слегка модифицированный LZ77 дополнительно отожмет еще две-три сотни символов. Но сейчас даже без этого сомнительного трюка LZ77 выглядит более эффективным.

2) Не знаю, портит ли crunch код, но его реализация LZ77 точно не самая эффективная. Особенно учитывая, что в самораспаковывающемся коде можно сколь угодно далеко уйти от стандартного алгоритма. Главное, код восстановить. Так вот, пример crunch демонстрирует, что потенциал LZ77 еще не исчерпан. По крайней мере, реально впихнуть 8615 байт уже минизированного Lua-кода в 3300 вместе с шустрым распаковщиком. Вот эти циферки в сравнении с твоими я и предлагаю обсудить.

3) Недословарь, ограниченный 127 словами, будет сильно тебя сдерживать. Отказавшись от фиксированных размеров как словарей, так и ссылок, мне удалось заметно увеличить степень сжатия. Разумеется, моя версия LZ77 тоже имеет ограничения – упаковщик слишком медлителен на больших файлах, но главной задачей я поставил подготовку кода для EEPROM, где хороши все средства ради входа в заветные 4096 байт.

4) Нет смысла говорить об эффективности LZ, не имея в виду конкретную его разновидность и реализацию. Одних только LZ77 я встретил три разных описания, и то, я был не сильно настойчивым в поиске. Предпочтет ли LZ более или менее эффективное слово, сильно зависит от примененных эвристик и зачастую даже не требует изменений в формате файла. Поэтому сейчас я бы предпочел рассуждать не об абстрактных преимуществах алгоритма, а его числовых характеристиках. Мне интересно, улучшилась ли твоя оценка сжатия для тех файлов, что я скинул, и насколько. На раскрытии деталей можешь пока не заморачиваться, достаточно указать выходной размер вместе с распаковщиком.

#24 Онлайн   eu_tomat

eu_tomat
  • Хранители Кода
  • Сообщений: 935
  • Уровень сигнала: 5,93%
  • В игре: 50 час. 55 мин.

Награды

                          

Отправлено 07 Март 2017 - 10:13

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

Можешь скинуть пример повреждаемого файла? Хочу проверить, на каком этапе crunch повреждает файл.

Не смотря на значительное улучшение LZ77, без предварительного синтаксического сжатия lua-кода всё равно не обойтись, а у меня пока нет сил морочиться с ним. Надеюсь, crunch с этим хорошо справляется.

#25 Оффлайн   Doob

Doob
  • Автор темы
  • Пользователи
  • Сообщений: 814
  • Уровень сигнала: 17,03%
  • В игре: 146 час. 10 мин.

Награды

                                   

Отправлено 07 Март 2017 - 11:08

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

 

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



#26 Оффлайн   MeXaN1cK

MeXaN1cK
  • Пользователи
  • Сообщений: 43
  • Уровень сигнала: 7,32%
  • В игре: 62 час. 48 мин.

Награды

              

Отправлено 07 Март 2017 - 16:09

Написаны алгоритмы LZ78 и LZW на Lua, вот собственно что получилось (надеюсь вам это поможет). Исходный файл http://pastebin.com/cCrJVYt9 (в моем примере он называется tresh). LZ78 - http://pastebin.com/X6h2jCda . LZW - http://pastebin.com/E8Qt8HZ9 . Вот собственно результат на скриншоте.

http://clip2net.com/s/3IdK7SX

 

UPD

Из источников стало известно, что алгоритмы не доделаны, но работают.



#27 Онлайн   eu_tomat

eu_tomat
  • Хранители Кода
  • Сообщений: 935
  • Уровень сигнала: 5,93%
  • В игре: 50 час. 55 мин.

Награды

                          

Отправлено 07 Март 2017 - 17:41

Написаны алгоритмы LZ78 и LZW на Lua, вот собственно что получилось (надеюсь вам это поможет). Исходный файл http://pastebin.com/cCrJVYt9 (в моем примере он называется tresh). LZ78 - http://pastebin.com/X6h2jCda . LZW - http://pastebin.com/E8Qt8HZ9 . Вот собственно результат на скриншоте.
http://clip2net.com/s/3IdK7SX

Может, и пригодится кому-то. Но для EEPROM не годится.
8615->4967 LZ78 жмёт хуже версии LZ77 в crunch.
8615->3881 LZW жмёт чуть лучше, но всё равно хуже моей версии LZ77.
Это при том, что часть EEPROM потратится на SFX-модуль.
8615->4581 crunch вместе с SFX
8615->3300 можно сжать вместе с SFX по моим расчетам (не точно, но очень близко к реальности)



#28 Оффлайн   MeXaN1cK

MeXaN1cK
  • Пользователи
  • Сообщений: 43
  • Уровень сигнала: 7,32%
  • В игре: 62 час. 48 мин.

Награды

              

Отправлено 23 Март 2017 - 22:34

Eu_tomat, мне тут подсказал 1 идейку товарищ: поставь в комп дата-карту и использую вот такую библиотеку http://pastebin.com/r7fvtPTA . Может быть это поможет. =)

 

UPD

Вот собственно результаты тестирования этой либы http://c2n.me/3IMOFRd.
Исходный файл тот же. Собственно результат на скрине. А применяется эта библиотека следующим образом:
WinRar.compress(filename,newfilename,limit) - Компрессит файл, нарезая его на фрагменты длины равной лимиту и сжимает его.
WinRar.decompress(filename, newfilename) - Декомпрессит файл.


Сообщение отредактировал MeXaN1cK: 23 Март 2017 - 23:22


#29 Онлайн   eu_tomat

eu_tomat
  • Хранители Кода
  • Сообщений: 935
  • Уровень сигнала: 5,93%
  • В игре: 50 час. 55 мин.

Награды

                          

Отправлено 24 Март 2017 - 09:46

Eu_tomat, мне тут подсказал 1 идейку товарищ: поставь в комп дата-карту и использую вот такую библиотеку http://pastebin.com/r7fvtPTA . Может быть это поможет. =)
 

Обязательно рассмотрю этот вариант через неделю-две, как доберусь до полноценного компа.





Темы с аналогичным тегами сжатие текста, lua, ascii, compressing

Количество пользователей, читающих эту тему: 0

0 пользователей, 0 гостей, 0 анонимных