Николай Невесенко
	      ЛЕМПЕЛЬ-ЗИВ В ПЛАНЕ МИНИМИЗАЦИИ ПРОГРАММЫ

Домашняя страница

	1. Знакомство с Лемпелем-Зивом
	2. Оптимален ли Лемпель-Зив?
	3. Дешифровщик
	4. Варианты усовершенствования
	5. Ускорение архивации

	Минимизация не отменяет требований к сжатию и к скорости.
Представлен архиватор COM-файлов, дающий лучшее сжатие среди известных
аналогов. При этом его собственный объем менее 0.5 КБ.

		   1. Знакомство с Лемпелем-Зивом

	В отличие от Хаффмана за Лемпелем и Зивом не стоит столь
однозначного и блестящего алгоритма. Есть только довольно расплывчатая
идея, к которой многие приложили руку. Но эта идея обычно приводит к
сжатию намного лучше, чем по Хаффману. Поэтому этой идее многое можно
простить.
	Возьмем набор символов
			АБВАБВЯЯЯЯЯЯ
В нем дважды встречается сочетание АБВ , поэтому его можно запасти в
так называемом словаре, а в исходном тексте только оставить ссылочку на
словарь. Тогда исходный текст можно преобразовать, например, в
			11ЯЯЯЯЯЯ
и отдельно запомнить, что за символом 1 на самом деле скрывается
троица АБВ . Ясно, что если в тексте сочетание АБВ встретилось не 2,
а 100 или еще лучше 1000 раз, то сжатие было бы весьма ощутимым.
Однако в рельных ситуациях на такое везение рассчитывать не следует.
Надо все выжимать даже из немногих повторений в исходном тексте.
	Посмотрим, много ли мы выгадали в рассмотренном примере.
Текст ужался на 4 символа, но и, как минимум, 4 символа оказалось
в словаре. Кроме того, построение словаря потребует введения
разделителей и пр.
	Но и это еще не все. А если в тексте уже есть символы 1 ?
Как понять, что это именно 1, а не ссылка на словарь? В общем
случае мы вообще не можем рассчитывать, что какие-то символы
останутся незадействованными в тексте и их можно будет использовать
в качестве ссылок.
	Забегая вперед, скажем, что при грамотном подходе даже одно
повторение двухсимвольного сочетания может быть использовано для
сжатия текста.
	Как же поступить наиболее грамотно? Вот тут ответ далеко
неоднозначен. Он и не может быть однозначен, потому что сжатие - это
не таблица умножения. Один текст лучше сжимается одним методом,
другой - совершенно другим способом. Для начала мы рассмотрим очень
упрощенный вариант, чтобы было от чего отталкиваться в дальнейшем.
	Для определенности будем полагать, что каждый символ в тексте
- это упорядоченный набор из 8 битов, т.е. байт, или, что то же самое,
целое число от 0 до 255. (Иногда бывает полезнее разбить текст на
цепочки битов иной, даже переменной, длины, но это уже отдельный
вопрос.)
	Последовательно читаем исходный текст и одновременно формируем
выходной файл. Если очередная буква встретилась впервые, либо она
оказалась последней в тексте, то на выход посылаем бит 1 и 8 битов
от самой этой буквы. Точно так же надо поступить, если символ не нов,
но в паре со следующим еще не встречался. Так что в нашем примере
первые три символа дадут на выходе 27 битов. Тогда при обратной
операции как только расшифровщик увидел очередной бит 1, он сразу
будет знать, следующие за ним 8 битов надо вывести, так сказать,
открытым текстом.
	Если очередной символ в паре со следующим за ним уже встречался,
то в принципе от этой пары можно вывести два бита 01 и указание на
существующую аналогичную пару. Тогда декодировщик, увидев 01, по
этому указанию посмотрит на уже расшифрованную часть текста, возьмет
нужную пару и припишет точно такую же в конец расшифрованной части.
	Но как оформить это указание? Если указание - это адрес в
тексте, то оно (16 битов при не самом большом тексте в 64 КБ) может
оказаться слишком громоздким и не даст никакого сжатия для
двухсимвольных сочетаний. Конечно, можно было бы вообще забросить
возню с повторяющимися парами, но специфика реальных текстов любого
происхождения такова, что именно двухсимвольные повторения встречаются
намного чаще трехсимвольных и прочих, и именно от них в итоге получается
один из крупнейших вкладов в сжатие.
	Можно ограничить адреса, скажем, десятью битами, но тогда мы
