Просмотр исходного текста страницы Поиск с предварительным анализом искомой подстроки (asm x86)

Основу материала этого раздела составляет алгоритм КМП-поиска. Имя "КМП" является выборкой первых букв фамилий его создателей: Д. Кнута, Д. Мориса и В. Пратта. В основе алгоритма КМП-поиска лежит идея о том, что в процессе просмотра строки S с целью поиска вхождения в нее образца P становится известной информация о просмотренной части. Работа алгоритма производится в два этапа. 
#Анализируется строка-образец Р. По результатам анаиза заполняется вспомогательный массив смещений D.
#Производится поиск в строке S с использованием строки-образца P и массива смещений D.
Ниже приведена программа, реализующая алгоритм КМП-поиска.

<syntaxhighlight  lang="asm">
//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 на экран
                     ;...
</syntaxhighlight>

Подробно, хотя и не очень удачно, алгоритм КМП-поиска описан у Вирта . Этот алгоритм достаточно сложен для понимания, хотя в конечном итоге его идея проста. Центральное место в алгоритме КМП-поиска играет вспомогательный массив D. Поясним его назначение. Массив D содержит значения, которые нужно добавить к текущему значению j в позиции первого несовпадения символов в строке S и подстроке P (Рис. 1. ).
[[Image:PoiskSpredv_1.png|thumb|center|747px|Рис. 1. Пример КМП-поиска]]


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

Следующий ( и последний) алгоритм поиска в строке носит название '''Боуера и Мура - БМ- поиск'''. Он в значительной степени устраняет недостатки, присущие методу КМП-поиска.

<syntaxhighlight  lang="asm">

// 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;                       ;...
</syntaxhighlight>


Идея алгоритма БМ-поиска в том, что сравнению подвергаются не первые, а последние символы образца P и очередного фрагмента строки S. Если они не равны, то сдвиг в строке S осуществляется сразу на всю дину образца. Если последние символы равны, то сравнению подвергаются предпоследние символы, и т.д. При несовпадении очередных символов величина сдвига извлекается из таблицы D, которая, таким образом, выполняет ключевую роль в этом алгоритме. Заполнение таблицы происходит на основе конкретной строки-образца P следующим образом. Размер таблицы определяется размером алфавита, то есть количеством кодов символов, которые могут появляться в тексте. В нашем случае мы отвели под таблицу D память длиной, равной длине кодовой таблице ASCII. Таким образом, строки S и P могут содержать любые символы. Первоначально все байты кодовой таблицы заполняются значением, равным длине строки- образца для поиска P. Далее последовательно извлекаются символы строки-образца P начиная с первого. Для каждого символа определяется позиция его самого правого вхождения в строку-образец P. Это значение и заносится в таблицу D на место, соответствующее этому символу. Подробно получить представление о заполнение таблицы можно по фрагменту программы на псевдоязыке:

<syntaxhighlight  lang="asm">
// этап 1: формирование массива d
ДЛЯ j=0 ДО 255 ДЕЛАТЬ
        НАЧ_БЛОК_1
                 d[j]:=M
        КОН_БЛОК_1
ДЛЯ j=0 ДО М-2 ДЕЛАТЬ
         НАЧ_БЛОК_1
                  d[p[j]]:=M-j-1
         КОН_БЛОК_1
  </syntaxhighlight>

Так, для строки abcdabce процесс и результаты формирование таблицы D показаны на Рис.2.

[[Image:PoiskSpredv_2.png|thumb|center|747px|Рис. 2. Формирование массива D в программе БМ-поиска]]

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

[[Категория:Примеры популярных алгоритмов на Ассемблере]]