ГЛАВА 2. РАЗРАБОТКА ТЕОРЕТИЧЕСКИХ ОСНОВ АКСЕЛЕРАЦИИ ПРОЦЕССА СОПОСТАВЛЕНИЯ

В данном разделе проводится анализ конструктивных объектов и процессов сопоставления, предлагаются основанные на последовательном, конвейерном и параллельном принципах работы высокоскоростные способы и алгоритмы сопоставления, реализующие безотступную технологию поиска.

2.1. Конструктивные объекты. Основные понятия и определения

Определение конструктивного объекта неразрывно связано с конструктивным процессом, состоящим из последовательных элементарных конструктивных актов – шагов процесса, выполняемых (в рамках данной диссертационной работы) над конечной последовательностью элементарных знаков. В качестве шага конструктивного процесса может фигурировать не только добавление нового элементарного знака, но и уничтожения старого знака. Шаг может также состоять в сравнении каких-нибудь двух ранее осуществленных элементарных знаков на предмет установления их одинаковости или различия. Результатом такого шага может быть осуществление третьего элементарного знака в зависимости от того, одинаковы или различны два сравниваемых. Элементарные знаки, участвующие в такого рода процессе, будем называть буквами (символами, литерами) при условии, что существуют и определены алгоритмы установления равенства и различия знаков.

Определение 2.1. Алфавит зададим конечным набором букв в виде некоторого, специальным образом устроенного списка. Количество букв алфавита является его мощностью. Будем обозначать мощность алфавита А записью .

Определение 2.2. Два алфавита, состоящие из одних и тех же букв, будем называть равносоставленными.

Определение 2.3. Условимся считать, что алфавит Б является расширением алфавита А, если всякая буква А является также и буквой Б. Будем обозначать это записью .

Определение 2.4. Разностью алфавитов А и Б, которую будем обозначать посредством , является алфавит, состоящий из тех и только тех букв, которые являются буквами А и не являются буквами Б.

Определение 2.5. Объединением () алфавитов А и Б назовем алфавит, состоящий из тех и только тех букв, которые являются буквами хотя бы одного из алфавитов А и Б.

Определение 2.6. Связанные цепочки букв фиксированного алфавита будем называть словами в этом алфавите. В частности, пустая цепочка букв также является пустым словом.

Слово не содержащие букв заданного фиксированного алфавита называется пустым.

Определение 2.7. Под длиной слова будем понимать число букв, содержащихся в этом слове. Пустое слово имеет длину ноль.

Определение 2.8. Графически равными словами будем называть слова, составленные из одинаковых букв, одинаковым образом расположенных.

Определение 2.9. Если при сравнении двух слов, одно из них оказывается длиннее другого или при равной длине эти слова различаются на некоторых местах буквами, тогда имеет место графическое различие слов.

Определение 2.10. Операция соединения (конкатенация) слов P и Q в алфавите А состоит в «приписывании» справа к слову, графически равному P, слова, графически равного Q. Соединение слова P и пустого слова есть слово P.

Определение 2.11. Операция итерации слова P состоит в приписывании справа к слову P стольких слов P, какова заданная длина итерации. Будем обозначать итерацию длины i слова P записью {P}i.

Определение 2.12. Будем считать, что слово P больше слова R тогда, когда выполняется одно из условий:

а) P графически равно слову RQ1, где Q1 – непустое слово;

б) P графически равно слову Q2xQ3 и R графически равно слову Q2yQ4, где Q2, Q3, Q4 – произвольные слова, x и y – символы алфавита, причем, согласно линейной метрике алфавита, x предшествует y.

Определение 2.13. Слово P есть начало слова Q, если существует слово X такое, что Q графически равно PX; слово P есть конец слова Q, если существует слово X такое, что Q графически равно XP.

Определение 2.14. Будем говорить, что X есть собственное начало Y, если X – начало Y и X графически не равно Y. Будем говорить, что X есть собственный конец Y, если X – конец Y и X графически не равно Y.

Определение 2.15. Левым дополнением слова S условимся называть такое непустое слово L, что конкатенация L с собственным концом S графически равна S.

Определение 2.16. Правым дополнением слова S условимся называть такое непустое слово R, что конкатенация собственного начала S с R графически равна S.

Определение 2.17. Два непустых слова S и T пересекаются тогда и только тогда, когда верно одно из условий:

а) собственное начало S графически равно собственному концу T;

б) собственный конец S графически равен собственному началу T;

в) S входит в T;

г) T входит в S.

Определение 2.18. Слова P и Q будем называть взаимно простыми слева, если не существует непустого слова, являющегося началом как P, так и Q.

