Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Программирование [игнор отключен] [закрыт для гостей] / самый простой алгоритм сжатия ? / 15 сообщений из 15, страница 1 из 1
22.08.2011, 13:43
    #37406029
nxx
nxx
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый простой алгоритм сжатия ?
подскажите какой-нибудь самый простой алгоритм сжатия для текста
нужно чтобы буквально несколько строк кода
(ну, может я преувеличиваю)

скорость работы значения не имеет
а вот коэффициент сжатия чем больше тем лучше
хотя простота алгоритма важнее коэффициента сжатия
...
Рейтинг: 0 / 0
22.08.2011, 14:00
    #37406072
DENIS_CHEL
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый простой алгоритм сжатия ?
Алгоритм Хаффмана...
...
Рейтинг: 0 / 0
22.08.2011, 14:35
    #37406151
Edd.Dragon
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый простой алгоритм сжатия ?
DENIS_CHEL,

Когда важен коээфициент сжатия, то программист фигней не страдает (пытаясь придумать эффективное сжатие в несколько строк), а подключает dll-ку того же 7zip и пользуется.

А если задача учебная, написать простенький архиватор, то
а) пофигу на эффективность - ибо эффективные алгоритмы требуют много времени и годами допиливаются, как тот же rar или 7zip;
б) никак в пару строчек не вложишься;
в) читаешь http://ru.wikipedia.org/wiki/Категория:Алгоритмы_сжатия_без_потерь , дальше уже определяешься что проще и понятнее для тебя
...
Рейтинг: 0 / 0
22.08.2011, 14:48
    #37406184
DENIS_CHEL
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый простой алгоритм сжатия ?
Edd.DragonDENIS_CHEL,

Когда важен коээфициент сжатия, то программист фигней не страдает (пытаясь придумать эффективное сжатие в несколько строк), а подключает dll-ку того же 7zip и пользуется.

Ну я как бы и сам пользуюсь готовыми библиотеками, точнее раньше, когда была необходимость пользовался...

PS И коллега я сразу перешел на пункт 'в', из того с чем сам когда-то баловался будучи студентом...
...
Рейтинг: 0 / 0
22.08.2011, 15:05
    #37406221
Edd.Dragon
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый простой алгоритм сжатия ?
Тогда:

1. Чем не устраивают готовые решения, зачем изобретать велосипед?

2. Раз видел готовые решения и количество строк в них и раз "раньше страдал", то откуда могла вообще появиться фраза " нужно чтобы буквально несколько строк кода "?

Т.е. откуда и зачем такое ТЗ? )))
Тогда может будет яснее, что тебе подходит, а что нет
...
Рейтинг: 0 / 0
22.08.2011, 15:15
    #37406243
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый простой алгоритм сжатия ?
Самый простой алгоритм сжатия - это копирование. Правда, выигрыш места нулевой, но зато он максимально прост для понимания и имеет самый короткий исходный код.
...
Рейтинг: 0 / 0
22.08.2011, 16:29
    #37406372
Abstraction
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый простой алгоритм сжатия ?
nxxхотя простота алгоритма важнее коэффициента сжатия
Если нужен учебный алгоритм - предлагаю проявить оригинальность.
Биграммы.
Сделать массив из 255 биграмм ("ла", "не", ", " и т.д.); архивирование:
Код: plaintext
1.
2.
3.
4.
5.
6.
Пока не кончился текст
    Если курсор стоит на начале биграммы из таблицы
        Записать в выходной файл номер биграммы (0-254)
        Сдвинуть курсор на две позиции
    Иначе
        Записать в выходной файл 0xFF, затем текущий символ
        Сдвинуть курсор на одну позицию
Разархивирование:
Код: plaintext
1.
2.
3.
4.
5.
6.
Пока не кончился архив
    Если текущий символ 0xFF
        Записать в выходной файл следующий символ
        Сдвинуть курсор на две позиции
    Иначе
        Записать в выходной файл биграмму, соответствующую коду текущего символа
        Сдвинуть курсор на одну позицию
...
Рейтинг: 0 / 0
23.08.2011, 12:20
    #37407607
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый простой алгоритм сжатия ?
nxxподскажите какой-нибудь самый простой алгоритм сжатия для текста
нужно чтобы буквально несколько строк кода
(ну, может я преувеличиваю)

