Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Предлагаю алгоритм сжатия текста

Автор: Деордица 17.2.2011, 16:37

Я бы написал на форум http://forum.compression.ru/, но не смог там зарегистрироваться
Предлагаю для сжатия текста следующий алгритм:
Для начала найти 50000 самых частовстречающихся словоформ. Использовать для этого можно библиотеку Мошкова. Это примерно 5000 слов в разных падежах и склонениях. Эти слова будут заменяться на 2 байта, указывающих номер этого слова в таблице. В таблице слова будут располагаться не по частоте, а по алфавиту. Это нужно чтобы ускорить архивирование. В специальном массиве размером 33Х33 будут храниться номера слов которые первыми начинаются с двух данных букв. Например, чтобы найти слово "капля" нужно найти какое слово начинается с "ка" в таблице первым. Затем перебором доходим до слова "капля" и узнаём какой код ему соответствует. Это его номер в таблице.
Пробел кодируется нулём.
Слова которых нет в словаре кодируются единицей, плюс длина слова, плюс само слово.
Те слова которые не попали в 50000 самых частовстречающихся словоформ будут кодироваться тремя байтами. Для этого составляется ещё одна таблица - редковстречающихся словоформ. Размер этой таблицы может достигать примерно 14000*256=3584000 словоформ. Сюда можно запихнуть английский язык и ещё место останется.

Автор: nworm 17.2.2011, 17:25

А что, интересный подход. Можно исследовать, смотреть, менять детали.

Автор: Jimy 17.2.2011, 17:49

Средняя длина слова в русском языке - 5,28 символа (http://www.lingvisto.org/artikoloj/ru_stat.html).
Если даже применить Ваш алгоритм к идеальному для него тексту (100% слов будут содержаться в словаре и будут закодированы по 2 байта на слово), то степень сжатия текста составит около 37% от исходного, что вовсе не является выдающимся результатом.
А для "неидеальных" текстов результат будет и того хуже.

Автор: Деордица 18.2.2011, 12:11

Цитата

степень сжатия текста составит около 37% от исходного, что вовсе не является выдающимся результатом.

Да, но результат сжатия можно сжать ещё каким-нибудь архиватором, правда насколько он будет сжиматься можно определить только экспериментально.

Автор: volatile 19.2.2011, 00:32

Цитата(Деордица @ 18.2.2011, 12:11

)

Да, но результат сжатия можно сжать ещё каким-нибудь архиватором

Чисто по опыту. если текст сжать сначала zip, а потом rar, то результат будет хуже, чем если просто, сразу rar.

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

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

)
В перспективе мы будем иметь очень большой архиватор, который сжимает только текст, и которому для полноценной работы будет нужен еще какой-то архиватор... smile

Автор: borisbn 28.2.2011, 11:10

где-то читал про такой алгоритм сжатия текста:
вычисляется частота появления букв, а не слов, далее самые частые буквы кодируются 4-мя битами (фактически 3-мя, т.е. 8 букв, т.к. 1 бит - маркерный и всегда равен 0). Оставшиеся буквы кодируются 7-ю битами (фактически 5-ю, т.к. 2 бита - маркерные и всегда равны 10). Оставшиеся символы кодируются 8-ю битами (фактически 6-ю, т.к. 2 бита маркерные и всегда равны 11).