Определение 2.19. Слово P входит в слово Q, если существует пара слов такая, что R – первый элемент этой пары, S – второй и что Q графически равно RPS.

Определение 2.20. Слова вида R*P*S будем называть *-вхождениями, где R, P, S – слова в алфавите А, * – буква, не принадлежащая А.

Определение 2.21. Слово R называется левым крылом вхождения R*P*S, слово P – основой этого вхождения, слово S – правым крылом этого вхождения.

Определение 2.22. Вхождения с пустым левым крылом называется начальным вхождением, вхождение с пустым правым крылом – концевым вхождением.

Определение 2.23. Вхождения с основой P будем называть вхождениями слова P; вхождения R*P*S такие, что RPS графически равно Q, называются вхождениями в слово Q.

Определение 2.24. Вхождение X предшествует вхождению Y, если левое крыло X есть собственное начало левого крыла Y, при этом длину левого крыла вхождения X называют глубиной вхождения X.

Определение 2.25. Вхождение слова P в слово Q, предшествующее всякому другому вхождению P в Q, называют первым вхождением слова P в слово Q.

Определение 2.26. Последним вхождением слова P в слово Q называется такое вхождение K слова P в слово Q, что всякое другое вхождение P в Q предшествует K.

Определение 2.27. Слово P частично входит в слово S, если при графическом равенстве P и MT, M входит в S, а T не является началом правого крыла вхождения Q*M*R слова, графически равного S. При этом T – непустое слово.

Определение 2.28. Начальной позицией вхождения (частичного вхождения) P в слово S является позиция первой буквы этого вхождения (частичного вхождения) в слове S.

Определение 2.29. Под процессом сопоставления слов Q и P условимся понимать алгоритм, результатом которого является заключение об истинности графического равенства слов или истинности вхождения слова P в слово Q.

Определение 2.30. Продукцией или формулой подстановки назовем слова вида SwT, где S, T – произвольные слова в алфавите А, называемые соответственно вхождением (образцом, анцендентом) и подстановкой (модификатором, консеквентом), w – символ-разделитель образца и подстановки, принимающий значения из алфавита {, a}. Формула вида S T называется простой, S a T – заключительной. Простая формула подстановки называется сокращающей, если ее правая часть меньше длины ее левой части.

Определение 2.31. Продукция называется активной тогда, когда она обнаруживает вхождение своего образца в обрабатываемое слово.

Определение 2.32. Конечный упорядоченный список продукций (нормальный алгорифм) задает дискретный конструктивный процесс преобразования исходного входного слова в требуемое выходное. Каждый шаг процесса представляет собой регламентированную последовательность включения в работу продукций, производящих преобразование обрабатываемых слов в соответствии с каждой активной продукцией.

Работа продукции над словом P заключается в сопоставлении слова S и P с целью обнаружения вхождения S в P. При положительном исходе сопоставления (слово P читается слева направо), тот фрагмент слова, который графически равен S и расположен первым слева в слове P, заменяется словом T. В противном случае входное слово не изменяется. После срабатывания продукции, чтение обрабатываемого слова осуществляется с его начала (отступ в пространстве обрабатываемого слова).

Выполнение нормального алгорифма определяется следующими правилами передачи управления на упорядоченном множестве продукций:

1) первой включается в работу первая в списке продукция;

2) после срабатывания любой простой формулы подстановки, в работу включается первая в списке продукция (отступ в пространстве алгорифма);

3) при несрабатывании простой формулы подстановки осуществляется переход к следующей в списке продукции;

4) после срабатывания заключительной формулы подстановки или в случае несрабатывания последней продукции алгорифма, выполнение алгорифма завершается и выдается результат.

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

2.2. Исследование влияния структуры образца на скорость и корректность протекания процессов сопоставления

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

Рассмотрим два произвольных слова S и P в виде цепочек букв:

, (2.1)

, (2.2)

где , , A – конечный алфавит.

Пусть P – это образец, S – обрабатываемое слово, в котором требуется найти первое слева вхождение слова P.

Если исключить случай, когда длина m образца больше длины n обрабатываемого слова (при этом результат сопоставления очевидно ложен), то последовательный алгоритм поиска может быть таким:

1) указатель на текущую букву слова – i:=1, указатель на текущую букву образца – j:=1;

2) если i n и j m, тогда после выполнения условия равенства букв и осуществляется переход к сравнению следующих букв (i:=i+1, j:=j+1).

При неравенстве и побуквенное сопоставление слов начинается с первой буквы образца (j:=1) и текущей буквы слова.

3) алгоритм завершает работу с результатом «вхождение обнаружено» в позиции (i–j+1) слова S при истинности условия j > m или с результатом «вхождение не обнаружено» при выполнении условия i > n.