скорость работы значения не имеет
а вот коэффициент сжатия чем больше тем лучше
хотя простота алгоритма важнее коэффициента сжатия
Есть такой гипотетический архиватор. Вы берёте текст. И (условно) считаете каждое слово
- справочным словом. Тоесть если оно встречается второй раз, то вы добавляете на него
ссылку. Как учитывать ссылку - вопрос отдельный (можно offset) но, при использовании кодов
с плавающей разрядностью (чтоб было компактно) на большом объёме текста
можно получить нехилый прирост. У меня есть предположение что на бесконечности
этот архиватор порвёт все другие супер-архиваторы у которых справочники могут
иметь ограничения.
...
Рейтинг: 0 / 0
23.08.2011, 12:32
    #37407649
Abstraction
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый простой алгоритм сжатия ?
mayton,

Не порвёт. Среднее количество символов в слове русского языка ~9, соответственно, со знаками препинания на авторский лист приходится около четырёх тысяч слов. При словарном запасе автора "бесконечного" текста в 20 000 слов, со словоформами и заглавными буквами набегает под 60 000 в лучшем случае - то есть, два байта. В итоге, авторский лист сжимается до 12 000 байт или 30%.
...
Рейтинг: 0 / 0
23.08.2011, 12:35
    #37407658
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый простой алгоритм сжатия ?
Abstraction, не обязательно слова и словоформы. Можно обрабатывать целые
фразы, предложения и абзацы текста.
...
Рейтинг: 0 / 0
30.08.2011, 15:05
    #37417688
самый простой алгоритм сжатия ?
...
Рейтинг: 0 / 0
30.08.2011, 16:44
    #37417917
Edd.Dragon
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый простой алгоритм сжатия ?
mayton,

Так lzma - это и есть обобщение этого подхода )))
В твоем случае нужно вводить целое множество "если" и "костылей", зависимых от особенности контента (в данном случае - текст на каком-либо языке). А lzma - универсальное обобщение подхода. Ты попросту не сможешь его обскакать. Я не могу доказать тебе это математически ибо доказательство в моей голове на полуинтуитивном уровне. Грубо говоря,ты ограничиваешь себя словом или N словами (фразой), а lzma не ограничивается смысловой нагрузкой - надо будет - он вычленит в словарь 3 с половиной слова с пунктуацией и пробелом. А ты нет. Начнешь отимизировать свой подход - выйдешь на собстенную модификацию lzma.

Но если напишешь свою сжималку, которая сожмет какой-либо (не короткий, чтобы нивелировать размер заголовка) текст лучше 7z с макс. настройками сжатия - я посыплю голову пеплом ;)
...
Рейтинг: 0 / 0
30.08.2011, 17:24
    #37418013
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый простой алгоритм сжатия ?
Может быть ты прав. Но в wiki пишут про ограничение для метода lzma
размером словаря до 4 Гб.

Вообще мой пост - это просто теоретический "посыл" к исследованиям.
Я почти 7 лет клепал разные алгоритмы поиска и генерации простых
чисел. Вобщем-то особого успеха нет. Но в процессе копания пришёл
к выводу что мне нужно было заглядывать 1) в дискретку 2) в теорию
чисел 3) мат. статистику 4) и прочие разделы.
...
Рейтинг: 0 / 0
30.08.2011, 17:37
    #37418047
Edd.Dragon
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый простой алгоритм сжатия ?
maytonМожет быть ты прав. Но в wiki пишут про ограничение для метода lzma
размером словаря до 4 Гб.

Верно.
Для 64-битки ограничения этого нет.

Но ведь этих 4 гиг в десятки раз больше, чем может понадобиться при архивировании многотомного романа, даже если он на нескольких языках сразу.

А если говорить, о специально подобранных данных, которые при ограничении дадут результат хуже, то конечно гипотетический неограниченный размером словаря архиватор порвет ограниченный 7zip. Но гипотетический не ограниченный 7zip скорее всего порвет неограниченный гипотетический "фразо-ориентированный" архиватор ))
...
Рейтинг: 0 / 0
30.08.2011, 17:41
    #37418059
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый простой алгоритм сжатия ?
На бесконечности действуют совершенно другие
законы. Все эти 32, 64 бит можно засунуть в ж., когда
на входе энтропия астрономических масштабов.

Яж говорю. Мой архиватор - чистая теория. Как
"сравниватель" изоморфизма Ретти.
...
Рейтинг: 0 / 0
Форумы / Программирование [игнор отключен] [закрыт для гостей] / самый простой алгоритм сжатия ? / 15 сообщений из 15, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]