Сжатие строки

From

Anthone Tikhonov ()

To

Evgeniy Jirnov

Date

2002-10-14T11:23:44Z

Area

RU.ALGORITHMS

From: "Anthone Tikhonov" <ia26@vtb.ru>

 EJ> Объясните мне как можно произвести сабж. То есть на входе обычная строка,
 EJ> а на выходе строка меньшей длины. На входе сжатая строка, на выхода
 EJ> обычная строка.
 EJ> Строка размером или <255 или <65536

Сам никогда не занимался, но то, что помню из лекций по дискре:

1) Поиск наиболее часто повторяющихся участков в строке, и замена их
  на более короткую комбинацию символов-код, в начале строки помещается 
  описание всех таких кодов; если в исходной строке встречается сам 
  код, его надо заменить на что-то еще 

2) Подсчет частоты каждой буквы и замена частых букв на более короткие 
битовые коды, а редких - на более длинные
Например, если у нас строка из 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)