Black Crow #02 01 ноября 1998

Программирование

Программистам - Быстрый поиск в текстовом файле.

   ---ОТКРЫТЫЕ ТЕХНОЛОГИИ---    
                                
                    
------------------------------------------
   Компьютером я обзавёлся в середине 1992
года. С начала я, как и все, наверное, си-
дел  исключительно на игрушках. Ну надо же
совковый  голод  по  передовым технологиям
удалить.  Так вот - вдоволь наигравшись во
всевозможные  игры (до сих пор люблю логи-
ческие  игрушки) начал понемногу посматри-
вать  во  внутрь программ. Бейсиковых, ко-
нечно.  Как было интересно менять цвета, а
потом  и  лоадеры.  Медленно, но уверенно,
приходили  знания  по ассемблеру. Язык так
называемого высокого уровня, коим величают
Бейсик,  так  и  не  знаю  толком. Вернее,
знаю, но пользоваться полноценно научиться
не  пришлось. Сразу полез "в дебри", о чём
никогда  не  жалел.  Начали появляться уже
свои  программки.  Ещё тогда начала слажи-
ваться  традиция  писать системный и прик-
ладной  софт. Я умышленно разделяю эти ка-
тегории,  т.к.  многие  ламеры ошибочно их
мешают в единое целое.                    
                                
   Ну  да  ладно, проехали. Однажды... Как
банально  звучит.  Но однажды столкнулся с
маленькой проблемой: нужно быстро и эффек-
тивно  найти  что-то  символьное  в чём-то
символьном. Короче, писалась как раз прог-
рамма "Картотека файлов". Так вот там надо
было  найти  имя  файла  по  образцу.  Ес-
тественно,  что  делал  поиск  примитивным
способом:  перебирая и сравнивая все буквы
попорядку.  Для той программы это "тормоз-
ное"  действие  особой  роли не играло, но
стало  интересно придумать более умное ре-
шение данной проблемы. Не успел. Подверну-
лась  под  руку  одна  очень умная книга с
интригующим  названием "Современный компь-
ютер".  Я  свой "Sintez" именно таким счи-
тал,   поэтому   начал  листать  мудрённые
статьи. И вот нашёл нужную статью на инте-
ресующую тему. Но вот только ассемблерного
примера  для  Z-80 там не было;-) Пришлось
самому сочинять...                        
                                
   Не слишком ли утомителен мой вступитель
ный пасквиль? Знаю, молчу, каюсь.         
                                
   Итак, поехали. Не буду более много рас-
сусоливать  на тему что и как было - пере-
ходим  к  делу,  а по сему нудную часть из
книги тоже пропускаю. Надо сектора на дис-
ке экономить.                             
                                
   Для начала рассмотрим пример "обычного"
ламерского метода поиска, коим грешат даже
ассы программирования. Иногда. Поиск слова
в  тексте  осуществляется путём последова-
тельных  сравнений букв. Слово и текст яв-
ляются  массивами букв. Пример такого тек-
ста, в котором ищем слово PICK:           
                                
P I С K                                   
P I С K                                   
  P I С K                                 
    P I С K                               
      P I С K                             
        P I С K                           
          P I С K                         
          P I С K                         
          P I С K                         
            P I С K                       
              P I С K                     
              P I С K                     
                P I С K                   
                  P I С K                 
                    P I С K               
                    P I С K               
                    P I С K               
                    P I С K               
                                
   Как  вы уже догадались - красным цветом
выделены  совпадения при поиске, а голубым
несовпадения.  Здесь наглядно видно утоми-
тельность  данного  процесса для поиска. В
примере условный текст содержит 20 букв, а
слово  4 буквы. Слово считается найденным,
когда  все  буквы совпали. Начинаем искать
совпадения  с  начала текста. Первая буква
слова сравнивается с первой буквой текста.
Поскольку   они  совпали  (красный  цвет),
сравниваются  вторые  буквы.  На  этот раз
буквы  не совпали (голубой цвет); следова-
тельно,  слово  сдвигается на одну позицию
вправо  и проверка производится заново и с
начала  слова.  И так до тех пор, пока все
четыре буквы не совпадут. Мраки...        
                                
   Ассемблерный  пример  такого поиска нет
никакого смысла приводить, т.к. это не яв-
ляется  целью  статьи - ТОЛЬКО ПЕРЕДОВЫЕ И
СОВЕРШЕННЫЕ  ТЕХНОЛОГИИ  В ЖИЗНЬ! Если кто
желает,  может найти такой пример в подав-
ляющем  большинстве прикладного софта, ра-
ботающего с базами данных.                
                                
   Кто  бы мог подумать, что спустя 30 лет
