| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Сжать! |
| Автор: NoeR 13.7.2005, 23:11 |
| Два вопроса в одном: Как сжать текст и как сжать цыфры? "Например" - занимает 8 байт, а мне надо меньше... "1024768" - можно уместить в 4 байта, даже можно в 3, а в два возможно? Заранее спасибо. |
| Автор: Y-Vladimir 14.7.2005, 08:52 |
| Для начала можно уменьшить количество цифр на представление одного символа. Например для буквы можно взять 5,6 бит - смотря какой алфавит), для цифры - 4 бита. И наконец, сжать это дело каким-либо алгоритмом, напрмер алг. Хафмана. А вообще, степень сжатия зависит от избыточности информации. В твоем примере число "1024768" смахивает на возможное разрешение экрана. Если у тебя фиксированный набор таких чисел, то их можно сжимать (вернее заменять) в несколько бит. Если есть много повторяющихся фргаментов в тексте или цифрах, то лучше использовать алгоритм сжатия LZW. |
| Автор: NoeR 14.7.2005, 15:12 | ||
А где этот сайт был, там где алгоритмы эти...?
Вот как бы это сделать? (Пусть будет фиксировано, т.е. от 0000000(позиция 0х0) до 1024768(позиция 1024х768)). Ну ладно, допустим если одно число - тада заменить просто, например на букву "А", а вот када их много... куда девать все это? Алфавита та нема столько  |
| Автор: SoWa 16.7.2005, 15:24 |
| Ничего невозможно сжать в 2 байта и даже бита. Оттуда не достать уже. |
| Автор: NoeR 16.7.2005, 23:46 |
| SoWa в каком смысле ничего? |
| Автор: Y-Vladimir 18.7.2005, 09:48 | ||||||||
Что-то не понял...
Я не это имел ввиду. Допустим, что у тебя в тексте часто встречаются, в основном, такие значения 800600, 1024768, 640480. Вот их и надо заменять на префиксные коды, а если у тебя с одинаковой вероятностью встречаются числа "от 0000000 до 1024768", то тут никакое сжатие особо не поможет. Основная истина архивации - сжатия происходит за счет наличия у входного потока информации некоторой избыточности. Чем ее больше, тем лучше сжимается инфрмация.
Так не надо алфавит использовать, тут нужно оперировать битами и совокупностями битов.
Не понял фразы. Почему это нельзя? В 2 байта можно, при определенных условиях и мегабайт впихнуть |
| Автор: NoeR 18.7.2005, 12:56 | ||
Вот это как  |
| Автор: Y-Vladimir 18.7.2005, 13:25 | ||
Ну напрмер 12 битов - 4096 комбинаций. Вот их и используй. А вообще, напиши, что тебе конкретно нужно, приведи конкретный фрагмент текста, что хочешь сжать, а то так еще долго можно обсуждать... Вообще, думаю тебе Хаффман или LZW подойдут - дают хорошую степень сжатия и просто реализуются. |
| Автор: Y-Vladimir 18.7.2005, 17:20 |
| А вообще, рекомендую почитать: http://www.compression.ru/arctest/artic-algo.htm Там рассказывается о наиболее известных способах и алгоритмах сжатия информации. Многие вопросы отпадут сами собой. |
| Автор: NoeR 18.7.2005, 19:08 |
| Мне надо сжать положение курсора и текст к нему, чтобы меньше весило... За ссылку спасибо, приеду почитаю  |
| Автор: Y-Vladimir 19.7.2005, 09:13 | ||
А подробнее? Что такое "положение курсора и текст к нему"??? |
| Автор: val 20.7.2005, 11:54 |
| Тебе поможет алгоритм Хафмана. |
| Автор: Y-Vladimir 20.7.2005, 11:57 |
| Лучше наверное LZW, затем Хафман. |
| Автор: NoeR 29.7.2005, 21:51 | ||
Пусть будет просто положение курсора: 1x12, 768x4.... |
| Автор: Y-Vladimir 30.7.2005, 10:20 |
| А зачем это сжимать? Имеются ввиду отдельные значения положения курсора или последовательность таких значений? Только в последнем случае есть смысл что-то сжимать... Опиши ПОДРОБНО свою задачу, тогда можно будет подбирать алгоритм. а то получается гадание по типу игры "Холодно-Горячо" |
| Автор: NoeR 2.8.2005, 13:13 |
| В текст. док. надо сохранять все положения курсора, когда эти положения меняются естественно... Добавлено @ 13:14 И надо сделать так, чтобы файл с этими положениями, был как можно меньше в размере! |
| Автор: Romtek 2.8.2005, 14:50 |
| Повторяющиеся значения можно сжимать по принципу RLE. AAABBCCCCC -> A3B2C5 |
| Автор: Romtek 2.8.2005, 15:48 |
| Что-то, я чувствую, прога будет использоваться не в благих целях... |
| Автор: Y-Vladimir 2.8.2005, 16:03 | ||||
Тогда лучше использовать что-то типа Дельта-модуляции. Т.е. запоминашь только изменение положения курсора относитльно предыдущей позиии. Пример: Вход: (345,594); (345,596); (347,597); (346,599). Выход: (345,594); [0,2]; [2,1]; [-1,1]. Как видишь - значения в квадратных скобках (это посути дельта) заметно меньше по модулю значений на входе, после такого преобразования можно сжимать дальше. Добавлено @ 16:04
Типа прога, котрая запоминает все дейсвия юзера - движения мышкой, нажатия клавиш и сливает их в инет? |
| Автор: NoeR 3.8.2005, 19:30 | ||||||
Учись чувствовать правильно
В принципе спасибо, но тут так не получиться, мало там одинаково будет 
Большое спасибо! Мне это и надо было, ну, во всяком - что-то типа того Теперь мне надо как-то сжимать текст, мне продолжать читать те методы по ссылке, или у кого-нибудь есть идеи? Не спрашивайте пож-ста зачем, надо для чата, тексты большие, много времени на сжатия тратить не могу, так как выгоды от экономии отправки - будет мало... |
| Автор: Romtek 3.8.2005, 22:27 | ||
| Если для чата, нужен обязательно текст, или можно хранить в бинарном коде ? Тогда типа gzip вполне можно применить - есть готовые библиотеки для этого. Если хранить движения мыши в формате дельта, то совсем необязательно, что координаты будут отличаться на +/- 2. Могут быть изменения даже в десятках единиц - зависит также и от скорости движения мыши. P.S.
|
| Автор: Y-Vladimir 4.8.2005, 09:50 | ||
Разумеется могут - у каждого метода есть свои недостатки. Это ведь не метод сжатия, а способ преобразования входных данных таким образом, чтобы дальнейшее сжатие получилось эффективнее. К тому же, обычно юзеры не махают мышкой с огромной скоростью и движения лостаточно плавны - в этом случае подобное преобразование даст ощутимый выигрыш в сжатии. Кстати, не обязательно запоминать все позиции курсора с точностью до пикселя - скорее всего это не требуется, тогда можно огрубить точность дельты - степень сжатия получится еще большей. Начет сжатия текста - либо, как писал Romtek, применяй готовые библиотеки, либо используй алгоритм LZW, т.к. на основе него построено большинство архиваторов. |
| Автор: NoeR 4.8.2005, 14:42 |
| Попробую с LZW, спасибо |