сильно не бейте если что
в общем ситуация такая: пишем слова (цифры+русские+английские символы)
затем все переводится к виду 'двоичному' 7 битовому
'А' 0000000
'Б' 0000001
'В' 0000010
'Г' 0000011
'Д' 0000100
'Е' 0000101
'Ё' 0000110
'Ж' 0000111
.....................
'Z' 1001011

в итоге получается строка типа
0001100000010100110100000000010101100100110010100010101100011010011
00000001000001001000110000000000101011010000101000010101000
вопрос: какой метод сжатия лучше использовать в данном случае (в нэте я кое что нашел, типа Хофмана, LZ)
и если можно общую суть алгоритма, если есть какой-то свой вариант.

Скорее всего подойдёт метод Хафмана или арифметическое сжатие. Но может быть что-то можно будет ещё выжать, проанализировав получше исходные данные. О сжатии можно поспрашивать на www.compession.ru. Там у них есть бесплатные главы из книги и форум.

Я на нули гляжу...
Может записывать цифру(ненулевую, ибо их в строке нету)- кол-во нулей. При разжатии вместо цифры- нули.

У символов 'Б', 'В' одинаковое число нулей. При таком способе кодирования, наверное, не будет однозначности декодирования. А, вообще, интересно.

dstorm81
А почему 'Z' 1001011? Если калькулятор не врёт, то в десятичной системе счисления это 75 != 10 + 33 + 26.

Это сообщение отредактировал(а) nworm - 27.3.2006, 22:40

Вообщето, согласно одной из теорем кодирования, для длинных текстов Хафман оптимален до эпсиолна.

И ваше замечание не релевантно.

Арифметической кодирование также достигает нижней границы сжатия

nworm, ну и что, что одинаковое. Например вместо трех нулей напишу "3".

В той теореме вероятность, что следующим символом будет какой-то наперёд заданный символ (например, '1') постоянная для любого места в тексте . А если цифры с буквами, то могут буть тектсты, где за цифрой с большей вероятностью идет другая цифра, а не буква и т.п.

2 nworm

ну вот такой вот такой странный алфавит
для тех кто смотрит на нули, предполагается закрытие все 7 бит, то есть в алфавита конце будут 1111110 1111111 тут нулей вобщем уже нема
ну мне так и не порекомендовали чем лучше сжимать, мне еще стоит подождать-то?

Я же в первом посте написал. Повторяю

1. Если задача сжатия не является центральной или могут быть произвольные тексты (известен только алфавит), использовать лучше арифметическое сжатие или метод Хафмана.

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

спасибо всем ...

смысл второй части от меня ускользает. Определите более формально модель и что вы хотите сказать. Иначе это не консистентно

Цитата из книги с "Методы сжатия данных" с http://www.compression.ru/, глава методы контекстного моделирования:
"Анализ распространенных типов данных - например, тех же текстов на естественных языках, - выявляет сильную зависимость вероятности появления символов от непостредственно им предшествующих. Иначе говоря, большая часть данных с которыми мы сталкиваемся, порождается источником с памятью. Допустим, нам известно, что сжимаемый блок является текстом на русском языке. Если, например, из трех только что обработанных символов равна "_цы" (подчеркиванием здесь и далее обозначается пробел), то текущий символ скорее всего входит в следующую группу 'г' ("цыган"), 'к' ("цыкать"), 'п' ("цыпочки"), 'ц' ("цыц"). Или, в случае аналдиза сразу нескольких слов, если предыдущая строка равна "Вставай,_проклятьем_заклейменный,", то продолжением явно будет "весь_мир_". Действительно, в случае посимвольного кодирования при использовании информации об одном непосредственно предшествующем символе достигается средняя длина кодов в 3.6 бита для русских текстов, при учёте двух последних - уже порядка 3.2 бита. В первом случае моделируются условные распределения вероятьностей символов, зависящие от значения строки из одного непосредственно предшествующего символа, во втором - зависящие от строки из двух предшествующих символов."

Похожая ситуация может возникнуть (а может и не возникнуть), если dstorm81 будет сжимать только какие-то специальные тексты (например, только тексты на естественных языках или только финансовые отчёты).

кстати, можно использовать Хаффмана/арифметическое кодирование и во втором случае - достаточно на каждом шагу использовать не одну и ту же кодировку, а оптимальную для текущего распределения

в случае Хаффмана это приводит к необходимости частой перестройки дерева - с арифметическим кодированием это несколько проще...