сможем делать ссылки только на первый килобайт исходного текста.
	Намного лучше вместо абсолютного адреса указывать относительный,
точнее, расстояние от заполняемого фрагмента до точно такого же,
встречавшегося ранее. Тогда ссылки всегда будут на ближайший участок
исходного текста. Никакой логикой невозможно доказать, что относительная
адресация лучше. Но такова практика: если уж начал кто-то о чем-то
говорить, то непременно повторяет одно и то же по многу раз без связи
с тем, с чего он начал выступление. Точно так же дело обстоит с
программами, базами данных и т.д.
	В нашем примере можно обыграть малую длину текста и от второй
пары АБ можно было бы пустить на выход два бита 01 и двубитовое число 3,
т.е. всего 4 бита: 01 11. Число 3 означает, что аналогичную пару надо
искать на 3 позиции левее. Но в таком случае очередной символ В
пришлось бы выдавать открытым текстом, и с учетом однобитового признака
он потянул бы на 9 битов.
	Гораздо лучше будет, если мы сразу заметим, что ранее в тексте
встречалась целая тройка символов АБВ. Тогда на выход подадим три бита
001 (это будет отличительный признак троек) и указание на ранее
встречавшуюся такую же троицу. Теперь выгода получится даже при
использовании двубайтовых адресов. Однако выгода выгоде рознь. Далеко не
всегда нужны здесь длинные ссылки, и как поступить здесь рациональнее
- это вопрос, который позже будет рассмотрен.
	Пока же в нашем примере достаточно двубитовых ссылок. Так что
на выход пошлем: 001 11.
	Далее от буквы Я по известным правилам пойдет 9 битов. Остаток
текста шифруется семью битами:
				00001 01
Первая группа из нулей, оканчивающаяся единичкой, означает, что
ранее в тексте уже была аналогичная пятерка символов. Вторая группа
представляет число единицу, указывающее, на каком расстоянии надо искать
прототип. Пусть вас не смущает, что при дешифровке этот прототип еще
не существует, точнее, не выведен, так сказать, целиком. На самом деле
никакого противоречия здесь нет. Прототип будет достраиваться по ходу
строительства копии с него, но опережающими темпами, достаточными
для того, чтобы копирование не простаивало.
	Таким образом, исходный текст в сжатом виде при несколько
вольном изображении предстанет в виде:
		1 А 1 Б 1 В 001 11 00001 01
Правильнее (но менее наглядно) было бы вписать вместо А, Б и В их
восьмибитовые представления.

        

		      Рис.  Дерево Лемпеля-Зива

	Заметим, что отдельный словарь нам не понадобился. Его роль
играет сам исходный текст, вернее та часть, которая уже подверглась
шифровке (а при обратной операции, восстановлении, уже получена в
результате дешифровки).
	Чтобы программа расшифровки годилась не только для
рассмотренного примера, еще к сжатому тексту надо приложить некоторые
параметры: длину сжатого или развернутого текста, а также длину ссылок.
Само дерево прикладывать не надо, если оно подчиняется простым широко
употребительным правилам.
	В рассмотренном примере правило простое: длина группы нулей с
единичкой равна количеству перемещаемых символов. Но уже здесь видно,
что одним простым правилом не обойтись. Так, у нас оказались не
задействованы сочетания: 01, 0001, 000001 и т.д., т.е. мы израсходовали
битов значительно больше, чем необходимо для идентификации возникших
ситуаций. Повторяющуюся тройку можно было обозначить через 01, а
пятерку - через 001 (а можно и через 00), но тогда пришлось бы
хранить таблицу соответствия, в которой каждому количеству перемещаемых
символов ставился некий битовый код.
	Кстати, совершенно не обязательно малым количествам символов
приписывать короткие коды. Дело здесь не в длине повторяющихся
фрагментов текста, а в том, насколько много таких фрагментов. Если
одиночных символов мало или вовсе нет, то им можно присвоить длинный
код. А если все завалено, например, повторяющимися четверками, то им
надо дать самый короткий код из одного бита.
	Тем не менее, выбранная в примере кодировка ситуаций далеко
