Главная
страница 1

Ассоциативный способ сопоставления с двумерным образцом


1. ОСНОВНЫЕ ПОНЯТИЯ И ОБОЗНАЧЕНИЯ
Обозначим через А конечный алфавит, через М множество имен, имеющее мощность не более счетной.

Определение 1. Пара (символ алфавита, имя) называется клеткой и обозначается . Символ называется состоянием клетки, – именем клетки.

Определение 2. Множество клеток , в котором нет двух клеток с одинаковыми именами, называется клеточным множеством.

Определение 3. Конечное клеточное множество W = {, , …, } называется словом.

Слово можно представить в наглядной геометрической форме, если множество имен M интерпретировать точками пространства. Слово W = {, , , } имеет линейную форму и располагается в одномерной целочисленной решетке. Имена клеток являются координатами узлов этой решетки, а узлы помечены символами алфавита А – состояниями клеток. Слово W = {, , , } располагается в двумерной решетке, как показано на рис. 1.


Рис. 1. Пример двумерного слова.


Далее слова будем представлять помещенными в целочисленную прямоугольную решетку размерности n, n = 1, 2, …. Тогда множество имен можно представить в виде M = , где N = {1, 2, …}.

Определение 4. Два слова и пересекаются, если в них есть одинаковые клетки (с одинаковыми именами и состояниями) и множество является словом.

Определение 5. Два слова и равны, если для каждой клетки слова найдется точно такая же клетка в слове и слова и состоят из одинакового количества клеток.

Определение 6. Слово входит в слово , если для каждой клетки слова найдется точно такая же клетка в слове и слово состоит из такого количества клеток, что оно меньше или равно количеству клеток в слове .

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

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

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

W = { , , …, ,



, , …, ,

….,


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

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

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

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

Введенные обозначения рассмотрим для образца V = {, , , , , , }, изображенного на рис. 2.

Рис. 2. Пример двумерного образца V в локальной

прямоугольной системе координат
Для двумерного образца V: n = 3, m = 3, =3, =2, =2, =1, =3, =3, =1, =3, =2, =3, =2, =3, =1, =1, =1, =3, =1, =3.

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


2. ПРЯМОЙ ПОДХОД К СОПОСТАВЛЕНИЮ
Поиск вхождения двумерного образца начинается с сопоставления обрабатываемого слова с 1-й строкой образца. При успешном результате сопоставления необходимо сопоставить 2-ю строку образца с соответствующей подстрокой следующей строки обрабатываемого слова и т.д., пока не будут успешно сопоставлены все строки образца или не будет достигнут конец строки обрабатываемого слова. При обнаружении отвергающего символа (символ образца называется отвергающим, если в процессе сопоставления он не совпал с очередным символом обрабатываемого слова; с тем же основанием отвергающим называется и соответствующий символ обрабатываемого слова) процесс сопоставления с двумерным образцом снова начинается с поиска вхождения 1-й строки образца в позиции на единицу большей позиции обнаружения частичного вхождения. Если вхождение образца при просмотре слова слева направо обнаружить не удалось, выполняется поиск вхождения образца со следующей строки слова и т. д., пока не будет обнаружено вхождение или не будет достигнута последняя строка обрабатываемого слова.

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

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

Алгоритм, реализующий прямой подход, приведен на рис. 3.


j := 1;

t := 1;


sb := 0;

tb := 0;


while ( (tb <= r – n) и (sb <= p - m) ) {

while ((sb <= p - m) и (j <= n) ) {

i = Xminj;

s = sb + i

while ( i <= Xmaxj ) {

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

i := i + 1;

s := s + 1;

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

sb := sb + 1;

j := 1;

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



}

}

j := j + 1;



t := t + 1;

}

if (j > n) { // проверка успешности сопоставления



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

}

j := 1;



sb := 0;

tb := tb + 1;

}
достижении

Прежде чем перейти к рассмотрению


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

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


