| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > архивация строки |
| Автор: dstorm81 26.3.2006, 01:18 |
| сильно не бейте если что в общем ситуация такая: пишем слова (цифры+русские+английские символы) затем все переводится к виду 'двоичному' 7 битовому 'А' 0000000 'Б' 0000001 'В' 0000010 'Г' 0000011 'Д' 0000100 'Е' 0000101 'Ё' 0000110 'Ж' 0000111 ..................... 'Z' 1001011 в итоге получается строка типа 0001100000010100110100000000010101100100110010100010101100011010011 00000001000001001000110000000000101011010000101000010101000 вопрос: какой метод сжатия лучше использовать в данном случае (в нэте я кое что нашел, типа Хофмана, LZ) и если можно общую суть алгоритма, если есть какой-то свой вариант. |
| Автор: nworm 26.3.2006, 20:13 |
| Скорее всего подойдёт метод Хафмана или арифметическое сжатие. Но может быть что-то можно будет ещё выжать, проанализировав получше исходные данные. О сжатии можно поспрашивать на http://www.compession.ru. Там у них есть бесплатные главы из книги и форум. |
| Автор: SoWa 27.3.2006, 19:02 |
| Я на нули гляжу... Может записывать цифру(ненулевую, ибо их в строке нету)- кол-во нулей. При разжатии вместо цифры- нули. |
| Автор: nworm 27.3.2006, 22:38 | ||
У символов 'Б', 'В' одинаковое число нулей. При таком способе кодирования, наверное, не будет однозначности декодирования. А, вообще, интересно. dstorm81 А почему 'Z' 1001011? Если калькулятор не врёт, то в десятичной системе счисления это 75 != 10 + 33 + 26. |
| Автор: esperant0 27.3.2006, 23:31 | ||
Вообщето, согласно одной из теорем кодирования, для длинных текстов Хафман оптимален до эпсиолна. И ваше замечание не релевантно. Арифметической кодирование также достигает нижней границы сжатия |
| Автор: SoWa 28.3.2006, 09:16 |
| nworm, ну и что, что одинаковое. Например вместо трех нулей напишу "3". |
| Автор: nworm 28.3.2006, 15:20 | ||||
В той теореме вероятность, что следующим символом будет какой-то наперёд заданный символ (например, '1') постоянная для любого места в тексте . А если цифры с буквами, то могут буть тектсты, где за цифрой с большей вероятностью идет другая цифра, а не буква и т.п. |
| Автор: dstorm81 28.3.2006, 22:46 | ||
2 nworm
ну вот такой вот такой странный алфавит для тех кто смотрит на нули, предполагается закрытие все 7 бит, то есть в алфавита конце будут 1111110 1111111 тут нулей вобщем уже нема ну мне так и не порекомендовали чем лучше сжимать, мне еще стоит подождать-то? |
| Автор: nworm 29.3.2006, 08:09 |
| Я же в первом посте написал. Повторяю 1. Если задача сжатия не является центральной или могут быть произвольные тексты (известен только алфавит), использовать лучше арифметическое сжатие или метод Хафмана. 2. В других случаях можно подумать, какие будут исходные тексты, что-то поискать по сжатию своего типа текстов, спросить, например, на www.compression.ru. |
| Автор: dstorm81 29.3.2006, 22:29 |
| спасибо всем ... |
| Автор: esperant0 29.3.2006, 23:30 | ||
смысл второй части от меня ускользает. Определите более формально модель и что вы хотите сказать. Иначе это не консистентно |
| Автор: nworm 30.3.2006, 14:21 |
| Цитата из книги с "Методы сжатия данных" с http://www.compression.ru/, глава методы контекстного моделирования: "Анализ распространенных типов данных - например, тех же текстов на естественных языках, - выявляет сильную зависимость вероятности появления символов от непостредственно им предшествующих. Иначе говоря, большая часть данных с которыми мы сталкиваемся, порождается источником с памятью. Допустим, нам известно, что сжимаемый блок является текстом на русском языке. Если, например, из трех только что обработанных символов равна "_цы" (подчеркиванием здесь и далее обозначается пробел), то текущий символ скорее всего входит в следующую группу 'г' ("цыган"), 'к' ("цыкать"), 'п' ("цыпочки"), 'ц' ("цыц"). Или, в случае аналдиза сразу нескольких слов, если предыдущая строка равна "Вставай,_проклятьем_заклейменный,", то продолжением явно будет "весь_мир_". Действительно, в случае посимвольного кодирования при использовании информации об одном непосредственно предшествующем символе достигается средняя длина кодов в 3.6 бита для русских текстов, при учёте двух последних - уже порядка 3.2 бита. В первом случае моделируются условные распределения вероятьностей символов, зависящие от значения строки из одного непосредственно предшествующего символа, во втором - зависящие от строки из двух предшествующих символов." Похожая ситуация может возникнуть (а может и не возникнуть), если dstorm81 будет сжимать только какие-то специальные тексты (например, только тексты на естественных языках или только финансовые отчёты). |
| Автор: maxim1000 30.3.2006, 14:56 | ||
кстати, можно использовать Хаффмана/арифметическое кодирование и во втором случае - достаточно на каждом шагу использовать не одну и ту же кодировку, а оптимальную для текущего распределения в случае Хаффмана это приводит к необходимости частой перестройки дерева - с арифметическим кодированием это несколько проще... |