не случайна. Разбор текстов самого разного происхождения показывает,
что одиночные символы составляют примерно половину ситуаций, пары -
одну четверть, тройки - одну восьмую и т.д. Поскольку мы все равно
вынуждены делать кодировку только целым количеством битов, то даже
при заметном нарушении указанных пропорций обычно не удается увильнуть
от стандарта: N символов - N битов.
	Но это правило хорошо в меру. При формировании текстов кроме
чисто статистических закономерностей есть нюансы, привносимые таким
странным существом как человек, который почему-то любит большие
куски текста дублировать в том же тексте, или шлепать подряд пробелы
и нули сотнями. Согласно теории вероятности совпадение 100 символов
является практически невозможным событием, но именно практика
говорит об обратном. Обозначать такие повторы сотней подряд идущих
нулей - не менее странно и нерационально. Поэтому надо договориться,
что с некоторого момента длина фрагмента указывается не количеством
подряд идущих нулей, а обычным числом (одно- или двубайтовым).
	Так что дерево Лемпеля-Зива может быть достаточно сложным
и развесистым. Причем мы еще не упомянули всех направлений его
развития, необходимых для разработки мощного алгоритма сжатия.

		    2. Оптимален ли Лемпель-Зив?

	Поскольку никакого четкого однозначного алгоритма в данном
случае не существует, и метод широко открыт для всевозможных
вариаций, то правильнее было бы поставить вопрос так: а есть ли
вообще оптимальное архивирование? 
	Если задача архивирования ставится только о компактном
однозначном представлении текста, то она решается просто: надо
отправить тест в Internet или в свои запасники или переписать на
бумагу, а себе на диске оставить только адресок.
	На ум приходят соображения об открытых и закрытых системах.
Но где сейчас найдешь закрытую систему?
	Исходный и сжатый тексты не будут иметь никакой связи, если
между ними не появится третье лицо: расшифровщик. Это лицо можно
мыслить в виде профессора в очках, можно в виде циркуляров и пачки
таблиц, но для содержательного формализованного анализа в качестве
расшифровщика годится только программа на вычислительной технике,
т.е. третий текст.
	Поэтому, строго говоря, степень сжатия надо оценивать по
сумме: сжатый текст плюс дешифровщик. Что толку от сжатия файла
с 10 КБ до 1 КБ, если при этом вам понадобится тащить архиватор в
100 КБ ?
	Но эта оценка однобока. Допустим, на своей персоналке вы сжали
1000 подобных файлов тем же архиватором. Эффект налицо. Что же тогда:
объем архиватора и дешифровщика не имеет значения? Нет. Если не
ограничить его объем, то формально в него можно записать множество
ходовых текстов. Но даже при ограничениях для ряда специальных текстов
можно организовать представления всего лишь несколькими битами, вплоть
до одного бита.
	Таким образом, задача архивации вообще не может быть поставлена
строго математически. В ней можно выделить формальные показатели:
степень сжатия, объемы архиватора и дешифровщика, а также скорость
их работы. Но все они, если так можно выразиться, не достаточно
показательны.
	Кроме того, для любого архиватора нетрудно подобрать примеры,
на которых он не дает никакого сжатия. Говоря словами математика, всегда
найдется опровергающий пример. Но в данном случае это не исключает
архивирование из широкой практики.
	Мощные архиваторы сначала как-то оценивают заданный текст и
выбирают наиболее перспективные из множества заложенных в них методов.
Но окончательный выбор обычно удается сделать только после длинных
расчетов, эквивалентных разным типам сжатия. Об определенном оптимуме
и вовсе говорить не приходится. Это видно по разнобою в степени
сжатия для разных архиваторов. И все же привлечение широкого диапазона
разных подходов делает архиваторы достаточно эффективными.

	Возвращаясь к Лемпелю и Зиву, отметим, что наряду с общими
проблемами архивирования рассматриваемый метод привносит и массу
своих собственных. Как мы увидим, он допускает множество вариаций,
и каждая из них лучше работает в одних случаях, хуже в других. И
таким образом в миниатюре повторяется неопределенность выбора.
	Кроме того, здесь нет надобности бороться за чистоту метода.
Поэтому в реальных архиваторах метод встречается с такими наворотами,
в которых начальную идею трудно разыскать. Да и есть ли вообще эта
идея в чистом виде?

			   3. Дешифровщик

	Хотя согласно причинно-следственным связям шифрование должно