Следующими сравниваются A(m, ) и B(s+fm+m,t+).
При обнаружении отвергающих символов A(m, j), где <= j <= и B(s+m,t+j), и при отсутствии среди букв j строки образца буквы B(s+m,t+j), образец сдвигается по горизонтали на позиций вправо.
Пусть отвергающими оказались символы A(m, ) и B(k,l). Как уже говорилось, если B(k,l) не содержится нигде в строке образца, шаблон можно сдвинуть на f позиций вправо. С другой стороны, если B(k,l) присутствует в образце, и A(m-v, ) – его самое правое вхождение в строке, то образец можно сдвинуть лишь на v позиций вправо, совмещая A(m-v, ) с B(k,l). Поиск можно продолжить сравнением A(m, ) с B(k+v,l), то есть индекс отвечающий за движение в горизонтальном направлении по обрабатываемому слову увеличиваем на v.
Если A(m, ) и B(k,l) совпадают, нужно сравнивать все символы в m столбце образца и с соответствующими символами k столбца обрабатываемого слова, пока весь подстолбец обрабатываемого слова не будет сопоставлен со столбцом образца или пока не встретится несовпадение. Когда вхождение m столбца будет определено, необходимо перейти к сопоставлению m-1 столбца образца с соответствующими символами k-1 столбца обрабатываемого слова и т.д.
Если отвергающим оказался, скажем, символ A(i, j), то мы знаем, что суффикс j-й строки образца A(i+1,j)… A(Xmaxj,j) равен подстроке обрабатываемого слова B(k- Xmaxj +i+1, l)… B(k, l), и A(i, j) не равен B(k- Xmaxj +i, l). Теперь, если самым правым вхождением B(k- Xmaxj +i, l) в j строку образца снова является, скажем, A(Xmaxj -v, j), образец можно сдвинуть по горизонтали на i- Xmaxj +v символов вправо, так что A(Xmaxj -v, j) окажется на одной позиции с B(k- Xmaxj +i, l). Процедуру поиска следует продолжить сравнением A(m, ) с соответствующим символом, в данном случае с B(k + i- Xmaxj +v, l). Приращение индекса отвечающего за движение в горизонтальном направлении по обрабатываемому слову с позиции несовпадения до следующей пробной позиции равно, таким образом, (k + i- Xmaxj +v)-( k- Xmaxj +i) = v. Заметим, что приращение тоже, что и в случае обнаружения отвергающего символа в самом правом столбце образца.
Если A(Xmaxj -v, j) находится правее A(i, j), то значение i- Xmaxj +v отрицательно и совмещение A(Xmaxj -v, j) с B(k + i- Xmaxj +v, l) оказывается излишним, поскольку повлечет за собой шаг назад. В этих обстоятельствах образец лучше сдвинуть на одно место вправо и сравнивать A(m, ) с B(k+1, l). Для этого следует увеличить индекс отвечающий за движение в горизонтальном направлении по обрабатываемому слову на (k+1)-( k- Xmaxj +i) = Xmaxj +1-i.
Приращения v, используемые для перемещения по обрабатываемому слову в горизонтальном направлении, вычисляются заранее для каждой строки образца отдельно и хранятся в таблицах delta[n]. В процессе поиска доступ к таблице j строке образца delta[j] осуществляется по отвергающим символам обрабатываемого слова, поэтому размер каждой таблицы равен мощности используемого алфавит символов.
При формировании таблицы delta[j] вход для символа w равен fj-i, где A(i, j) – самое правое вхождение w в j строку образца, и равен fj, если w не содержится в j строке образца, то есть:
delta[j][w] = min {v : v = fj или (0 <=v < fj и A(Xmaxj-v, j) = w)}
Таблица delta[j] для алфавита ОМЕГА инициализируется следующим образом:
for j = 1 to n do

for w = 1 to ОМЕГА

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

for i = Xminj to Xmaxj

delta[j][A(i, j)] = Xmaxj – i
Отсюда видно, что время инициализации n таблиц delta равно O(n(ОМЕГА+fj)).

Проиллюстрируем работу одной таблицы delta для строки образца x = ABCDB.


w A B C D E F G H ...

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


Несовпадение возникает при yi = A

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

y - текст . . . L M N A B C D B . . .

i
Следующими сравниваются символы xm и yi+skip[A], то есть yi+4.

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

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

i i+4
Ниже приведен алгоритм сопоставления двумерного образца с прямоугольной матрицей символов – обрабатываемое слово.

i = m;


s = m;

tb := 0; // Глоб. индекс смещения в верт.направлении по обрабатываемому слову

while ( tb <= r - n ) {

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

j = Ymaxi;

t = tb + j

// сканирование i столбца образца в направлении снизу вверх

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

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

j: = j – 1;

t:= t – 1;

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

if (i > delta[j][B(s, t)] ) {

s := fj+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;

}


Смотрите также:
Быстрый способ сопоставления с двумерным образцом
132.42kb.
1 стр.
Ассоциативный способ сопоставления с двумерным образцом
90.66kb.
1 стр.
Воображение и внимание. Первый способ репетирования атмосфера. Второй способ репетирования
321.72kb.
1 стр.
Статья: Перспективы мультилингвального обучения в свете сопоставления терминосистем в русском и армянском языках
88.03kb.
1 стр.
1. Общая характеристика туристической компании ооо«Лаперуз&Кук»
192.17kb.
1 стр.
Лабораторная работа №7 обработка двумерных массивов цель работы: Изучить принципы работы с двумерными массивами. Общие сведения
76.78kb.
1 стр.
Урок №19. Тема. А. С. Пушкин. Стихотворение «Зимняя дорога»
52.04kb.
1 стр.
«россия в мире XXI века: между насилием и диалогом»
84.11kb.
1 стр.
Аллен Карр Легкий способ добиться успеха
652.1kb.
14 стр.
Способ химической очистки ткани
10.55kb.
1 стр.
Технологическая схема производства цемента
32.73kb.
1 стр.
Урок. Слово о М. А. Шолохове и его романе «Тихий Дон». Ассоциативный анализ названия романа. Роль эпиграфов
87.94kb.
1 стр.