Представленный алгоритм поиска вхождений при своей очевидной простоте имеет наименьшую временную сложность O(n), но не всегда обнаруживает позиции вхождения.

Пусть для слов (2.1) и (2.2) обнаружено частичное вхождение образца P в позиции k слова S, т.е. выполняется графическое равенство подслов

и (2.3), t<m.

В соответствии с безотступной технологией поиска, подразумевающей в ситуации частичного вхождения поиск продолжать с текущей или следующей буквы обрабатываемого слова, мы условились начинать поиск с текущей (k+t) буквы слова и первой буквы образца. При таком подходе не учитывается возможность вхождения собственного начала слова (2.3) в себя самого, что может повлечь за собой пропуск позиции вхождения.

В литературе [74] приводятся способы и алгоритмы поиска, которые на основе анализа пересечений образца с образцом строят специальный числовой массив. При этом i-й элемент массива содержит позицию образца, с которой следует начинать новый этап поиска при возникновении частичного вхождения на i-й букве образца.

Для исключения возможных пропусков позиции вхождения в рассмотренный выше алгоритм можно внести изменение, заключающееся в том, что при любом частичном совпадении начала искомого вхождения с просматриваемым обрабатываемым словом поиск продолжать сопоставление «с отступом» с позиции буквы слова, следующей за началом частичного совпадения. При таком подходе временная сложность будет варьироваться от O(n), для длины искомого вхождения равной одному символу (в этом случае нет ни одного частичного совпадения), до O(m(n–m+2)), когда обрабатываемое слово состоит из одного и того же символа и полностью совпадает с первыми (m–1) символами искомого вхождения, а последний символ вхождения в позиции m – другой. Иллюстрацией сложности O(m(n–m+2)) может послужить пример:

обрабатываемое слово – ,

образец – .

Таким образом, анализ предельных алгоритмов поиска вхождений образца показывает, что, во-первых, структура образца влияет на корректность поиска и на некоторых образцах приводит к пропуску позиций вхождения, во-вторых, конфигурация образца определяет скорость протекания процессов сопоставления.

Рассмотрим более подробно классы образцов и исследуем их влияние скорость протекания процессов сопоставления.

Все образцы можно разбить на два больших класса – простые и сложные образцы.

Определение. Простым образцом является слово в некотором фиксированном алфавите, которое не имеет более одной позиции вхождения любого своего собственного начала.

Определение. Класс сложных образцов, составляют слова, получаемые из простых образцов применением к ним операций конкатенации и итерации.

Местоположение итерации в слове позволяет выделить следующие структуры сложных образцов:

1. {P}i – итерация слова;

2. {P}iR – итерация в начале слова;

3. R{P}i – итерация в конце слова;

4. R1{P}iR2 – итерация в середине слова;

5. {P1}iR{P2}j – итерация в начале и конце слова.

Общим для структур 1, 2, 5 является наличие начальной итерации образца. Рассмотрим начальную итерацию вида:

{a}i = (2.4)

В случае возникновения ситуации частичного вхождения k начальных букв итерации вида (2.4) и выполнения отступа, на следующем этапе поиска будет обнаружено еще одно частичное вхождение (k–1) начальных букв итерации, за которым вновь последует отступ. Процесс будет продолжаться до тех пор, пока длина частичного вхождения не станет равна 1. Временные затраты, связанные с многократными откатами и повторной обработкой символов, составят:

(2.5)

Если распространить подобные рассуждения на произвольную длину итерационного слова (будем эту длину называть глубиной итерации), то можно получить общую формулу для вычисления временных затрат:

, (2.6)

где d – глубина итерации {P}i, v - общее количество ситуаций отступа для позиции частичного вхождения k. Число отступов, приходящееся на итерацию, может быть вычислено по формуле v = .

Для фиксированной длины частичного вхождения количество повторно обрабатываемых символов уменьшается с ростом глубины итерации. Причиной этого является сокращение количества отступов в число раз, кратное глубине итерации. Например, при обнаружении частичного вхождения первых (2i–1) букв образца вида

{a}2i = (2.7)

будет выполнено 2(i–1) отступа, а при обнаружении частичного вхождения первых (2i–1) букв образца вида

{ac}i = (2.8)

будет осуществлено всего (i–1) отступа. По формуле (2.6) для образца (2.7) временные затраты составят , для образца (2.8) – . Очевидно, что .