предшествовать дешифровке, но именно дешифровщик наиболее полно и
концентрированно отражает структуру сжатого текста. По этой структуре
уже нетрудно догадаться, как в принципе должен работать архиватор.
	Далее приводится алгоритм дезархивации со всеми необходимыми
техническими подробностями и тщательно подобранными значениями
параметров. Дело в том, что даже очень небольшие вариации параметров
резко меняют степень сжатия и, как правило, в худшую сторону. А борьба
ведь ведется за доли процента. Задача осложняется тем, что нет
объективных критериев, по которым можно было сразу сказать, что то
или иное изменение алгоритма пошло ему на пользу. Как мы знаем, для
любого архиватора найдется уйма текстов, вообще не поддающихся сжатию.
Если вы будете брать только такие тексты, то работу можно не начинать.
Оценивать архиватор надо по ходовым текстам, но ходовые - это не научное
понятие (как, строго говоря, и архивация вообще).

	1. Читается очередная серия битов до первого единичного
бита. Пусть N - количество считанных битов. Например, если на
очереди 001000... , то считываются 3 бита и соответственно N=3.
А если первый же бит равен единице, то считывается только он, и
N=1. Вводим число M для формирования количества символов, которые
позже будут взяты из уже расшифрованного текста. Поначалу M=N.
Числа M и N - целые двубайтовые.
	2. Если N больше или равно 17 , то считываются очередные
8 битов и помещаются в младшие биты числа M.
	3. Если N > 17 , то считываются очередные 8 битов и
помещаются в старший байт числа M. (Оно считается беззнаковым.)
	4. Если M=1, то считываются очередные 8 битов и посылаются
на выход, т.е. в восстановленный текст, и тогда переход на п.1.
	5. Считываются очередные 2 бита, по которым формируется
целое число Z от 0 до 3. Вводим K и R.
		Если M=2, Z=0, то K=5 , R=0.
		Если M=2, Z=1, то K=7 , R=-32.
		Если M=2, Z=2, то K=9 , R=-160.
		Если M=2, Z=3, то K=11 , R=-672.
		Если M>2, Z=0, то K=6 , R=0.
		Если M>2, Z=1, то K=9 , R=-64.
		Если M>2, Z=2, то K=12 , R=-576.
		Если M>2, Z=3, то K=14 , R=-4672.
	6. Считываются очередные K битов и помещаются в младшие K
битов вспомогательного целого двубайтового числа S. Остальные биты
этого числа заполняются единицами. Так что S<0, поскольку в старшем
бите, отвечающем за знак, находится единица.
	7. Определяется адрес в выпускаемом тексте, откуда будет взят
нужный фрагмент. Адрес - это попросту номер байта в последовательном
их расположении. Для этого к адресу, на котором пока закончено
формирование расшифрованного текста, надо прибавить R и S.
С полученного таким образом адреса берем M символов и добавляемом в
конец формируемого текста. Переход на п.1 (если данные не исчерпаны).

	Следующая реализация алгоритма предназначена для
самораспаковывающихся COM-программ. Поэтому первый десяток команд
в основном служит для перемещения программы в конец сегмента кодов.
А уже оттуда расшифрованные операторы складируются в начало этого
сегмента. Поэтому первый встречающийся в листинге jmp , да еще
представленный через db, передает управление именно на тот
оператор, который следует за ним в листинге (но после rep movsb
оказывается в другом месте памяти). Нельзя написать jmp с обычной
ссылкой на метку, поскольку код программы (а точнее, расположение ее
фрагментов) формируется в процессе ее выполнения. Необходимо отметить,
что первые 16 байтов дешифровщика (кончая jmp) находятся в начале
сжатого файла, а все остальное - в конце. Поэтому перемещение в сегменте
кодов не затирает этого начала даже вблизи предельных объемов файлов, и
передача управления корректна.

	mov dl,1	; Счетчик чтения битов в байте
	mov di,-64	; Адрес переноса программы в конец сегмента
	mov si,256	; Стандартный адрес размещения программы
	mov cx,si	; Количество перемещаемых байтов
	std		; Направление: с конца
	rep movsb	; Перемещение программы
	db 233,61,254	; jmp  Согласование регистра команд IP
	cld		; Чистка флага направления
	lea bx,[di+272]	; bx=di+272 = адрес сжатого текста
	mov di,256	; Адрес вывода
	push di		; Запоминание начального адреса вывода
	mov bp,-98	; Установка bp на подпрограмму PP
