Сборник по задачам и примерам Assembler

     

Прямой поиск в текстовой строке



Прямой поиск в текстовой строке

«Корень зла есть незнание истины», — сказал Будда.

Из этого же корня вырастает дерево заблуждения

со своими тысячными плодами страдания.

Цель поиска некоторой строки Р в строке большего размера S — определить первый индекс элемента в строке S, начиная с которого все символы S совпадают с символами строки Р. Для этого алгоритм поиска последовательно просматривает символы строки S, проводя одновременное сравнение ее очередного символа с первым символом строки Р. После возникновения такого совпадения алгоритм производит последовательное сравнение соответствующих элементов строк S и Р до возникновения одного из следующих условий:

  • в процессе поиска соответствия достигнут конец строки Р — это означает,

    что строка Р совпадает с некоторой подстрокой строки S;

  • достигнут конец строки S при незавершенном или неначатом просмотре строки Р — это означает, что строка Р не соответствует ни одна из подстрок S.
  • Одна из главных проблем, которую приходится решать при написании программы обработки символьной строки, — определение конца строки S. Здесь возможны два варианта:

  • статический — размер строки фиксирован некоторым значением N;
  • динамический (характерен для обработки массивов символьных строк) — длина строки определяется значением, являющимся либо первым элементом очередной строки, либо концевым (служебным) символом, значение которого заранее определено и не может совпадать ни с одним символом строки.
  • Начнем обсуждение прямого способа поиска с программы поиска в строке с фиксированной длиной. Для экономии места ограничим число вхождений Р в S рдним.

    ;prg4_67_f.asm - поиск строки Р в строке S, Длина S фиксирована.



    ;Вход: S и Р - массивы символов размером N и М байт (М=<N.
    :Выход: сообщение о количестве вхождений строки Р в строку S.

    '.data"

    :задаем массив S

    s db "Ax. какой был яркий день! Лодка, солнце, блеск и тень, и везде цвела сирень."

    Len_S=$-s

    Db "$" mes db "Вхождений строки - "

    :задаем массив Р - аргумент поиска


    р db "ень"

    1_еп_Р=$-р

    db " - " Count (Jb 0."$" :счетчик вхождений Р a S

    .code

    eld

    movcx.len_s

    lea di ,s

    moval ,p ;P[0]->al next_search:

    lea si,p

    incsi ;на следующий символ repne scasb

    jcxz exit push ex

    mov cx.len_p-l repe empsb

    jz eq_substr :строка p <> подстроке в s

    mov bx.len_p-l

    sub bx.cx pop ex

    subcx.bx ;учли пройденное при сравнении empsb

    jmp next_search eq_substr:

    ; далее можно выйти, если поиск однократный, но мы упорные, поэтому продолжаем... рорех

    sub сх.1еп_р-1 ;учли пройденное при сравнении empsb

    inc count

    jmp next_search exit: add count,30h :вывод сообщения mes на экран

    Из программы видно, что когда размер строки фиксирован, то проблема конца строки решается просто. Но чаще приходится иметь дело с задачами, выполняющими поиск подстроки в строке, длина которой заранее не известна. Это характерно, в частности, для приложений обработки файлов. Но и с файлами не так все просто. Для текстовых ASCII-файлов особых проблем нет — в них строки заканчиваются символами Odh, Oah. Сложнее дело обстоит с обработкой двоичных файлов, где с равной степенью вероятности могут встретиться любые символы кодовой таблицы. В подобных случаях проблему локализации места в файле, где осуществляется поиск, нужно решать исходя из постановки конкретной задачи. Несмотря на это, сами приемы поиска не сильно отличаются от рассмотренных в этом разделе.

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

    ¦ в памяти. Другая возможность задания границы строки — введение в структуру строки специального байта, обычно первого, содержащего длину этой строки.



    Следующая программа демонстрирует возможную организацию поиска в текстовом файле. Для этого содержимое файла читается в динамически выделяемую область памяти. После небольшой модернизации данную программу можно рассматривать как основу для других программ поиска в строках памяти, ограниченных некоторым служебным символом, как это обсуждалось выше. Программа производит поиск слова «шалтай» в строках файла. На экран выводится номер строки, в которой встретилось это слово, и количество повторений этого слова в файле. В такой постановке задачи возникает проблема — необходимо отслеживать наступление одного из двух событий: обнаружение первого символа образца или обнаружение первого из пары символов OdOah, обозначающих конец строки. Вариант использования цепочечных команд из предыдущей программы не подходит, так как сканировать строку можно на предмет наличия только одного символа. Поэтому данную задачу можно реализовать двумя способами. Первый способ заключается в последовательном чтении и проверке каждого символа строки на предмет удовлетворения их одному из обозначенных выше событий. При втором способе каждая строка файла сканируется два раза. На первом проходе определяется размер очередной строки, а затем эта строка сканируется второй раз на предмет наличия в ней искомой подстроки. Достоинство второго способа состоит в том, что его можно реализовать только использованием цепочечных команд. Какой из способов будет работать быстрее, можно определить с помощью профайлера. Мы выберем второй способ по двум причинам: во-первых, в этом разделе нас интересуют варианты использования цепочечных команд; во-вторых, в одной программе мы продемонстрируем приемы работы со строкой, размер которой определяется динамически двумя способами: со служебным символом в конце (им будет Odh) и извлекаемым из байта в начале строки. В нашей программе байт со значением длины очередной строки будет эмулироваться первым проходом.

    start proc near :точка входа в программу:

    ;для размещения файла используем кучу, выделяемую процессу по умолчанию (1 Мбайт)
    ;HANDLE GetProcessHeap (VOID);



    call GetProcessHeap

    inov Hand_Head.eax сохраняем дескриптор ;читаем файл в динамически выделяемую область памяти ;открываем файл

    :HANDLE CreateFiIeCLPCTSTR ipFileName.DWORD dwDesiredAccess.DWORD ;dwShareMode.LPSECURITY_ATTRIBUTES 1pSecuri tyAttributes.DWORD

    :dwCreationDisposition.DWORD :dwFlagsAndAttributes.HANDLE hTemplateFi1e):

    call CreateFileA

    cmp eax.Offffffffh

    je exit :если неуспех

    mov hFile.eax :дескриптор файла определим размер файла :DWORD GetFi1eSize(HANDLE hFile.LPDWORD ipFileSizeHigh);

    call GetFileSize

    cmp eax.O

    jz exit :если неуспех

    mov FileSize.eax :сохраним размер файла :запрашиваем блок памяти из кучи:

    :LPVOID HeapAlloc(HANDLE hHeap. DWORD dwFlags, DWORD dwBytes): ;.........

    call HeapAlloc

    mov buf_start,eax :адрес блока с текстом программы из общей кучи процесса :читаем файл

    :BOOL ReadFile(HANDLE hFile.LPVOID ipBuffer.DWORD nNumberOfBytesToRead. ;LPDWORD lpNumberOfBytesRead.LPOVERLAPPED lpOverlapped):

    :.........

    call ReadFile

    cmp eax.O

    jz exit :если неуспех push ds pop es

    eld

    mov ecx.FileSize

    movedi.buf_start :адрес буфера с текстом файла в edi cycll: push ecx push edi

    mov ebx.ecx

    moval.Odh :0dh ->al repne scasb

    jcxz e_exit

    jmp $+7 e_exit: jmp exit pop edi

    sub ebx.ecx

    xchg ebx.ecx

    mov al.p :P[0]->al next_search: repne scasb

    jcxz end_str:достигнут конец строки проверяем возможное совпадение

    push ecx lea esi.p

    mov ecx.len_p-l repe empsb

    jz eq_substr :строка р <> подстроке в s

    mov edx.len_p-l

    sub edx.ecx

    sub ecx.edx :учли пройденное при сравнении empsb

    jmp next_search end_str: incedi

    xchg ebx.ecx преобразуем в символьное представление счетчик вхождений count

    :вывод на экран строки mes call WriteConsoleA

    mov count.0 обнуляем счетчик вхождений в строку pop ecx :1 - восстанавливаем

    sub ecx.len_p-учли пройденное при сравнении empsb

    inc count

    jmp next_search

    exit: pop ecx

    ;выход из программы - задержим ввод до нажатия любой клавиши

    Этой программой мы проиллюстрировали оба варианта поиска с динамическим определением размера строки.

    Алгоритмы, реализованные в этих программах, можно использовать для организации поиска в строке S небольшой длины, так как попытки повысить эффективность приведут к излишним накладным расходам. Для строки S большой размерности (потоковые данные для приложений мультимедиа) прямые алгоритмы поиска могут быть неэффективными. Положение можно исправить рассмотренными ниже алгоритмами поиска с предварительным анализом искомой подстроки.

     

    Содержание раздела