Если при сопоставлении образцов со структурами 2, 5 частичное вхождение в слове будет обнаружено на этапе компарации букв слова R, то будет просмотрено дополнительное количество символов, определяемое формулой (2.6) для начальной итерации образца и выполнен однократный просмотр той начальной части R, вхождение которой было обнаружено в ситуации первого частичного вхождения. Например, при сопоставлении слова вида {a}ibx с образцом {a}ibd будет обнаружено вхождение начальной части образца {a}ib, за которым последует отступ. Сдвиг по обрабатываемому слову на одну позицию приведет к тому, что на следующих этапах поиска, в первую очередь, будет обнаружен ряд частичных вхождений начальной итерации образца – {a}i, а затем будет просмотрена оставшаяся часть слова – bx.

Время обработки образца со структурой 5, при возникновении частичного вхождения на этапе компарации конечной итерации – {P2}j, будет очевидно состоять из времени повторной обработки символов, связанного с обнаружением частичных вхождений начальной итерации, времени однократного просмотра слова R и времени однократного просмотра части конечной итерации (если P2 не пересекается с P1). При совпадении итерационных слов начальной и конечной итерации время обработки может возрасти из-за дополнительных частичных вхождений начальной итерации в конечной. Иллюстрацией этого может послужить, например, обработка образца {a}4bde{a}6 и слова {a}4bde{a}4xywq.

Поиск образцов со структурами 3, 4 не подвержен таким временным затратам, которые сопутствуют обработке слов с начальными итерациями. Частичное вхождение любой начальной части образца вида R{P}i или R1{P}iR2 при отсутствии вхождений собственного начала R в P приведет только к однократному просмотру участка обрабатываемого слова, на который придется частичное вхождение.

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

2.3. Разработка префиксно-суффиксного метода сопоставления

Как следует из анализа структур образцов наибольшую сложность представляет обработка образцов с начальной и конечной итерациями. Поэтому дальнейшие рассуждения будут связаны с повышением скорости поиска именно таких образцов.

Рассмотрим поэтапно процесс обработки слова S = {a}4c{a}4 и образца P = {a}3b{a}3 (см. таблица 2.1). Время поиска пропорционально числу компараций букв слов. Для представленного примера число компараций равно 22. Можно заметить, что время обработки станет минимальным, если в первую очередь выполнять поиск той части образца, которая наибольшим образом определяет цель поиска. Как видно на примере для P такой определяющей частью является подслово b.

Для того чтобы не подвергать образец предварительной обработке с целью выявления определяющего подслова, будем придерживаться следующей стратегии. При обнаружении ситуации частичного вхождения образца P в слово S, что означает вхождение некоторого начала слова P в S, будем продолжать поиск остатка образца со следующей буквы слова. Начальную часть образца, вхождение которой было обнаружено, назовем префиксом, а остаток образца – суффиксом. Когда будет найдено вхождение суффикса, останется проверить графическое равенство префикса и части слова, начинающейся с позиции, предшествующей позиции вхождения суффикса.

В процессе поиска могут также возникать ситуации частичного вхождения суффикса. В этом случае необходимо выполнить реконфигурацию префикса и суффикса и продолжить поиск.

Целесообразно во избежание потерь времени связанных с последовательным просмотром сначала суффикса, а затем префикса, при аппаратной поддержке данного метода сопоставления, обработку префикса и суффикса совместить во времени. Введем следующие обозначения:

РКПрф – результат компарации буквы префикса и буквы слова;

ПРКПрф – признак окончания обработки префикса;

РКСуф – результат компарации буквы суффикса и буквы слова;

ПРКСуф – признак окончания обработки суффикса;

АОС1 – указатель на букву обрабатываемого слова при поиске вхождения префикса;

АОС2 – указатель на букву обрабатываемого слова при поиске вхождения суффикса;

АПрф – указатель на букву префикса;

АСуф – указатель на букву суффикса.

При параллельной обработке префикса и суффикса будем придерживаться следующих правил:

1. Если ПРКПрф = 0, РКПрф = 1, ПРКСуф = 0, РКСуф = 1, тогда выполняется переход к компарации следующих букв префикса и суффикса, т.е.

АОС1 := АОС1–1, АПрф := АПрф – 1, АОС2 := АОС2 + 1, АСуф := АСуф + 1.

2. Если ПРКПрф = 1, ПРКСуф = 0, РКСуф = 1, тогда осуществляется компарация следующей буквы суффикса, т.е. АОС2 := АОС2 + 1, АСуф := АСуф + 1.

3. Если ПРКПрф = 0, РКПрф = 1, ПРКСуф = 1, тогда продолжается проверка вхождения префикса, т.е. АОС1 := АОС1 – 1, АПрф := АПрф – 1.