C1:	inc cx		; Подсчет количества нулей
	call bp		; Чтение очередного бита
	jae C1		; Возврат при бите 0
	db 214		; setalc, al=-1
	cbw		; ax=-1
	cmp cx,17	; Сравнение количества нулей с 17
	jb M2		; Если меньше, то переход на M2	
	pushf		; Сохранение регистра флагов
	mov cl,[bx]	; Чтение очередного байта в cl
	inc bx		; Корректировка адреса чтения
	popf		; Восстановление регистра флагов
	je M2		; Если количество нулей = 17, то переход на M2
	mov ch,[bx]	; Чтение очередного байта в ch
	inc bx		; Корректировка адреса чтения
M2:	push cx		; Сохранение cx (т.е. количества нулей)
	mov si,bx	; si = текущему адресу чтения
	inc bx		; Корректировка адреса чтения
	dec cx		; cx-1
	je M9		; На перенос одиночного символа
	dec bx		; Возврат адреса чтения
	dec cx		; cx-1
	setne cl	; Если cx не 0, то cl=1
	mov ch,0	; ch=0
	call bp		; Чтение очередного бита
	rcl cx,1	; Занесение очередного бита в младший разряд cx
	call bp		; Чтение очередного бита
	rcl cx,1	; Занесение бита сдвигом в cx
	imul si,cx,3	; si=cx*3 Определение адреса в табл.расстояний
	mov cl,[bp+si+10]	; Кол-во битов в расстоянии
C3:	call bp		; Чтение очередного бита расстояния
	rcl ax,1	; Занесение бита в ax
	loop C3		; Конец чтения расстояния
	add ax,[bp+si+11]	; ax= точка отсчета
	xchg ax,si	: si=ax
	add si,di	; si = абсолютный адрес фрагмента текста
M9:	pop cx		; Восстановление количества нулей
	rep movsb	; Перенос фрагмента текста
	cmp bx,bp	; Проверка на исчерпание сжатого текста
	jb C1		; На продолжение
PP:	ror dl,1	; На эту п/п указывает bp
	jae N
	mov dh,[bx]	; Чтение очередного байта
	inc bx		; Корректировка адреса чтения
N:	shr dh,1	; Занесение очередного бита в флаг CF
	ret		; Возврат на адрес 256
 db 5,0,0,7,-32,-1,9,-160,-1,11,-160,-3, 6,0,0,9,-64,-1,12,-64,-3,14,-64,-19
; Таблица расстояний

	То же самое для контроля в кодах (всего 131 байт):
178,1, 191,192,255, 190,0,1, 139,206, 253, 243,164, 233,61,254,
252, 141,157,16,1, 191,0,1, 87, 189,158,255, 65, 255,213,
115,251, 214,152, 131,249,17, 114,10, 156, 138,15, 67,157, 116,3,
138,47, 67,81, 139,243, 67,73, 116,33, 75,73, 15,149,193, 181,0,
255,213, 209,209, 255,213, 209,209, 107,241,3, 138,74,10,
255,213, 209,208, 226,250, 3,66,11, 150, 3,247, 89, 243,164,
59,221, 114,187, 208,202, 115,3, 138,55, 67, 208,238,
195, 5,0,0, 7,224,255, 9,96,255, 11,96,253, 6,0,0, 9,192,255,
12,192,253, 14,192,237.
	Можете посмотреть коды в шестнадцатиричной системе.
	Дешифровщик не сохраняет начальных значений регистров
общего назначения. Поэтому для охвата программ, использующих эти
значения, подпрограмма будет, конечно, чуть длиннее.

		  4. Варианты усовершенствования

	Приведенные выше детали алгоритма и значения параметров не
могут быть выведены какими-либо рациональными строгими методами.
В какой-то мере в них отражены особенности современного
программирования и человеческого языка. Но авторы каждого
архиватора находят свои оптимумы, и что лучше - может подсказать
только практика (критерий всеобщий, но несколько расплывчатый).
	Нетрудно подсчитать, что описанный дезархиватор заглядывает
