Главная
страница 1
FAST WAY OF TWO-DIMENSIONS PATTERN
MATCHING TO ROW AND TO COLUMN

The fast way of two-dimensions pattern matching is considered, in which one the acceleration of scanning of a two-dimensions string is reached at the expense of preprocessing of a sample. The calculation of positions of shift of a sample allows to minimize time of scanning of a two-dimensions string in a horizontal and a vertical directions.


БЫСТРОЕ СОПОСТАВЛЕНИЕ С ДВУМЕРНЫМ
ОБРАЗЦОМ ПО СТРОКЕ И ПО СТОЛБЦУ

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

V = {, , …, }, где (i = ), обрабатываемое слово представим перечислением клеток прямоугольной матрицы

W = { , , …, ,

, , …, ,

….,


, , …, }, где (i = , j = ).

Клеткой будем называть пару , где символ является состоянием клетки, – именем клетки. Для образца (обрабатываемого слова) символ a – это буква, которая расположена в x-ом столбце y-й строке в прямоугольной системе координат.

Задача сопоставления образца V и слова W состоит в поиске двухкоординатных позиций вхождения V в слово W.

Будем называть буквы образца V, координаты которых равны, столбцом образца, буквы образца V, координаты которых равны, строкой.

Обозначим через m – максимальный индекс столбца образца, через n – максимальный индекс строки образца, количество букв образца в j-й строке через , количество букв образца в i-м столбце через , максимальный индекс буквы образца в j-й строке через , минимальный индекс в j-й строке через , максимальный индекс буквы образца в i-ом столбце через , минимальный индекс в i-м столбце через .

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

Первыми таким образом сравниваются символы и . Если они не совпадают и не встречается среди букв -й строки образца, то согласно этому способу образец сдвигается по горизонтали на позиций вправо. Следующими сравниваются и .

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

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

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

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

При формировании таблицы delta[j] вход для символа w равен , где – самое правое вхождение w в j-ю строку образца, и равен , если w не содержится в j-й строке образца, то есть:

delta[j][w] = min {v : v = или ( и = w)}

Таблица delta[j] для алфавита инициализируется следующим образом:


for j := 1 to n do

for w := 1 to

delta[j][w] :=
for j := 1 to n do

for i := to

delta[j][A(i, j)] := – i
Отсюда видно, что время инициализации n таблиц delta равно .

Проиллюстрируем работу одной таблицы delta для одномерного образца

x = ABCDB (m = 5 – длина образца).

w A B C D E F G H …

delta[w] 4 0 2 1 5 5 5 5 …

Несовпадение возникает при .

x – образец A B C D B

y – текст …L M N A B C D B …

i

Следующими сравниваются символы и , то есть .



образец A B C D B

текст …L M N A B C D B …

i i+4

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


i := m;

s := m;


tb := 0;

while ( (tb <= r - n) и (s <= p) ) {

while ( (s > 0) и (i > 0) и (s <= p) ) {

j := ;

t := tb + j;

// поиск вхождения i-го столбца образца

// в направлении снизу вверх

while ( (t > 0) и (j >= ) ) {

if (A(i, j) == B(s, t)) {

j := j – 1;

t := t – 1;

} else { // несовпадение

if (i - + delta[j][B(s, t)] <= 0) {

s := s + + 1 - i;

} else {

s := s + delta[j][B(s, t)];

}

i := m;


continue 2; // Продолжаем внешний цикл

}

}



// переход к поиску вхождения

// предыдущего столбца образца

i := i – 1;

s := s – 1;

}

if (i < 1) { // Проверка успешности сопоставления



// Область вхождения (s + 1, tb + 1)-(s + 1 + m, tb + 1 + n)

break;


}

// Переход к поиску вхождения образца относительно

// следующей строки обрабатываемого слова

i := m;


s := m;

tb := tb + 1;

}

Рис. 1. Алгоритм быстрого сопоставления с двумерным

образцом по строке

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

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