после того, как были начаты исследования в
области  кибернетики,  можно существенно и
почти  коренным образом улучшить метод ре-
шения  такой фундаментальной задачи, какой
является  поиск  в  тексте. Тем не менее в
1976 году Р. Бойер и Дж. Мур, работавшие в
то время в Техасском университете в Остине
нашли более быстрый способ. Их идея позво-
ляет увеличить скорость поиска как минимум
в  два  раза  при  каждом цикле программы.
Сравнение слова с частью текста начинается
от  конца слова (помещаемого в начале тек-
ста)  и  продолжается  к  его началу. Если
проверяемая  литера в слове не совпадает с
соответствующей  литерой  текста, то слово
двигается  вправо  относительно этой самой
позиции,  которую условно назовём опорной,
до тех пор, пока какая-нибудь литера снова
не  совпадёт с литерой текста в этой пози-
ции.  Если  этого  не произойдёт, то слово
сдвигается таким образом, чтобы его первая
литера отстояла от опорной позиции на один
интервал. Круто? Ещё бы!                  
                                
   Сразу  же возникает вопрос, как находят
следующую  совпавшую  литеру,  - ведь если
для  этого  нужно сравнивать литеры по од-
ной,  то никакого выигрыша нет. Существует
другой способ - завести таблицу расстояний
от  конца  слова  до  последнего появления
каждой  буквы в этом слове. Конечно, нужно
потратить определённое время на расчёт та-
кой  таблицы,  но  сделать  это необходимо
только  один  раз;  если  текст достаточно
длинный, дело того стоит. По личному опыту
уже убедился в этом.                      
                                
   Возможно,  что  алгоритм  Бойера и Мура
работает  быстрее,  однако насколько можно
быть   уверенным  в  его  правильности?  В
частности,  как  убедиться, что при сдвиге
на  несколько  позиций вправо без попутных
сравнений  не было пропущено ни одной сов-
падающей группы литер? Содержательное объ-
яснение  состоит  в  том,  что для полного
совпадения  необходима  идентичность  всех
пар  литер, между тем, как группы, которые
пропускаются,  отличаются  хотя бы в одной
позиции, а именно в опорной позиции.      
                                
   Нельзя не учитывать ещё один немаловаж-
ный ньюанс - в данном тексте слова может и
не  быть...  Тогда следует "договориться",
что необходимо знать размер слова и размер
текста  для  определения  по ходу дела ве-
роятности   совпадения.  Если  в  процессе
сдвига получается, что слово стало больше,
чем  остаток непроверенного текста, то де-
лать  там более нечего - нет такого слова!
                                
   Теперь  следует рассмотреть второй спо-
соб  на  схеме, что сразу же позволит оце-
нить его достоинства. Итак,               
                                
PETER PIPER PICKED A PECK       
РЕСK                            
  РЕСK                          
      РЕСK                      
        РЕСK                    
            РЕСK                
            РЕCK                
            РЕCK                
                РЕСK            
                    РЕСK        
                     РЕСK       
                     РЕCK       
                     РЕCK       
                     РECK       
                                
   Расчёт  смещения  в таблице, по которой
надо  делать  пропуск при несоответствиях,
происходит следующим образом:             
             P Е С K                      
             | | |__ 1                    
             | |____ 2                    
             |______ 3                    
                                
   Сама  таблица  вырабатывается  из учёта
размера слова, которое ищем в тексте, т.е.
четыре символа:                           
                                
        A.......4                         
        B.......4                         
        С_______1                         
        D.......4                         
        Е_______2                         
        F.......4                         
        G.......4                         
        Н.......4                         
        I.......4                         
        J.......4                         
        K_______4                         
        L.......4                         
        M.......4                         
        N.......4                         
        О.......4                         
        P_______3                         
        Q.......4   и так далее.          
                                
   Теперь  сравните  оба способа, посчитав
