Поиск с предварительным анализом искомой подстроки (asm x86)
Последнее изменение этой страницы: 19:58, 9 августа 2015.
Основу материала этого раздела составляет алгоритм КМП-поиска. Имя "КМП" является выборкой первых букв фамилий его создателей: Д. Кнута, Д. Мориса и В. Пратта. В основе алгоритма КМП-поиска лежит идея о том, что в процессе просмотра строки S с целью поиска вхождения в нее образца P становится известной информация о просмотренной части. Работа алгоритма производится в два этапа.
- Анализируется строка-образец Р. По результатам анаиза заполняется вспомогательный массив смещений D.
- Производится поиск в строке S с использованием строки-образца P и массива смещений D.
Ниже приведена программа, реализующая алгоритм КМП-поиска.
//prg4_73_KMP -программа на псевдоязыке поиска строки P в строке S
//по алгоритму КМП-поиска. Длина S фиксирована.
//Вход: S и P -массивы символов размером N и M байтов (M=<N).
//Выход: сообщение о количестве вхождений строки P в строку S.
ПЕРЕМЕННЫЕ
INT_BYTE s[n]; //0=<i<N-1
INT_BYTE p[m]; //0=<j<M-1
INT_BYTE d[m]; //массив смещений
INT_BYTE k=-1; i=0; j=0 // индексы
НАЧ_ПРОГ
// этап 1; формирование массива смещений d
j:=0; k:=-1; d[0]:=-1
ПОКА j<M-1 ДЕЛАТЬ
НАЧ_БЛОК_1
ПОКА ((k>=0)И(p[j]<>p[k])) k:=d[k]
j:=j+1; k:=k+1
ЕСЛИ p[j]==p[k] TO d[j]:=d[k]
ИНАЧЕ d[j]:=k
КОН_БЛОК_1
// этап 2: поиск
i:=0; j:=0; k:=0
ПОКА ((j<M)И(i<N)) ДЕЛАТЬ
НАЧ_БЛОК_1
ПОКА ((j>=0)И(s[i]<>p[j])) j:=d[j]
j:=j+1; i=i+1
КОН_БЛОК_1
ЕСЛИ j=M TO вывод сообщения об удаче поиска
ИНАЧЕ вывод сообщения о неудаче поиска
КОН_ПРОГ
; Программа: prg4_73_KMP.asm. Поиск строки P в строке S
; по алгоритму КМП-поиска. Длина S фиксирована.
.data
s db "fgcabefabcaabcdabc!bdededegjfkababcdabcec"
db "abeabcdabcej:koiabcabe" ; задаем массив S
Len_S=$ - s ; N=Len_S
db "$"
mes db 0dh. 0ah. "Вхождений строки - "
db "abcdabce" ; задаем массив P - аргумент поиска
Len_P =$ - p ; M=Len_P
db " - "
Count db 0. "$" ; счетчик вхождений P в S
d db Len_p dup (0) ; массив смещеий
k db 0
.code
;-------------этап 1 - заполнение массива смещений: j:=0; k:=-1; d[0]:=-1
xor si. si ; si - это j
mov k. -1
mov d. -1
;--------------ПОКА j<M-1 ДЕЛАТЬ
cycl1: cmp si, len_p -1 ; j<M-1
jge exit_d
cmp k, 0 ; ПОКА ((k>=0)И(p[j]<>p[k])) k:=d[k]
j1 falsee
mov bl, k
mov al, p[si]
cmp al, p[bx]
je falsee
mov bl, d[bx]
mov k, bl ; k:=d[k]
jmp cyc11
;--------j:=j+1; k:=k+1
falsee: inc si ; j:=j+1
inc k
mov bl, k
mov al, p[si] ; ЕСЛИ p[j]==p[k] TO d[j]:=d[k]
cmp al, p[bx]
jne elsee
mov al, d[bx]
mov d[si], al
jmp cycl1
elsee: mov d[si], bl
jmp cycl1
;--------этап 2: поиск
exit_d: xor di, di ; i:=0;
xor si, si ; j:=0;
m3: cmp si, Len_p ; ПОКА ((j<M)и(i<N)) ДЕЛАТЬ
jge m1
m34: cmp di, Len_s
jge m1
cmp si, 0 ; ПОКА ((j>=0)И(s[i]<>p[j])) j:=d[j]
j1 m4
mov al, s[di]
cmp al, p[si]
je m4
movzx al, d[si]
mov si, ax
m4 inc si ; j:=j+1
inc di ; i:=i+1
jmp m3
;------ЕСЛИ j=M TO вывод сообщения об удаче поиска
m1: cmp si, len_p
jne exit_f ; ИНАЧЕ вывод сообщения о неудаче поиска
inc count
cmp di, len_s
jge exit_f
xor si, si
jmp m34
exit_f: add count. 30h
;------вывод сообщения mes на экран
;...Подробно, хотя и не очень удачно, алгоритм КМП-поиска описан у Вирта . Этот алгоритм достаточно сложен для понимания, хотя в конечном итоге его идея проста. Центральное место в алгоритме КМП-поиска играет вспомогательный массив D. Поясним его назначение. Массив D содержит значения, которые нужно добавить к текущему значению j в позиции первого несовпадения символов в строке S и подстроке P (Рис. 1. ).
Из проведенного обсуждения можно сделать два вывода - один приятный, другой - не очень. Во-первых, явное достоинство этого метода в том, что исключены возвраты назад. Во-вторых, эффективность использования КМП-поиска зависит от исходных данных - реальное ускорение поиска ( сдвиг образа P относительно строки S более чем на один символ) получается, когда в строке S достаточно часто встречаются последовательности символов, совпадающие с началом образа P.
Следующий ( и последний) алгоритм поиска в строке носит название Боуера и Мура - БМ- поиск. Он в значительной степени устраняет недостатки, присущие методу КМП-поиска.
// prg4_83_BP - программа на псевдоязыке поиска строки P в строке S
// по алгоритме БМ-поиска . Длина S фиксирована.
// Вход: S и P - массивы символов размеров N и M байтов (M=<N).
// Выход: сообщение о количестве вхождений строки P в строку S.
ПЕРЕМЕННЫЕ
INT_BYTE M; // M - длина образца
INT_BYTE s[n]; // 0=<i<N-1
INT_BYTE p[m]; // 0=<j<M-1
INT_BYTE d[256]; //вспомогательный массив с размером = длине кодовой таблицы
INT_BYTE k=0; i=0; j=0 // индексы
НАЧ_ПРОГ
// этап 1 : формирование массива d
ДЛЯ j=0 ДО 255 ДЕЛАТЬ
НАЧ_БЛОК_1
d[j]:=M
КОН_БЛОК_1
ДЛЯ J=0 ДО М-2 ДЕЛАТЬ
НАЧ_БЛОК_1
d[p[j]]:=M-j-1
КОН_БЛОК_1
// этап 2: поиск
i:=M
ПОВТОРИТЬ
j:=M; k:=i
ПОВТОРИТЬ
K:=k-1; j:=j-1
ПОКА (j>=0)ИЛИ(p[j]==s[k])
i:=i+d[s[i-1]]
ПОКА (j>=0)ИЛИ(i<N)
ЕСЛИ j<0 ТО вывод сообщения об удаче поиска
ИНАЧЕ вывод сообщения о неудаче плиска
КОН_ПРОГ
;+-----------------------------------------------------------------------------------------------------------+
; | Программа: prg4_B3_BP.asm. Поиск строки P в строке S |
; | по алгоритму БМ-поиска. Длину S фиксирована. |
; +----------------------------------------------------------------------------------------------------------+
.data
mes db 0dh, 0ah, "Вхождений строки - "
p db "ab" ; задаем массив P - аргумент поиска
Len_P = $ - p ; M=Len_P
db " - в строку -"
s db "fgcabceabcaab" ; задаем массив S
Len_S = $ - s ; N=Len_S
db " - "
Count db 0 ; счетчик вхождений P в S
db " раз(a)$"
d db 255 dup (0) ; всмоготательный массив
k db 0
.code
;-------этап 1 - заполнение массива D значением M –
; размером образца для поиска
mov cx, 255 ; размер кодовой таблицы ASCII
mov al, len_p ; ДЛЯ j=0 ДО 255 ДЕЛАТЬ
les di,d
rep stosb ; d[j]:=M
;-------- цикл просмотра образца и замещение некоторых элементов d
; значениями смещений ( см. пояснение за текстом програмы)
xor si, si ; j:=0
;--------ДЛЯ j=0 ДО М-2 делать
cycl1: cmp si, len_p - 1
jge e_cycl1
mov al, p[si]
mov di, ax
xor bx, bx
mov bl, len_p
dec bl
sub bx, si
mov d[di], bl
inc si
jmp cycl1
;--------//этап 2: поиск
e_cycl1: mov di, len_p
;-------ПОВТОРИТЬ - цикл пока ( j>=0)ИЛИ(I<n)
cycl2: mov si, len_p ; j:=M
mov bx, di ; k:=I
;-------цикл пока (j>=0)ИЛИ(p[j]==p[k])
cycl3: dec bx ; k:=k-1
dec si ; j:=j-1
cmp si, 0 ; пока (j>=0)ИЛИ(p[j]==p[k])
jl m2
mov al, p[si]
cmp s[bx], al
jne m2
jmp cycl3
;---------i:=i+D[S[I-1]]
m2: push di
dec di
xor ax, ax
mov al, s[di]
mov di, ax
mov al, d[di]
pop di
add di, ax ; I:=I+d[s[I-1]]
cmp si, 0 ; цикл пока (j>=0)ИЛИ(I<n)
jl m1
cmp di, len_s
jg exit_f
jmp cycl2
;---------вывод сообщения о результатах поиска
m1 inc count
jmp cycl2
exit_f: add count, 30h
lea dx, mes
mov ah, 09h
int 21h
exit; ;...
Идея алгоритма БМ-поиска в том, что сравнению подвергаются не первые, а последние символы образца P и очередного фрагмента строки S. Если они не равны, то сдвиг в строке S осуществляется сразу на всю дину образца. Если последние символы равны, то сравнению подвергаются предпоследние символы, и т.д. При несовпадении очередных символов величина сдвига извлекается из таблицы D, которая, таким образом, выполняет ключевую роль в этом алгоритме. Заполнение таблицы происходит на основе конкретной строки-образца P следующим образом. Размер таблицы определяется размером алфавита, то есть количеством кодов символов, которые могут появляться в тексте. В нашем случае мы отвели под таблицу D память длиной, равной длине кодовой таблице ASCII. Таким образом, строки S и P могут содержать любые символы. Первоначально все байты кодовой таблицы заполняются значением, равным длине строки- образца для поиска P. Далее последовательно извлекаются символы строки-образца P начиная с первого. Для каждого символа определяется позиция его самого правого вхождения в строку-образец P. Это значение и заносится в таблицу D на место, соответствующее этому символу. Подробно получить представление о заполнение таблицы можно по фрагменту программы на псевдоязыке:
// этап 1: формирование массива d
ДЛЯ j=0 ДО 255 ДЕЛАТЬ
НАЧ_БЛОК_1
d[j]:=M
КОН_БЛОК_1
ДЛЯ j=0 ДО М-2 ДЕЛАТЬ
НАЧ_БЛОК_1
d[p[j]]:=M-j-1
КОН_БЛОК_1Так, для строки abcdabce процесс и результаты формирование таблицы D показаны на Рис.2.
Куда в двух последних программах пристроить цепочные команды? К сожалению, некуда. Когда автор писал текст этих программ, он настолько увлекся, что напрочь забыл как о них, так и о цели настоящего раздела - показать особенности использования цепочных команд при организации поиска информации. А когда вспомнил, то сделал вывод, что пристроить их вроде бы и некуда. А вы как думаете? Окончательный вывод об эффективности можно сделать по результатам работы профилировщика.
ISSN 2542-0356
Следуй за Полисом
Оставайся в курсе последних событий
Лицензия
Если не указано иное, содержание этой страницы доступно по лицензии Creative Commons «Attribution-NonCommercial-NoDerivatives» 4.0, а примеры кода – по лицензии Apache 2.0. Подробнее см. Условия использования.