Прежде чем начать очередной этап сравнения образца с частью двумерного слова, который всегда состоит в сравнении букв A(m, ) и B(s+m,t+), номер столбца (s+m) слова, с которым первым будет сопоставлен m-й столбец образца, проверяется на наличие во временной памяти. При отсутствии номера столбца во временной памяти, переходят собственно к последовательному сравнению букв образца и части слова в известном порядке. Если номер столбца (s+m) найден во временной памяти, извлекается соответствующий ему номер строки двумерного слова, с которого следует начинать двумерное сопоставление, вычисленный в результате обнаружения отвергающего символа на предыдущем этапе поиска. Если этот номер больше текущего номера строки слова (t+), то процесс сравнения в столбце (s+m) не начинается, а переходят к следующей итерации в столбце слова (s+m+1).

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

Таким образом, общее время инициализации n+m сдвиговых таблиц равно .

На рис. 2 приведен алгоритм быстрого поиска по строке и по столбцу.
i := m;

s := m;


tb := 0;

bs := s;


while ( (tb <= r - n) и (s <= p) ) {

while ( (s > 0) и (i > 0) и (s <= p) ) {

j := ;

t := tb + j;

// тест на возможность пропуска

// сопоставления в этой области

if ( mem[bs] <= t ) {

// поиск вхождения i-го столбца образца

// в направлении снизу вверх

while ( (t > 0) и (j >= ) ) {

if (A(i, j) == B(s, t)) {

j := j – 1;

t := t – 1;

} else { // несовпадение

if (j - + delta2[i][B(s, t)] <= 0) {

mem[bs] := t + – j;

} else {

mem[bs] := t + delta2[i][B(s, t)];

}

if (i - + delta[j][B(s, t)] <= 0) {



s := + 1 - i;

} else {


s := s + delta[j][B(s, t)];

}

i := m;



bs := s;

continue 2; // Продолжаем внешний цикл

}

}

} else {



s := s + 1;

bs := s;


continue; // новая итерация

}

// переход к поиску вхождения



// предыдущего столбца образца

i := i – 1;

s := s – 1;

}

if (i < 1) { // Проверка успешности сопоставления



// Область вхождения (s + 1, tb + 1)-(s + 1 + m, tb + 1 + n)

break;


}

// Переход к поиску вхождения образца относительно

// следующей строки обрабатываемого слова

i := m;


s := m;

bs := s;


tb := tb + 1;

}

Рис. 2. Алгоритм быстрого сопоставления с двумерным

образцом по строке и по столбцу

В таблицах 1, 2 представлены численные результаты сравнения эффективности прямого подхода к сопоставлению с двумерным образцом, алгоритма быстрого поиска по строкам обрабатываемого слова и алгоритма быстрого поиска по строкам и по столбцам обрабатываемого слова. В машинном эксперименте № 1 решалась задача сопоставления обрабатываемого слова, состоящего из 1024 строк и 1024 столбцов, с квадратным двумерным образцом, состоящим из n строк и n столбцов, где n варьировалось от 1 до 10, в случае отсутствия вхождений образца. В машинном эксперименте № 2 решалась задача сопоставления обрабатываемого слова, состоящего из 1024 строк и 1024 столбцов, с прямоугольным двумерным образцом, состоящим из n строк и 4-х столбцов, где n варьировалось от 1 до 10, в случае отсутствия вхождений образца. Обрабатываемое слово и образец генерировались при помощи датчика псевдослучайных чисел, распределенных по равномерному закону. Использовался 48-ми буквенный алфавит.

На рис. 3 изображен график зависимости количества сравнений символов от конфигурации образца n x n для прямого подхода к сопоставлению, быстрого сопоставления по строкам обрабатываемого слова и быстрого сопоставления по строкам и по столбцам. Количество сравнений символов в таблице 1 и на рис. 3 приведено в масштабе 1:1000.

На рис. 4 изображен график зависимости количества сравнений символов от конфигурации образца n x 4 для прямого подхода к сопоставлению, быстрого сопоставления по строкам обрабатываемого слова и быстрого сопоставления по строкам и по столбцам. Количество сравнений символов в таблице 2 и на рис. 4 приведено в масштабе 1:1000.