количество операций с текстом. Впечатляет,
не так ли? Эффективность второго безогово-
рочна. Осталось дело за малым: набить объ-
ектный  код в ассемблере. На Бейсике тоже,
наверное, можно, но зачем??? Итак, догово-
римся, что нам надо знать размер введённо-
го слова (далее "образец"). Обычно это де-
лается после input`а. Если нет - извращай-
ся сам. Теперь, когда размер знаем, не ме-
шало  бы знать размер текста. Если нет та-
кого  параметра, то прийдется при беганьи,
допустим  по  массиву с размыми величинами
его  составляющих,  вырабатывать или полу-
чать  его  размер, чтобы знать, когда надо
прекратить поиск ввиду отсутствия совпаде-
ний. Ох, закрутил... Всё, ассемблер:      
                                
     ПРИМЕР РАБОТЫ С ПОИСКОМ ПО ИМЕНИ     
           ИЛИ НЕПОЛНЫМ ДАННЫМ            
------------------------------------------
                                
        ORG  #6000                        
        LD   HL,1       ;номер начальной  
        LD   (NOMLI),HL ;строки поиска    
        LD   HL,4       ;размер вложений  
        LD   (N_END),HL ;в ГМ.            
        CALL INTABL                       
        CALL 3435                         
        LD   A,2                          
        CALL 5633                         
SENAME  LD   HL,(NOMLI) ;номер строки ГМ  
        PUSH HL                           
        CALL SUMMA      ;ее адрес         
        CALL POISK      ;поиск            
        CALL Z,EXECUT   ;найдено совпад.  
        POP  HL                           
        INC  HL         ;дальше идем      
        LD   (NOMLI),HL                   
        LD   HL,(N_END) ;проверка конца   
        DEC  HL         ;глоб.массива     
        LD   (N_END),HL ;по кол-ву но-    
        LD   A,Н        ;меров в нем      
        OR   L                            
        JR   NZ,SENAME                    
        RET             ;"NOT FOUND"      
;                                         
EXECUT  LD   DE,(ТЕХТ)  ;откуда           
        LD   ВС,8       ;длина            
        CALL 8252       ;печать           
        LD   A,13                         
        RST  16                           
        RET                               
                                
     ИНИЦИАЛИЗАЦИЯ ТАБЛИЦЫ ДЛЯ ПОИСКА     
    Вызывается один раз перед поиском.    
;--------------------------------------   
INTABL  LD   HL,ZAG     ;где образец      
        LD   DE,OBRAZ                     
        LD   ВС,8                         
                                
        LDIR    ;....ЭТО ДЛЯ ПРИМЕРА....  
;       CALL IN_NAM     ;ввод образца     
;       EXX                               
;       LD   HL,ZAG                       
;       LD   DE,OBRAZ                     
;       CALL NAME       ;проверка символов
;       EXX     ;и перекачка в OBRAZ...   
                                
        LD      B,5;......ПРИМЕР......... 
;B=СКОЛЬКО БУКВ НЕДОНАБРАНО ПРИ INPUT     
        LD   A,B        ;кол-во букв образ
                        ;НАДО ЗНАТЬ!!!    
        DEC  A                            
        JR   Z,MMM1     ;1                
        LD   A,8                          
        SUB  B                            
        JR   NZ,MMM2                      
        EI              ;НЕТ ВВОДА!!!     
        RET                               
MMM1    LD   A,(ZAG+7)  ;конец образца    
        СР   #20        ;байт заполнения  
        LD   A,7                          
        JR   Z,MMM2     ;<>8              
        INC  A          ;8                
MMM2    LD   (NSIZE),A  ;размер образца   
        LD   IX,OBRAZ   ;образец          
        LD   HL,MASIV   ;таблица сдвига   
        LD   DE,MASIV+1 ;для пропускания  
        LD   ВС,95      ;несоответствия   
        LD   (HL),A     ;step пропусканий 
        LDIR                              
        LD   HL,OBRAZ   ;образец          
        LD   С,A        ;его длина        
        DEC  С          ;минус один на    
        ADD  HL,ВС      ;последний симв.  
        LD   (ENDOBR),HL;конец образца    
        LD   С,B        ;С=0              
        LD   B,A        ;B=длина образца  
        DJNZ MMMЗ       ;>1               
        JR   MMMЧ       ;<1               
MMMЗ    LD   A,(HL)     ;проверка совпаде-
        DEC  HL         ;ний рядом стоящих
        СР   (HL)       ;символов         
        JR   NZ,MMMS                      
        DJNZ MMMЗ                         
        LD   HL,MASIV   ;массив перескока 
        LD   DE,MASIV+1 ;заполнить 1 для  
        LD   ВС,95      ;шага в единицу   
        LD   (HL),1                       
        LDIR                              
        JR   MMMЧ                         
MMMS    LD   A,(IX+0)   ;символ из образца
        SUB  #20        ;корректируется к 
        LD   Е,A        ;0 для опр.шага   
        LD   D,С;С=0    ;при несовпадении 
        LD   HL,MASIV   ;см.прим.!        
        ADD  HL,DE                        
        LD   (HL),B     ;шаг пропуска для 
        INC  IX         ;каждой буквы     
        DJNZ MMMS       ;по длине образа  
MMMЧ    RET             ;конец операции   
                ;или JP в цикл поиска...  
                                
    --------- ПРИМЕЧАНИЕ -------------    
;MMMS   делает поправку в массив при несо-
;ответствиях образца и данных в глобальном
;массиве для определения размера шага при 
;оставлении несовпавшего фрагмента для    
;каждой буквы из образца.                 
;---------------------------------------  
                                
    ПОЛУЧЕНИЕ НОВОГО АДРЕСА ДЛЯ ПОИСКА    
;---------------------------------------  
;in:HL,0 - номер строки в глоб. массиве   
                                
SUMMA   LD   Е,L                          
        LD   D,Н                          
        LD   B,7        ;размер записи    
SUMM1   ADD  HL,DE                        
        DJNZ SUMM1                        
        LD   ВС,GMASS-8 ;адрес начала ГМ  
        ADD  HL,ВС                        
        LD   (ТЕХТ),HL  ;адрес для поиска 
        RET                               
                                
  ПОИСК В ГЛОБАЛЬНОМ МАССИВЕ ПО ОБРАЗЦУ   
;---------------------------------------- 
POISK   LD   A,(NSIZE)  ;размер образца   
        DEC  A          ;стать на послед- 
РО1     LD   (NSIZE+1),A;нюю букву        
        LD   HL,(ТЕХТ)  ;адрес в глоб.масс
        LD   ВС,(NSIZE)                   
        LD   Е,A                          
        LD   D,#00                        
        LD   B,D                          
        ADD  HL,DE      ;стать на длину   
        ЕХ   DE,HL      ;образца в гл.масс
        LD   HL,(ENDOBR);конец образца    
РО2     LD   A,(DE)     ;байт в гл.масс.  
        CPD             ;сверяется с образ
        JR   NZ,PO3     ;не совпал        
        DEC  DE         ;новый байт гл.мас
        RET  РО         ;конец проверки   
        JR   РО2                          
PO3     SUB  32         ;коррекция для пе-
        LD   Е,A        ;рехода по массиву
        LD   D,B        ;оставления фрагм.
        LD   HL,MASIV                     
        ADD  HL,DE                        
        LD   A,(NSIZE+1);откуда начал     
        ADD  A,(HL)     ;сколько переск.  
        СР   8          ;размер записи в  
                        ;глобал.массиве   
        JR   С,РО1      ;продолжить поиск 
        OR   A          ;флаг Z=0 нет сов-
        RET             ;падений ???????  
                                
       СИСТЕМНЫЕ ПЕРЕМЕННЫЕ ПОИСКА        
;---------------------------------------  
ТЕХТ    DEFS    2       ;адрес в ГМ       
NOMLI   DEFS    2       ;номер строки ГМ  
N_END   DEFS    2       ;кол-во строк ГМ  
ENDOBR  DEFS    2       ;конец образца    
NSIZE   DEFS    2       ;длина образца    
OBRAZ   DEFS    8       ;корректный образ.
ZAG     DEFM  "ISH     ";введенный образец
MASIV   DEFS    96      ;таблица для пере-
                        ;скакивания при   
                        ;несоответствии.  
GMASS   DEFM "SASHA   " ;глобальный массив
        DEFM "GRYSHA  " ;для примера 8    
        DEFM "MISHA   " ;символов размер  
        DEFM "KLAVISHA"                   
        DEFS    10                        
                                
   Не  совсем удачный пример получился, но
работоспособный. Если его откомпилировать,
то получится рабочая версия поиска по вве-
дённому  образцу.  Взято из моей программы
"Картотека файлов". С другой стороны - мне
наплевать  на  то,  понял  ли  кто-то  ас-
семблерный  пример. Главное - уловить суть
идеи  быстрого  поиска,  понять технологию
приготовления  сего  шикарного блюда. Если
кому-то мой текст показался трудным, коро-
че,  если кто-то чего-то недопонял - читай
оригинал  в  книге "Современный компьютер"
издательства "Мир" за 1986 год. Старенькая
книжонция,  но  весьма  полезная.  На этом
позвольте  откланяться  -  я  устал и хочу
спать... Пока.                            
                                
Июль 1998 (С) MAX