Обработка цепочек элементов
Конструктор знает, что он достиг совершенства не тогда, когда нечего больше добавить, а тогда, когда нечего больше убрать.
Антуан де Сент-Экзюпери
Материал этой главы является дополнением к уроку 11 "Цепочечные команды" учебника. Из этого урока следуют выводы о том, что, во-первых, цепочечные команды являются мощным инструментом обработки последовательностей элементов размером 1/2/4 байт и, во-вторых, это единственное средство микропроцессора для обработки данных по схеме память-память.
В процессе разработки программ для учебника и этой книги мы достаточно часто использовали команды микропроцессора этой группы. Но цепочечные команды – это примитивы, и, как любые примитивы, они являются лишь основой для построения более сложных алгоритмов обработки цепочек элементов. Особенно это чувствуется при разработке программ для задач обработки текстов, и в частности задачи поиска.
Для решения этой проблемы существует ряд классических алгоритмов, оптимизирующих этот процесс. Ниже будет приведено несколько программ, демонстрирующих алгоритмы поиска данных в строках символов, то есть цепочках элементов размером 1 байт. Так как все они построены на основе стандартных байтовых цепочечных команд микропроцессора, то при необходимости обработки последовательностей элементов большей размерности (2 и 4 байта) их доработка не составит вам особого труда.
Организацию поиска одиночного символа в программе на ассемблере мы рассматривать не будем, так как это делается самими цепочечными командами без привлечения посторонней алгоритмической поддержки. Информацию об этом можно получить из учебника.
Более подробно мы рассмотрим организацию поиска текстовой подстроки в строке символов, превышающей размер искомой подстроки. При всей кажущейся простоте этого вида поиска его реализация в программах на языке ассемблера сопряжена с рядом проблем.
Введем некоторые обозначения:
- Р – строка-аргумент поиска, размерность строки Р – М байт, j – индекс символа в строке Р, 0 <j < М-1;
- S – строка, в которой ведется поиск строки Р, размерность строки S – N байт, i – индекс символа в строке S, 0 < i < N-1.
Все алгоритмы поиска в текстовой строке можно разбить на два класса: прямые и учитывающие особенности объектов поиска. Последний класс алгоритмов предполагает предварительный анализ искомой подстроки и формирование на его основе некоторой информации, управляющей процессом поиска.