4. Ситуация, когда условия 1–3 ложны, означает обнаружение частичного вхождения суффикса или (и) неудачу, при проверке графического равенства префикса и части обрабатываемого слова. Необходимо выполнить реконфигурацию префикса и суффикса, которая при ПРКСуф = 1 состоит в том, что восстанавливается суффикс образца. Суффиксом становится правое дополнение текущего префикса образца. В выбранных обозначениях: АОС1 := АОС2, АОС2 := АОС2 + 1, АПрф := АСуф – 1. При ПРКСуф = 0, суффиксом становится правое дополнение текущего префикса образца – АОС2 := АОС1 + 2, АОС1 := АОС1 + 1, АСуф := АПрф + 1.

5. Вхождение обнаружено, когда истинно условие ПРКПрф = 1, ПРКСуф = 1.

В таблице 2.2 приводится пример работы префиксно-суффиксного метода сопоставления для рассмотренных выше слов S и P. Число компараций здесь равно 9. Это в 2 раза меньше, по сравнению с прямым метод поиска.

Таблица 2.1

Поиск вхождения образца {a}3b{a}3

в слово {a}4c{a}4 прямым способом

Этап	S
	a	a	a	a	c	a	a	a	a
1	a =	a =	a =	b
2		a =	a =	a =	b
3			a =	a =	a
4				a =	a
5					a
6						a =	a =	a =	b
7							a =	a =	a =

Таблица 2.2

Поиск вхождения образца {a}3b{a}3

в слово {a}4c{a}4 с учетом определяющего подслова образца

Этап	S
	a	a	a	a	c	a	a	a	a
1	a =	a =	a =	b
2				a =	b
3					a =	b
4						a =	b
5							a =	b
6								a =	b

2.4. Конвейеризация процесса сопоставления

Процесс поиска вхождений образца в обрабатываемое слово можно разбить на два этапа:

1-й этап – локализация в обрабатываемом слове таких фрагментов, в которых наиболее вероятно есть вхождение образца (этап прогнозирования, предсказания);

2-й этап – детальный анализ фрагментов обрабатываемого слова, которые были определены на 1-м этапе, с целью получения окончательного решения о позиции вхождения образца (этап доказательства, подтверждения).

Операционный блок, реализующий 1-й этап, назовем блоком прогнозирования, а операционный блок, реализующий 2-й этап, – блоком доказательства.

Для обеспечения высокой скорости обработки необходимо совместить во времени работу блоков прогнозирования и доказательства. Так, при обнаружении позиции вероятного вхождения, ее адрес сразу передается на блок доказательства. Одновременно с запуском процесса доказательства продолжается выполнение прогнозирования со следующей позиции обрабатываемого слова.

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

После того, как возможная позиция вхождения будет обнаружена, доказательство может быть выполнено обычным побуквенным сопоставлением образца и фрагмента обрабатываемого слова. При этом не имеют значения ситуации частичного вхождения и нет необходимости в выполнении отступа.

Рассмотрим различные способы вычисления компактной информации для входных слов. Обозначим входное слово через W, двоичный вектор, получаемый в результате преобразования слова W, через V.

Самый простой способ вычисления компонент двоичного вектора состоит в сравнении на больше (меньше, больше или равно, меньше или равно) кодов соседних букв в слове и записи результата отношения в соответствующую позицию вектора. При таком подходе длина двоичного вектора будет равна на единицу меньше, чем длина слова.

Первый способ преобразования

Каждая i-я компонента вектора V принимает значение «1», если выполняется одно из заранее определенных отношений код(Wi) код(Wi+1), где – оператор отношения. Если отношение не выполняется, то компонента принимает значение «0». Под операцией код(<буква>) подразумевается порядковый номер буквы в рабочем алфавите.

Вектор V, вычисляемый по такому правилу, будем называть двоичным вектором отношений 1-го рода.

Проиллюстрируем на примере слова-образца P = cbdd и обрабатываемого слова S = cbccbabcbccbddbabdaddc работу первого способа преобразования и алгоритм прогнозирования.

В качестве оператора отношения выберем оператор «больше или равно». Тогда после применения к слову P алгоритма вычисления вектора отношений 1го рода получим двоичный вектор A = {1,0,1}, после применения того же алгоритма к слову S – получим вектор B = {1,0,1,1,1,0,0,1,0,1,1,0,1,1,1,0,0,1,0,1,1}.

Прогнозирование состоит в сканировании двоичного массива B с целью поиска в нем двоичной цепочки A. В результате такого сканирования можно сделать четыре предположения о возможной позиции вхождения образца в обрабатываемое слово. Это позиции 1, 8, 11, 18.