назад в выпускаемом тексте не далее, чем на 16383+4672 байтов.
Маловато. Некоторые глядят дальше, вплоть до самого начала. Чтобы
расширить горизонт, достаточно исправить последнюю строку в п.5.
Тогда лучше будут обрабатываться файлы, в которых одинаковые
фрагменты очень удалены друг от друга. Но сразу пострадает гораздо
большее множество ходовых файлов, так как 15 или 16 битов будут
использоваться там, где хватило бы 14.
	Мощные архиваторы обычно делают предварительную оценку
исходного файла и к каждому файлу (или к большим частям одного
файла) осуществляют индивидуальный подход. Например, перед каждым
большим фрагментом сжатого кода указывается его объем и тип сжатия,
для этого достаточно 3 байтов, которые не портят общего качества
компрессии.
	Если файл короткий, значит, вообще дезархиватору не
понадобится заглядывать далеко назад, тогда не нужен, скажем,
случай K=14, и освободившиеся биты можно использовать с большей
пользой. Однако эффект сравнительно невелик. А поскольку он
проявляется только на малых файлах, то на общих (обычно гигантских)
объемах информации он и вовсе теряется.
	В исходных текстах (особенно в загрузочных модулях) немалую
долю составляют одиночные символы, не вошедшие в повторяющиеся
группы символов. Но частота таких символов различна. На основе
частот по методу Хаффмана символам можно дать новые представления.
Это позволяет уменьшить сжатый файл дополнительно на 2% (но не для
слишком малых файлов, где начинает перевешивать таблица соответствия,
которая сама может быть ужата до 64 байтов). Правда, архиватор
и дешифровщик при этом удваиваются в объеме.
	В представленном варианте наиболее коротким признаком (один
бит) наделен перенос байта один к одному. Далее длина признаков
увеличивается по мере роста цепочек и увеличения расстояний между
совпадающими фрагментами. Т.е. по сути имеется азбука Морзе для
набора выделенных случаев. В конкретном файле подобная монотонность
есть не всегда. Скажем, четырехбайтовых совпадений оказалось хоть пруд
пруди, а в точности трехбайтовых - кот наплакал. Поэтому аналогично
идеям азбуки Морзе, надо оптимизировать преставление цепочками нулей
и единиц, только представляться ими будут не символы и не фрагменты
текста, а ситуации архивирования. Такой архиватор, конечно, сжимает
лучше, но не настолько, чтобы, например, его использовать для
архивации COM-файлов, где эффект от собственно сжатия (сжатый текст
удается уменьшить еще на 1%) почти полностью съедается дополнительной
таблицей соответствия.
	Возможны многие другие варианты усовершенствований, не
связанных напрямую с характерными для Лемпеля-Зива идеями.
	Важен случай, когда численная информация набита цифрами.
Например: 132, -44.8, 555. Понятно, что цифры могут быть так
перетасованы, что даже одинаковые пары будут крайне редки. Упомянутые
методы не дают сжатия. Однако, если во фрагменте текста используются
всего 16 разных знаков, то каждый из них представляется четырьмя битами.
А это уже двукратное сжатие! Дополнительные резервы могут быть вскрыты,
если текст - на русском языке и используется не более 64 знаков.
	Можно выделять в исходном файле несжимаемые участки. Тогда
убыток от каждого из них можно снизить до 3 байтов. А в представленном
варианте каждый перенесенный без изменений символ тянет за собой
однобитовый признак, т.е. убыток 12.5%!
	Однако изложенный выше алгоритм не учитывает такие детали,
потому что они относительно редки, а эффект от них скромен. А так же
потому, что разных усовершенствований можно придумать тысячи, и здесь
не ставится задача их коллекционировать.

			5. Ускорение архивации

	При знании описанного выше дешифровщика алгоритм архивации
был бы почти тривиален, если бы не одно НО...
	Расшифровка производится практически мгновенно, и время
требуется только на перемещение файлов. (Тем не менее, некоторые
разработчики заметно усложняют алгоритм для малозаметного ускорения
дешифровки.) Другое дело с архивацией. Если здесь специально не
озаботиться, то она будет работать безобразно долго.
Неудовлетворительно даже на самых мощных ЭВМ.
	Прикинем, во что выльется поиск цепочки из десятка символов в
