Главная Промышленная автоматика.

2. По данной цепочке-тексту х найти самую длинную повторяющуюся подцепочку в х.

3. По данным двум цепочкам хну найти самую длинную подцепочку, входящую как в х, так и в г/.

Определение. Позицией в цепочке длины п считается любое число от 1 до п. Говорят, что символ а входит в цепочку х в позиции i, если x=yaz и \y\=i-1. Говорят, что подцепочка и идентифицирует позицию i в цепочке х, если x=yuz, где \y\=i-1, и цепочку х можно представить в виде yuz только при у=у, т. е. в позиции i начинается единственное вхождение цепочки и в х. Например, подцепочка bba идентифицирует позицию 2 в цепочке abbabb. Подцепочка bb не идентифицирует позицию 2.

В оставшейся части этой главы положим x=aia2. . .а„ - цепочка в некотором алфавите / и а„+1=$/. Тогда каждая позиция i цепочки ;c$=fl!ia2. . .a„fl!n+i идентифицируется по крайней мере одной цепочкой, а именно aiOt+i. . .a„+i. Кратчайшая цепочка, иден-тифииирующая позицию i в х$, называется идентификатором (для) позиции i в X н обозначается через s{i).

Пример 9.16. Рассмотрим цепочку abbabb%. Идентификаторы позиций от 1 до 7 приведены на рис. 9.19. □

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

Определение. 1-деревом называют помеченное дерево Т, ребра которого, выходящие из любого внутреннего узла, помечены различными символами из /. Если ребро (w, w)T помечено символом а, то W называют а-сыном узла v.

Позиция

Идентификатор

abba

abbs

Рис. 9.19. Идентификаторы для abbabb$.



Деревом позиций (или позиционным деревом) (для) цепочки л:$= =«1. . .а„а„+1, где Ui б /, и a„+i=$, называют (/ и {$})-

дерево, для которого выполнены следующие условия.

1) Т имеет п+1 листьев, помеченных числами 1, 2, . . . , п+1. Листья дерева Т взаимно однозначно соответствуют позициям в х%.

2) Последовательность реберных меток, стоящих на пути из корня в лист с меткой t, служит идентификатором s (t) позиции t.

Пример 9.17. Позиционное дерево для цепочки abbabb$ изображено на рис. 9.20. Например, путь из корня в лист с меткой 2 помечен цепочкой bba, являющейся идентификатором позиции 2. □

Сформулируем некоторые основные свойства идентификаторов.

Лемма 9.3. Пусть s (i) - идентификатор позиции i цепочки х%=ага2. . Mn+i.

(а) Если s{i) имеет длину /, mo длина подцепочки s{i-1) не превосходит /+1.

(б) Никакой идентификатор не является собственным префиксом другого.

Доказательство, (а) Если длина подцепочки s{i-1) больше /+1, то найдется такая позиция кф1-1, что ai-iUt. . . . . .ai+j-i=a+.. . .flj+y. Поэтому «гй+х. . .ai+j-i=a+ia+2. . . . . .a+j, и aiUi+i. . .Oi+j-i не идентифицирует позицию i; получили противоречие.

(б) Легкое упражнение. □

Лемма 9.3(6) гарантирует, что для каждой цепочки х действительно существует позиционное дерево.


Рис. 9.20. Позиционное дерево.



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

Пример 9.18. Исследуем основную задачу идентификации образов: "Является ли уЬф. . .bp подцепочкой цепочки хайа. . . . . .а„?" Допустим, что мы уже построили для ;с5 позиционное дерево Т. Чтобы узнать, входит ли y=bib2. . .bp в х, рассмотрим его как граф переходов некоторого детерминированного конечного автомата. Иными словами, отправляясь из корня дерева 7, проследим максимально длинный возможный путь в позиционном дереве, которому приписана цепочка bib. . .bj для некоторого Otp. Пусть этот путь оканчивается в узле v. Возможны несколько случаев.

1. Если j<.p и г» не лист, то ответом будет "нет". В этом случае bibi. . .bj - подцепочка цепочки х, а bib,. . .bjbj+i нет.

2. Если /р и W - лист с меткой i, то Ьф,. . .bj совпадает с / символами цепочки х, начиная с позиции i. Тогда надо сравнить bj+ibj+2. . .bp с ai+jCi+j+t. . .ui+p-i. Если они не совпадают, то ответом будет "нет"; в противном случае "да", причем у входит в х, начиная с позиции /.

3. Если j=p и у не лист, то ответом будет "да". В этом случае у - подцепочка с двумя или более вхождениями в х. Начальные позиции этих вхождений - метки листьев, принадлежащих поддереву узла V позиционного дерева. □

Пример 9.19. С помощью позиционного дерева можно найти самую длинную повторяющуюся подцепочку данной цепочки х= =aifl!2- • -fln (два вхождения этой подцепочки могут перекрываться). Длиннейшая повторяющаяся подцепочка соответствует внутреннему узлу позиционного дерева с наибольшей глубиной. Такой узел можно обнаружить очевидным способом.

Рассмотрим нахождение длиннейшей повторяющейся подцепочки в abbabb. В позиционном дереве для abbabb$ (рис. 9.20) есть один внутренний узел глубины 3 и ни одного внутреннего узла большей глубины. Поэтому соответствующая этому узлу цепочка abb - самая длинная повторяющаяся подцепочка в abbabb. Узлы с метками 1 и 4 указывают, где начинаются два вхождения цепочки abb. В нашем случае они не перекрываются. □

Изучим подробно задачу построения позиционного дерева. В оставшейся части этой главы ;с$ будет цепочкой ai. . .a„a„+i, где On+i - единственный правый концевой маркер $. Через Xt,

будем обозначать суффикс aj. . .a„a„+i, а через Stij) - идентификатор позиции j в Xi. Все позиции нумеруются по исходной цепочке ai. . .а„а„+1.

Мы изложим алгоритм построения позиционного дерева для fli. . .a„+i за время, пропорциональное числу узлов окончательного





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 [125] 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0022