Из журнала 'Чёрная Ворона 2' Украина, Донецкая область, г.Дмитров-1, 08.1998 ---ОТКРЫТЫЕ ТЕХНОЛОГИИ--- БЫСТРЫЙ ПОИСК СЛОВА В ТЕКСТЕ. (C) 1998 MAX ------------------------------------------ Компьютером я обзавёлся в середине 1992 года. С начала я, как и все, наверное, си- дел исключительно на игрушках. Ну надо же совковый голод по передовым технологиям удалить. Так вот - вдоволь наигравшись во всевозможные игры (до сих пор люблю логи- ческие игрушки) начал понемногу посматри- вать во внутрь программ. Бейсиковых, ко- нечно. Как было интересно менять цвета, а потом и лоадеры. Медленно, но уверенно, приходили знания по ассемблеру. Язык так называемого высокого уровня, коим величают Бейсик, так и не знаю толком. Вернее, знаю, но пользоваться полноценно научиться не пришлось. Сразу полез "в дебри", о чём никогда не жалел. Начали появляться уже свои программки. Ещё тогда начала слажи- ваться традиция писать системный и прик- ладной софт. Я умышленно разделяю эти ка- тегории, т.к. многие ламеры ошибочно их мешают в единое целое. Ну да ладно, проехали. Однажды... Как банально звучит. Но однажды столкнулся с маленькой проблемой: нужно быстро и эффек- тивно найти что-то символьное в чём-то символьном. Короче, писалась как раз прог- рамма "Картотека файлов". Так вот там надо было найти имя файла по образцу. Ес- тественно, что делал поиск примитивным способом: перебирая и сравнивая все буквы попорядку. Для той программы это "тормоз- ное" действие особой роли не играло, но стало интересно придумать более умное ре- шение данной проблемы. Не успел. Подверну- лась под руку одна очень умная книга с интригующим названием "Современный компь- ютер". Я свой "Sintez" именно таким счи- тал, поэтому начал листать мудрённые статьи. И вот нашёл нужную статью на инте- ресующую тему. Но вот только ассемблерного примера для Z-80 там не было;-) Пришлось самому сочинять... Не слишком ли утомителен мой вступитель ный пасквиль? Знаю, молчу, каюсь. Итак, поехали. Не буду более много рас- сусоливать на тему что и как было - пере- ходим к делу, а по сему нудную часть из книги тоже пропускаю. Надо сектора на дис- ке экономить. Для начала рассмотрим пример "обычного" ламерского метода поиска, коим грешат даже ассы программирования. Иногда. Поиск слова в тексте осуществляется путём последова- тельных сравнений букв. Слово и текст яв- ляются массивами букв. Пример такого тек- ста, в котором ищем слово PICK: P E T E R P I P E R P I C K E D P E C K P I C K P I C K P I C K P I C K P I C K P I C K P I C K P I C K P I C K P I C K P I C K P I C K P I C K P I C K P I C K P I C K P I C K P I C K Как вы уже догадались - красным цветом выделены совпадения при поиске, а голубым несовпадения. Здесь наглядно видно утоми- тельность данного процесса для поиска. В примере условный текст содержит 20 букв, а слово 4 буквы. Слово считается найденным, когда все буквы совпали. Начинаем искать совпадения с начала текста. Первая буква слова сравнивается с первой буквой текста. Поскольку они совпали (красный цвет), сравниваются вторые буквы. На этот раз буквы не совпали (голубой цвет); следова- тельно, слово сдвигается на одну позицию вправо и проверка производится заново и с начала слова. И так до тех пор, пока все четыре буквы не совпадут. Мраки... Ассемблерный пример такого поиска нет никакого смысла приводить, т.к. это не яв- ляется целью статьи - ТОЛЬКО ПЕРЕДОВЫЕ И СОВЕРШЕННЫЕ ТЕХНОЛОГИИ В ЖИЗНЬ! Если кто желает, может найти такой пример в подав- ляющем большинстве прикладного софта, ра- ботающего с базами данных. Кто бы мог подумать, что спустя 30 лет после того, как были начаты исследования в области кибернетики, можно существенно и почти коренным образом улучшить метод ре- шения такой фундаментальной задачи, какой является поиск в тексте. Тем не менее в 1976 году Р. Бойер и Дж. Мур, работавшие в то время в Техасском университете в Остине нашли более быстрый способ. Их идея позво- ляет увеличить скорость поиска как минимум в два раза при каждом цикле программы. Сравнение слова с частью текста начинается от конца слова (помещаемого в начале тек- ста) и продолжается к его началу. Если проверяемая литера в слове не совпадает с соответствующей литерой текста, то слово двигается вправо относительно этой самой позиции, которую условно назовём опорной, до тех пор, пока какая-нибудь литера снова не совпадёт с литерой текста в этой пози- ции. Если этого не произойдёт, то слово сдвигается таким образом, чтобы его первая литера отстояла от опорной позиции на один интервал. Круто? Ещё бы! Сразу же возникает вопрос, как находят следующую совпавшую литеру, - ведь если для этого нужно сравнивать литеры по од- ной, то никакого выигрыша нет. Существует другой способ - завести таблицу расстояний от конца слова до последнего появления каждой буквы в этом слове. Конечно, нужно потратить определённое время на расчёт та- кой таблицы, но сделать это необходимо только один раз; если текст достаточно длинный, дело того стоит. По личному опыту уже убедился в этом. Возможно, что алгоритм Бойера и Мура работает быстрее, однако насколько можно быть уверенным в его правильности? В частности, как убедиться, что при сдвиге на несколько позиций вправо без попутных сравнений не было пропущено ни одной сов- падающей группы литер? Содержательное объ- яснение состоит в том, что для полного совпадения необходима идентичность всех пар литер, между тем, как группы, которые пропускаются, отличаются хотя бы в одной позиции, а именно в опорной позиции. Нельзя не учитывать ещё один немаловаж- ный ньюанс - в данном тексте слова может и не быть... Тогда следует "договориться", что необходимо знать размер слова и размер текста для определения по ходу дела ве- роятности совпадения. Если в процессе сдвига получается, что слово стало больше, чем остаток непроверенного текста, то де- лать там более нечего - нет такого слова! Теперь следует рассмотреть второй спо- соб на схеме, что сразу же позволит оце- нить его достоинства. Итак, PETER PIPER PICKED A PECK PECK PECK PECK PECK PECK PECK PECK PECK PECK PECK PECK PECK PECK Расчёт смещения в таблице, по которой надо делать пропуск при несоответствиях, происходит следующим образом: P E C K ? ? ?__ 1 ? ?____ 2 ?______ 3 Сама таблица вырабатывается из учёта размера слова, которое ищем в тексте, т.е. четыре символа: A.......4 B.......4 C_______1 D.......4 E_______2 F.......4 G.......4 H.......4 I.......4 J.......4 K_______4 L.......4 M.......4 N.......4 O.......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,H ;меров в нем OR L JR NZ,SENAME RET ;"NOT FOUND" ; EXECUT LD DE,(TEXT) ;откуда LD BC,8 ;длина CALL 8252 ;печать LD A,13 RST 16 RET ИНИЦИАЛИЗАЦИЯ ТАБЛИЦЫ ДЛЯ ПОИСКА Вызывается один раз перед поиском. ;-------------------------------------- INTABL LD HL,ZAG ;где образец LD DE,OBRAZ LD BC,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) ;конец образца CP #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 BC,95 ;несоответствия LD (HL),A ;step пропусканий LDIR LD HL,OBRAZ ;образец LD C,A ;его длина DEC C ;минус один на ADD HL,BC ;последний симв. LD (ENDOBR),HL;конец образца LD C,B ;C=0 LD B,A ;B=длина образца DJNZ MMM3 ;>1 JR MMM4 ;<1 MMM3 LD A,(HL) ;проверка совпаде- DEC HL ;ний рядом стоящих CP (HL) ;символов JR NZ,MMM5 DJNZ MMM3 LD HL,MASIV ;массив перескока LD DE,MASIV+1 ;заполнить 1 для LD BC,95 ;шага в единицу LD (HL),1 LDIR JR MMM4 MMM5 LD A,(IX+0) ;символ из образца SUB #20 ;корректируется к LD E,A ;0 для опр.шага LD D,C;C=0 ;при несовпадении LD HL,MASIV ;см.прим.! ADD HL,DE LD (HL),B ;шаг пропуска для INC IX ;каждой буквы DJNZ MMM5 ;по длине образа MMM4 RET ;конец операции ;или JP в цикл поиска... --------- ПРИМЕЧАНИЕ ------------- ;МММ5 делает поправку в массив при несо- ;ответствиях образца и данных в глобальном ;массиве для определения размера шага при ;оставлении несовпавшего фрагмента для ;каждой буквы из образца. ;--------------------------------------- ПОЛУЧЕНИЕ НОВОГО АДРЕСА ДЛЯ ПОИСКА ;--------------------------------------- ;in:HL,0 - номер строки в глоб. массиве SUMMA LD E,L LD D,H LD B,7 ;размер записи SUMM1 ADD HL,DE DJNZ SUMM1 LD BC,GMASS-8 ;адрес начала ГМ ADD HL,BC LD (TEXT),HL ;адрес для поиска RET ПОИСК В ГЛОБАЛЬНОМ МАССИВЕ ПО ОБРАЗЦУ ;---------------------------------------- POISK LD A,(NSIZE) ;размер образца DEC A ;стать на послед- PO1 LD (NSIZE+1),A;нюю букву LD HL,(TEXT) ;адрес в глоб.масс LD BC,(NSIZE) LD E,A LD D,#00 LD B,D ADD HL,DE ;стать на длину EX DE,HL ;образца в гл.масс LD HL,(ENDOBR);конец образца PO2 LD A,(DE) ;байт в гл.масс. CPD ;сверяется с образ JR NZ,PO3 ;не совпал DEC DE ;новый байт гл.мас RET PO ;конец проверки JR PO2 PO3 SUB 32 ;коррекция для пе- LD E,A ;рехода по массиву LD D,B ;оставления фрагм. LD HL,MASIV ADD HL,DE LD A,(NSIZE+1);откуда начал ADD A,(HL) ;сколько переск. CP 8 ;размер записи в ;глобал.массиве JR C,PO1 ;продолжить поиск OR A ;флаг Z=0 нет сов- RET ;падений ??????? СИСТЕМНЫЕ ПЕРЕМЕННЫЕ ПОИСКА ;--------------------------------------- TEXT 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 (C) MAX