Добрый день!
Пишу модуль ядра, который должен сжимать поступающие в него данные и сохранять в ОП. Искал, но не нашел как произвести сжатие строки. Во внутренних (internal) функциях ядра, доступных для моего модуля, есть bunzip2, gunzip, но я не нашел ни одной функции для сжатия (искал в /proc/kallsyms).
Может кто-то сталкивался? Буду очень рад если приведете пример/название драйвера использующего сжатие или натолкнете на мысль.
LinuxForum.Fans
Сжатие данных в модуле ядра
Автор: DendrE
12 сообщений
9379 просмотров
в хедерах же всё проде очень неплохо описано:
include/linux/zlib.h
include/linux/lzo.h
из использующих: deflate - используется ipsec...
ЗЫ: о результатах отпишитесь...
но я не нашел ни одной функции для сжатия
все алгоритмы сжатия используют неизвестно сколько памяти. А в ядре так нельзя. И ещё и работают неизвестно сколько времени. Вам что-то попроще вроде http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A5%D0%B0%D1%84%D1%84%D0%BC%D0%B0%D0%BD%D0%B0 не пойдёт?
все алгоритмы сжатия используют неизвестно сколько памяти.
можете набить морду тому, кто вам это сказал... например LZO - использование памяти О(1)
А в ядре так нельзя.
можно, если это а) необходимо. и б) делать это очень осторожно...
ЗЫ: ещё используется в ./drivers/net/ppp_deflate.c там уж совсем всё очевидно.
все алгоритмы сжатия используют неизвестно сколько памяти.
можете набить морду тому, кто вам это сказал...
эх... лицо-ладонь... щаз убьюсь апстену по вашему совету...
алгоритм сжатия IRL всего один, и он очень прост:
1) для каждого символа считаем его информационную ценность (называется - энтропия)
2) каждый символ кодируем E битами, где E - его энтропия.
3) ???????????
4) PROFIT!
Так работает ЛЮБОЙ известный мне алгоритм сжатия. А знаком я с Over9000 вариантов. Несколько сам написал, кстати.
Что касается bzip2, он неявно вычисляет энтропию. Энтропия зависит от контекста, а контекстов в сообщении из N символов ровно N. bzip2 сортирует все контексты в блоке (обычно 900000 байт), и пожирает при этом 8*900000байт + ещё 400k. После этого, он переставляет символы в сообщении так, что символы с похожим контекстом оказываются рядышком. Дальше всё просто: вычисляется разность этих символов, которая почти всегда равна нулю, ну иногда 1. Бывает больше, но редко. Дальше достаточно сжать всё это по методу Хаффмана (IRL там ещё нули кодируются двумя символами, а не одним. Потому, n нулей закодированы log2(n) символами).
Считать энтропию можно и по другому, но точность будет никакая, как и сжатие. Контексты надо где-то хранить... Пример - LZO, который жрёт всего 64к (а вовсе не O(1). Не, 64к это конечно О(1), но ТСу от этого не легче ни разу)
Как не крутись, но нужно очень много памяти (и/или очень много времени), что-бы получить хоть какое-то приемлемое сжатие. :(
можно, если это а) необходимо. и б) делать это очень осторожно...
ну я и говорю - использовать примитивные древние алгоритмы вроде LZO или Хаффман+расчёт энтропии просто как частоты символов (контекстная модель 0го порядка)...
кстати, xz - тоже жрёт О(1)
674 MiB / 65 MiB
wink
алгоритм сжатия IRL всего один, и он очень прост:
вообще (белей-менее) эффективных в общем случае два: алгоритм хаффмана и сжатие по словарю остальное - а остальное их модификации и комбинации... но
Считать энтропию можно и по другому, но точность будет никакая, как и сжатие. Контексты надо где-то хранить... Пример - LZO, который жрёт всего 64к (а вовсе не O(1). Не, 64к это конечно О(1), но ТСу от этого не легче ни разу)
5 рублей - уже не деньги, 64k - на x86 не память если у ТС что-то нестандартное поддерживать было бы в задачах он бы об этом, наверное, упомянул...
Хаффман+расчёт энтропии просто как частоты символов (контекстная модель 0го порядка)
это вроде и есть описание Хаффмана? точнее алгоритм построения самого дерева, глубина в нём и есть энтропия...
ещё используется zlib, (он в основном и используется, судя по grep'у)... он немного поболее кушает - в зависимости от параметров, но IRL <~ 256K / 44К... но всё в пределах допустимого, если ограничивать кол-во одновременных компрессоров... в общем ничего страшного.
кстати, xz - тоже жрёт О(1)
674 MiB / 65 MiB
:lol: не знал...
вообще (белей-менее) эффективных в общем случае два: алгоритм хаффмана и сжатие по словарю остальное - а остальное их модификации и комбинации...
метод Хаффмана и есть "сжатие по словарю". на каждой символ - своя комбинация байт. Метод Хаффмана может использоваться и для прямого словарного метода, как вы его понимаете. Но вообще, IRL алгоритм сжатия всего один, можно просто по разному считать энтропию, и по разному кодировать. Не модифицированный метод Хаффмана жмёт очень плохо, из-за очень низкой точности - энтропия округляется до целого числа бит, потому возникает значительная погрешность. Например, если жать байты, то они сжимаются максимум в 8 раз :(
Но алфавит можно расширить, и тогда сжатие будет лучше.
5 рублей - уже не деньги, 64k - на x86 не память если у ТС что-то нестандартное поддерживать было бы в задачах он бы об этом, наверное, упомянул...
ну я не знаю... LZO требует 64к. Может и на 8к работать, но наверное раз в 80 медленнее.
это вроде и есть описание Хаффмана? точнее алгоритм построения самого дерева, глубина в нём и есть энтропия...
нет. на входе метод Хаффмана принимает энтропию каждого символа, и переводит её в двоичный код. Но метод Хаффмана имеет погрешность, он не работает с дробными битами.
А вот как вы будете считать энтропию - вопрос другой. И важен именно он. Энтропия == стоимость единицы информации. Чем более важен символ, тем его энтропия выше. Лишние символы имеют нулевую энтропию, и их можно выкинуть. Например букву u, в контексте "после q" и в контексте англ. языка. Ибо в англ, ВСЕГДА после q u, и энтропия u равна нулю. IRL она конечно не всегда равна нулю, и может быть просто очень мала. В таком случае мы выделим для неё не 0 битов, а скажем 0.1 бита.
Метод Хаффмана энтропию НЕ считает, а предполагает, что она УЖЕ вычислена. В учебниках всё-же считает, что-бы было понятнее. Проще всего, считать энтропией величину обратную частоте символов в данном тексте. Как и делается в учебниках. Но на практике так никто не делает, ибо сжатия почти нет. На практике нужно учитывать контексты. К примеру сохранять прошлые N символов, и искать там похожие контексты. Именно так и работают все LZ алгоритмы. В т.ч. LZO.
Кроме того, как я уже писал, можно переставить символы в зависимости от их контекста. Если в тексте хоть что-то похожее есть, тогда символы в похожих контекстах окажутся рядом, типа аааапаааоааааааолааааааоааааАааааОоаа, а уж это сжать тривиально.
Кроме того, можно хранить не все прошлые N символов, а только годные контексты. Если текущий контекст какой-то новый, то мы кодируем особый символ ошибки ESC, а если старый, то кодируем этот символ в данном контексте (после q (почти)всегда u, значит u тут имеет энтропию равную (0.1)0). Такой алгоритм называется PPM. (привет винрару).
ещё используется zlib, (он в основном и используется, судя по grep'у)... он немного поболее кушает - в зависимости от параметров, но IRL <~ 256K / 44К... но всё в пределах допустимого, если ограничивать кол-во одновременных компрессоров... в общем ничего страшного.
не думаю, что использование zlib приведёт к хорошим результатам в данном случае... впрочем - не знаю конечно...
В похожем случае я использовал такой алгоритм:
1) всё записывается блоками переменной длинны
2) первый байт - заголовок блока - число байтов в нём.
3) потом сами байты.
4) после последнего байта - число повторений этого последнего байта.
В худшем случае каждые 256 байтов переходят в 258
В лучшем случае каждые 256 байтов упаковываются в 3.
Память - не нужно.
Время - не нужно.
Автор - не я. Не знаю кто. Украл в чужом платном коде smile
Не пойдёт - тогда zlib. smile
метод Хаффмана и есть "сжатие по словарю". на каждой символ - своя комбинация бит.
// fix
да, сам по себе Хаффман почти не жмёт... поэтому его и сочетают или с перестановками или с LZ - алгоритмами
...он не работает с дробными битами.
я тоже хочу такой травы...
а вообще в теории я откровенно слаб...
В похожем случае я использовал такой алгоритм:
1) всё записывается блоками переменной длинны
2) первый байт - заголовок блока - число байтов в нём.
3) потом сами байты.
4) после последнего байта - число повторений этого последнего байта.
а как выделяется наилучший повторяющийся блок из последовательности байт? просто перебираем блоки по N(от 1 до 256) и выбираем какой лучше ужмётся? а время на этом не потеряем?
// fix
ну бит. без разницы.
сам по себе Хаффман почти не жмёт... поэтому его и сочетают или с перестановками или с LZ - алгоритмами
как раз Хаффман и жмёт. Это способ кодирования нужности символов. А уж чем вы нужность считаете - LZ,PPM, или ещё что то - другой вопрос. Но важный конечно - если в тексте 12% нулей, это не говорит о том, что энтропия любого нуля равна M/0.12. Это средняя энтропия.
я тоже хочу такой травы...
между тем - всё просто. Очевидное решение, сделать алфавит в 65536 символов (ну ввести двухбайтовые буквы, как в UTF-16). В этом случае, одна буква так-же будет занимать минимум бит. Но один байт будет являться половинкой буквы, а следовательно занимать 1/2 бита. На практике так и делают, только считают часто встречающиеся комбинации одной "буквой". Это совсем не обязательно слово, обычно это часть слова, например КОРОВа, КОРОВы, и т.д. в тексте про коров. Метод называется PPM. реализация winrar (есть и свободные. но они старые, и жмут не лучше винрара).
Есть ещё один способ - получив энтропию, мы не переводим её в биты, как делает Хаффман, мы её так и оставляем - числом 0..1. И используем её для уточнения интервала. Каждый символ уточняет интервал, и нам в конце кодирования достаточно передать любое число из этого интервала. Получается длинное число 0..1. На много мегабайт. Распутав его с начала мы можем найти энтропии всех символов, а значит и сами символы. Это арифметическое кодирование, и оно не округляет биты. Потому, даже простой вариант жмёт лучше. Но там патентные ограничения :(
Проще модифицировать Хаффмана, и добиться той-же точности.
а как выделяется наилучший повторяющийся блок из последовательности байт?
очень просто - если в встретились 3 одинаковых байта, блок закончен. Когда-то я строго доказал, что это оптимальная стратегия для любых файлов. Уже не помню доказательство.
Спасибо за ответы.
В качестве примера я использовал testmgr.h в нем наглядно показывается как использовать потоковые функции для компрессии / декомпрессии.
Я специально использовал алгоритмы сжатия поставляемые вместе с ядром, т. к. моей целью была компрессия данных, а не переписывание готовых отлаженных алгоритмов.
Я специально использовал алгоритмы сжатия поставляемые вместе с ядром, т. к. моей целью была компрессия данных, а не переписывание готовых отлаженных алгоритмов.
ну я и не предлагал ничего переписывать. просто надо знать, как ЭТО работает.
Войдите или зарегистрируйтесь, чтобы ответить.