уже обработанной части текста. Если в тексте N байтов, то в среднем
придется сделать N/2 сравнений. Ограничиваясь порядком, просто N.
Причем каждое сравнение касается не одного байта, и может увеличить
объем еще на порядок-другой. И так надо пройтись по всему файлу.
Т.е. количество операций гораздо более, чем N*N. Для файла из
тысячи килобайтов это уже триллионы операций и часы работы ЭВМ.

	Сначала мы рассмотрим упрощенный вариант ускорения, который
повышает скорость примерно на 2 порядка (100 раз). А потом ускорим его
еще на 2 порядка.	
	Введем 256 массивов (многовато! но в основном варианте мы от
этого избавимся) по количеству возможных символов. Еще придется ввести
показатели заполнения массивов. Изначально показатели равны нулю.
	При чтении очередного символа S из исходного текста
в соответствующий массив заносится адрес, по которому считан S. Тогда
для поиска фрагмента схожего с текущим не придется перебирать каждый
символ прочитанного текста. По первому символу текущего фрагмента у нас
готов массив с адресами всех мест, представляющих интерес. А таких мест
в среднем в 256 раз меньше, нежели бы мы перебирали исходный текст
напропалую. Чтение соответствующего массива лучше начать с конца (с
последнего заполнения), но это уже менее значительные детали...
	Достигнутого ускорения недостаточно. Секунды, а то и минуты на
один файл - не годится, когда время - деньги.
	Следующий логический этап: запасать список адресов для каждой
пары символов. Но тогда понадобится 65536 массивов (технически это можно
оформить в виде двумерного массива). В каждом из них в принципе может
оказаться информация, сравнимая по объему с исходным текстом. Тут,
пожалуй, никакой памяти не хватит. В подобных случаях используют
динамическое распределение памяти, т.е. попросту говоря, без конца
перетасовывают данные в одном большом массиве. Очень хлопотное занятие...
	Но конкретные особенности задачи позволяют решить проблему
достаточно культурно. Первый массив заполняется пропорционально и
одновременно с чтением исходного текста. А устроен он следующим образом.
Каждый его элемент - это некий адрес в исходном тексте (а ввиду указанной
пропорциональности одновременно и адрес в 1-м массиве с точностью до
простейшего преобразования). Если по этому адресу мы заглянем в исходный
текст, то обнаружим в тексте некую пару символов XY. А теперь по тому же
адресу (с учетом преобразования) заглянем в 1-й массив. Там обнаружим
новый адрес, и если теперь по нему глянуть в текст, то там окажется в
точности та же пара XY.
	Таким образом, ухватившись за конец этой цепочки, мы легко
выйдем на все места исходного текста, где встречается пара XY. Осталось
разобраться с концами цепочек. Для этого вводится второй массив,
в котором 65536 элементов. Каждый элемент отвечает некоторой паре
символов. И упорядочены элементы по возрастанию номера первого символа,
а при равенстве - по возрастанию номера второго. Каждый такой элемент,
отвечающий некоторой паре символов XY, - это адрес в первом массиве,
с которого описанной выше процедурой можно перебрать все пары XY в
исходном тексте.
	Если очередной фрагмент начинается с XY, то моментально по
второму массиву определяется край нужной цепочки в 1-м массиве. И,
собственно, никакого перебора.
	После чтения в исходном тексте каждого символа смотрим также
на следующий. И для этой пары наращивается соответствующая цепочка и
одновременно 1-й массив. Корректируется и адрес ее конца во втором
массиве.
	Есть разные приемы которые позволяют сократить объемы массивов.
Например, если назад в исходном тексте надо смотреть не далее чем на N
символов, то в 1-м массиве достаточно иметь N адресов и заполнять массив
циклически. Т.е. если дошли до конца 1-го массива, то далее заполняем с
начала.

	В прилагаемом примере L.COM заложен метод ускорения, являющийся
вариацией описанного выше. Он занимает около половины объема программы.
	При запуске в командной строке надо указать имя исходного файла,
под тем же именем окажется и выходной файл (т.е. исходный удалится!).
	Здесь нет диагностики, подсказок, развитого сервиса, т.е. всего
того, что требует коммерческий продукт. Но все это можно добавить,
причем при небольшом увеличении объема программы. А не добавлено это
потому, что здесь цель - выделить центральный механизм. Обычно же,
приобретая программу, пользователь понятия не имеет, что в ней
существенно (микроскопическая часть), а что - упаковка.

                                                      Невесенко Н.В.
                                                  31 октября 2002 г.

                         © 2002 Suncloud.Ru