Недостатком предыдущего способа вычисления компонент двоичного вектора является то, что при определенной структурной особенности образцов способ генерирует непрерывные цепочки нулей или единиц. Если при этом и обрабатываемый текст имеет ту же структурную особенность, что и образец, то поиск вхождений двоичного вектора образца в двоичном векторе слова приведет к предсказанию ряда позиций вхождений, которые накладываются друг на друга. Это может привести к снижению скорости поиска вхождений образца.

Структурная особенность слов, на которой способ чувствителен к генерации непрерывных последовательностей нулей и единиц, состоит в том, что коды букв в словах монотонно возрастают или убывают. Чтобы уменьшить влияние монотонного возрастания (убывания) кодов букв на процесс прогнозирования, дополнительно к вектору отношений 1-го рода введем генерацию еще одного вектора, компоненты которого принимают значения в зависимости от условия четности или нечетности кода буквы.

Второй способ преобразования

Компоненты вектора отношений V1 1-го рода вычисляются согласно первого способа преобразования. Каждая i-я компонента вектора четности V2 принимает значение «1», если код(Wi) – четный. В противном случае, компонента принимает значение «0».

Рассмотрим на примере поиска вхождений слова-образца P = abcde в обрабатываемом слове S = cdefgjjdfghgfdsfdsabcdekl существенное повышение точности прогнозирования второго способа преобразования по сравнению с первым.

Результатом преобразования слова P в двоичный вектор отношение 1-го рода является вектор A1 = {0,0,0,0}, результатом преобразования слова S – вектор A2 = {0,0,0,0,0,1,1,0,0,0,1,1,1,0,1,1,0,1,0,0,0,0,0,0}. Как можно заметить, оба вектора имеют в своем составе непрерывные цепочки нулей.

Прогнозирование возможных позиций вхождения на основе только двоичных векторов отношений 1-го рода дает пять предположений. Это позиции 1, 2, 19, 20, 21.

Построим вектор четности для P – B1 = {0,1,0,1,0}, для S – B2 = {0,1,0,1,0,1,1,1,1,0,1,0,1,1,0,1,1,0,0,1,0,1,0,0,1}. Совместное использование векторов отношений и четности сужает область поиска вхождений образца до двух возможных позиций – 1 и 19.

Выше было введено определение вектора отношений 1-го рода. Для уточнения прогнозирования можно также дополнительно использовать вектор отношений 2-го рода, 3-го рода и т.д.

Под вектором отношений 2-го рода будем понимать двоичный вектор, получаемый при применении следующего правила ко всем по порядку слева на право буквам слова W.

Третий способ преобразования

Пусть Wi и Wi+2 – i-я и (i+2)-я буквы слова W, тогда при выполнении отношения код(Wi) код(Wi+2), где – оператор отношения, i-я компонента вектора принимает значение «1», в противном случае – «0».

Количество компонент двоичного вектора отношений 2-го рода на два элемента меньше, чем количество букв в слове W.

Примером вычисления вектора отношений 2-го рода может служить вектор V2 = {0,1,0,0,1} для слова P = bcdakfd, где в качестве оператора отношения было выбрано отношение «больше или равно».

Следует отметить, что вычисление двоичного вектора отношений 2-го рода может не всегда приводить к повышению достоверности работы прогнозатора. Это связано с тем, что при определенном расположении кодов букв компоненты двоичного вектора отношений 2-го рода выводятся из компонент двоичного вектора отношений 1-го рода.

Рассмотрим произвольную последовательность из трех букв Ai Ai+1 Ai+2. Тогда i-я и (i+1)-я компоненты вектора отношений V1 1-го рода можно вычислить согласно следующей системе альтернативных условий:

если код(Ai) код(Ai+1), тогда V1i=1; (2.9)

если код(Ai) < код(Ai+1), тогда V1i=0; (2.10)

если код(Ai+1) код(Ai+2), тогда V1i+1=1; (2.11)

если код(Ai+1) < код(Ai+2), тогда V1i+1=0. (2.12)

При одновременном выполнении условий (2.9) и (2.11) нет необходимости в непосредственном сравнении кодов букв Ai и Ai+2, так как из выполнения неравенства код(Ai) код(Ai+1) код(Ai+2) следует, что код(Ai) код(Ai+2).

Аналогично, при одновременном выполнении условий (2.10) и (2.12) нет необходимости в непосредственном сравнении кодов букв Ai и Ai+2, так как из неравенства код(Ai) код(Ai+1) код(Ai+2) следует, что код(Ai) код(Ai+2).

Таким образом, если коды букв рассматриваемой триады будут удовлетворять парам условий (2.9, 2.11) или (2.10, 2.12), тогда вычисление компонент вектора отношений 2-го рода не приведет к сужению области поиска возможных вхождений.

