|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Anthone Tikhonov 2:5020/400 14 Oct 2002 11:23:44
To : Evgeniy Jirnov
Subject : Сжатие строки
--------------------------------------------------------------------------------
EJ> Объясните мне как можно произвести сабж. То есть на входе обычная строка,
EJ> а на выходе строка меньшей длины. Hа входе сжатая строка, на выхода
EJ> обычная строка.
EJ> Строка размером или <255 или <65536
Сам никогда не занимался, но то, что помню из лекций по дискре:
1) Поиск наиболее часто повторяющихся участков в строке, и замена их
на более короткую комбинацию символов-код, в начале строки помещается
описание всех таких кодов; если в исходной строке встречается сам
код, его надо заменить на что-то еще
2) Подсчет частоты каждой буквы и замена частых букв на более короткие
битовые коды, а редких - на более длинные
Hапример, если у нас строка из 3х-битовых байтов
000 001 010 011 100 101 110 111, то их можно закодировать другим
набором - 1 01 001 00000 00001 00010 000110 000111
Здесь почти все коды длиннее чем 3, но зато 1 и 01 - короче,
кодируя ими самые частые буквы, мы можем получить выигрыш
Основная сложность здесь в том, что в наборе кодов ни один код не
должен быть началом другого кода, например 001 - это начало 00110,
иначе мы не сможем раскодировать полученную последовательность битов
Был какой-то алгоритм генерирования этих кодов по частотам букв, но
я не помню, как он даже называется
Вообще, можно покопаться в Инете и поискать алгоритмы построения
архиваторов, там все это и не только это должно быть
Антон
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
Сжатие строки |
Evgeniy Jirnov |
11 Oct 2002 02:19:02 |
 Сжатие строки |
Anthone Tikhonov |
14 Oct 2002 11:23:44 |
 RE: Сжатие стpоки |
Anatoly Svishev |
12 Oct 2002 22:48:18 |
|
|