Несложно заметить, что эффективность прямого подхода к сопоставлению с двумерным образцом в обоих экспериментах линейна относительно конфигурации образца. В машинном эксперименте № 1 алгоритм быстрого поиска по строкам и по столбцам с ростом n демонстрирует большую производительность по сравнению с алгоритмом поиска по строкам. Выигрыш достигает 25 % при сопоставлении с образцом 10 x 10 символов. В машинном эксперименте № 2 эффективность алгоритма быстрого поиска по строкам приблизительно равна константе и не зависит от количества строк образца, в то время как алгоритм поиска по строкам и по столбцам демонстрирует повышенную производительность, которая линейна относительно количества строк образца, и при обработке образца 10 x 4 символов в 2,4 раза больше, производительности алгоритма поиска по строке.



Таблица 1

Сравнение эффективности способов сопоставления

с двумерным образцом в конфигурации n x n символов

Алгоритм сопоставления

Длина образца, буквы


1

2

3

4

5

6

7

8

9

10

Прямой подход

1049

1069

1067

1065

1063

1060

1058

1056

1054

1052

Быстрый поиск по строке

1049

540

366

280

229

195

171

150

135

129

Быстрый поиск по строке и по столбцу

1049

515

324

235

185

155

134

118

106

97

Рис. 3. График зависимости количества сравнений символов, требуемых

для поиска всех вхождений двумерного образца с конфигурацией n x n,

от количества строк (столбцов) n образца


Таблица 2

Сравнение эффективности способов сопоставления

в конфигурации n x 4 символов

Алгоритм сопоставления

Длина образца, буквы


1

2

3

4

5

6

7

8

9

10

Прямой подход

1068

1066

1065

1065

1064

1063

1062

1061

1059

1058

Быстрый поиск по строке

278

276

276

275

275

275

275

274

274

273

Быстрый поиск по строке и по столбцу

278

272

258

233

200

175

155

137

125

114

Рис. 4. График зависимости количества сравнений символов, требуемых

для поиска всех вхождений двумерного образца с конфигурацией n x 4,

от количества строк n образца


СПИСОК ЛИТЕРАТУРЫ
1. Корректность параллельных вычислительных процессов/Ачасова С.М., Бандман О. Л. – Новосибирск: Наука. Сиб. отд-ние, 1990. – 253 с.

2. Специализированные процессоры для высокопроизводительной обработки данных/Бандман О. Л., Миренков Н. Н., Седухин С. Г. и др. – Новосибирск: Наука, 1988.



3. Boyer R.S., Moore J.S. (1977) "A fast string searching algorithm," Communications of the ACM, Vol. 20, No. 10, p. 762-72, October 1977.

4. Knuth D.E., Morris (Jr) J.H., Pratt V.R., 1977, Fast pattern matching in strings, SIAM Journal on Computing 6(1):323-350.


Смотрите также:
Задача сопоставления образца V и слова w состоит в поиске двухкоординатных позиций вхождения V в слово W
136.75kb.
1 стр.
Быстрый способ сопоставления с двумерным образцом
132.42kb.
1 стр.
1. Слово (лексическое значение, словосочетания, пословицы) Этимология слова
267.64kb.
1 стр.
Каким будет курс отечественной истории в школе? Это далеко не риторический вопрос
1887.88kb.
13 стр.
C. А. Лишаев Топологические метаморфозы слова: от речи к экрану
543.11kb.
3 стр.
Цена вхождения
6329.69kb.
22 стр.
К. Бессер-Зигмунд «Магические слова.»
1638.5kb.
28 стр.
К. бессер зигмунд магические слова
1647.45kb.
29 стр.
Святитель Григорий Нисский Слова и беседы
1165.49kb.
8 стр.
Проект методика организации коррекционной работы в старших классах общеобразовательной школы Разработчик проекта
104.94kb.
1 стр.
Задача по аналитической химии студентки 207 группы Гребенниковой Татьяны
190.74kb.
1 стр.
Курса Р1 Различные аспекты изучения русской лексики
13.63kb.
1 стр.