Четвертый способ преобразования

В прогнозе участвует три вектора отношений: 1-го, 2-го и 3-го родов.

Под вектором отношений 3-го рода будем понимать двоичный вектор, получаемый при применении следующего правила ко всем по порядку слева на право буквам слова W.

Пусть Wi и Wi+3 – i-я и (i+3)-я буквы слова W, тогда при выполнении отношения код(Wi) код(Wi+3), где – оператор отношения, i-я компонента вектора принимает значение «1», в противном случае – «0».

Количество компонент двоичного вектора отношений 3-го рода на три элемента меньше, чем количество букв в слове W.

Пример вычисления вектора отношений 3-го рода: для слова P = bcdakfd искомый вектор V3 = {1,0,0,0}. В качестве оператора отношения было выбрано отношение «больше или равно».

Исследуем надежность следующих способов прогнозирования от длины образца:

1) прогнозирование на основе вычисления вектора отношений 1-го рода;

2) прогнозирование на основе вычисления вектора отношений 1-го рода и вектора четности;

3) прогнозирование на основе вычисления векторов 1-го и 2-го родов;

4) прогнозирование на основе вычисления векторов 1-го, 2-го и 3-го родов.

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

Условия машинного эксперимента выберем следующие:

мощность алфавита – 26;

объем обрабатываемого текста – 1024 символа;

в текст равномерно вставляется 100 образцов.

Текст, образцы и позиции вставок образцов генерируются по равномерному закону распределения.

Численные результаты эксперимента приведены в таблице 2.3. Графики зависимости надежности способа прогнозирования от длины образца изображены на рис. 2.1.

Как следует из машинного эксперимента первый способ прогнозирования имеет наименьшую надежность и достигает величины 0.95 при обработке образцов длины 10. Одновременное использование вектора отношений 1-го и 2-го родов снижает порог длины образца до 7 символов для величины надежности 0.95. Использование же вектора отношений 3-го рода не дает значительного повышения надежности, снижая порог длины образца до 6 символов. Наибольшую эффективность предсказания имеет алгоритм сочетающий вычисление вектора отношений 1-го рода с вычислением вектора четности. Величины надежности 0.95 он позволяет достичь при обработке образцов длины 5.

Таблица 2.3

Результат машинного эксперимента по исследованию надежности способов прогнозирования

№ способа	Длина образца, букв
	2	3	4	5	6	7	8	9	10	11	12	13
1	0,17	0,26	0,34	0,6	0,59	0,7	0,88	0,79	0,96	0,98	0,98	0,99
2	0,46	0,73	0,9	0,94	0,97	1	1	1	1	1	1	1
3	0,17	0,36	0,6	0,83	0,88	0,97	0,98	1	0,99	1	1	1
4	0,17	0,36	0,71	0,87	0,96	0,98	1	1	1	1	1	1

Рис. 2.1. Графики зависимости надежности способов

прогнозирования от длины образца

2.5. Алфавитный метод сопоставления

Рассмотрим два слова в виде цепочек букв:

S = и P = ,

в которых каждая буква принадлежит одному конечному алфавиту A. Пусть слово P (образец) является целью поиска позиции вхождения в слове S.

Обрабатываемому слову S можно поставить в соответствие алфавит Б (), из букв которого построено данное слово. Аналогично образцу P можно поставить в соответствие алфавит В ().

Применим для обнаружения позиции вхождения способ параллельной компарации букв образца P с соответствующими буквами фрагмента слова S. Обозначим фрагмент с позиции i слова S через Ci. Каждому такому фрагменту Ci можно поставить в соответствие свой алфавит Fi , так что объединение всех Fi будет давать Б, т.е. .

Условие, когда алфавиты образца и фрагмента обрабатываемого слова не являются равносоставленными, (т.е. ) имеет достаточное основание для вынесения решения о графическом неравенстве образца и рассматриваемого фрагмента и, следовательно, об отсутствии вхождения в позиции i обрабатываемого слова.

Например, рассмотрим два графически неравных слова P1 = bdebdd, которому соответствует алфавит W1 = {b, d, e}, и слово P2 = adebdd, которому соответствует алфавит W2 = {a, b, d, e}. Разность алфавитов W1 и W2 в результате не дает пустого множества, что подтверждает графическое различие слов.

И наоборот, условие равносоставленности В и Fi является необходимым, но еще не достаточным условием графического равенства образца и фрагмента обрабатываемого слова Ci.

Проиллюстрируем это на примере. Рассмотрим два равносоставленных алфавита W1 = W2 = {b, d, e}. С использованием букв этого алфавита можно составить как пару графически равных слов P1 = P2 = ddbbe, так и пару графически различных слов P1 = bde, P2 = dbe.

Теперь сформулируем сам алгоритм сопоставления. Сначала формируется алфавит образца. Затем обрабатываемое слово подвергается побуквенному сканированию, в процессе которого каждая буква слова контролируется на принадлежность к алфавиту образца. Позиция первого найденного вхождения буквы образца в обрабатываемом слове помечается как начало фрагмента, с которого возможно есть вхождение образца. Каждая следующая буква обнаруженного фрагмента также контролируется на принадлежность к алфавиту образца до тех пор, пока не будет локализован блок слова длиной, равной длине образца. После того, как равносоставленность алфавитов образца и фрагмента обрабатываемого слова будет установлена, одновременной компарацией букв образца с соответствующими буквами локализованного фрагмента устанавливается или опровергается факт наличия вхождения.

Если параллельная компарация дает отрицательный ответ на вопрос об обнаружении позиции вхождения, тогда окно, локализующее фрагмент обрабатываемого слова, сдвигается на один символ влево, тем самым захватывая новую букву, которая снова проходит обязательный контроль на принадлежность к алфавиту образца, и проверка графического равенства образца и нового фрагмента повторяется.

Любое нарушение равносоставленности алфавитов образца и фрагмента слова сопровождается сбросом границ окна локализации участка обрабатываемого слова и переходом к сканированию оставшейся части.

Чаще всего объем обрабатываемого слова составляет тысячи или миллионы символов, тогда как объем поискового образца не превышает десятков или сотен символов. Как следствие этого, мощность алфавита образца оказывается меньше мощности алфавита обрабатываемого слова и значительно меньше мощности алфавита, используемого для кодирования состояний при решении конкретной задачи. Такое соотношение мощностей алфавитов создает предпосылку для разработки такого способа хранения образца и просматриваемого фрагмента обрабатываемого слова, при котором обеспечивается минимум аппаратных затрат при реализации схем параллельного сравнения.

На сегодня известно два способа кодирования символьной информации. Это восьмиразрядное кодирование в стандарте ASCII и шестнадцатиразрядное в стандарте UNICODE. Таким образом, мощность алфавита обрабатываемого слова может быть 28 = 256 или 216 = 65536. Как показывает решение реальных задач, отдельные поисковые образцы строятся из небольшого числа различных символов – мощность алфавита не превышает 32 букв, т.е. 25. Так как при обнаружении вхождения в компарации участвуют только буквы из алфавита образца, то есть возможность хранить символы закодированными не 8-ю или 16-ю разрядами, а всего 5-ю; вместо 8-и или 16-и разрядных компараторов можно использовать 5-ти разрядные.

В общем случае, для выбранной фиксированной мощности алфавита образца, которую обозначим через N, потребуется разрядов для двоичного представления букв обрабатываемых слов.

2.6. Выводы

1. Широкое распространение продукционных систем возможно только тогда, когда имеются значимые для практики скоростные преимущества систем и процессоров символьной обработки по отношению к существующему парку ПЭВМ и многопроцессорных систем обработки информации. Основным источником непродуктивных затрат времени являются отступы как в пространстве обрабатываемого слова, так и в пространстве алгорифма. Вместе с тем основные затраты времени непосредственно связаны с процессом сопоставления образца с обрабатываемым словом.

2. Анализ процессов последовательного сопоставления с образцом показал, что наибольшие временные затраты связаны с обработкой начальных итераций образца. Кроме того, выявлена структурная особенность образца, которая приводит к пропускам позиций вхождения. Такой особенностью является наличие множественных вхождений собственного начала образца в себя самого.

3. Предложен новый суффиксно-префиксный последовательный метод сопоставления, который исключает возникновение пропусков позиций вхождения и минимизирует время обработки образцов с начальными итерациями. Разработан алгоритм параллельной обработки префикса и суффикса образца с целью создания устройства, поддерживающего выполнение операции сопоставления.

4. Разработан способ распараллеливания процесса сопоставления, состоящий во введении этапа предсказания позиции вхождения и этапа доказательства истинности вхождения, и на основе него разработан безотступный алгоритм сопоставления. Предложено несколько функций преобразования обрабатываемых слов в форму, удобную для выполнения прогнозирования вхождений и исследована зависимость надежности их предсказания от длины образца.

5. Разработан высокоскоростной алфавитный метод и алгоритм сопоставления с образцов, реализующие безотступную технологию поиска. Алфавитный способ сопоставления допускает эффективное кодирование букв обрабатываемых слов, что позволяет сократить аппаратные затраты при разработке устройства поиска, поддерживающего мультиразрядные данные.