Рефераты | Рефераты по информатике, программированию | Алгоритмы поиска в тексте | страница реферата 4 | Большая Энциклопедия Рефератов от А до Я
Большая Энциклопедия Рефератов от А до Я
  • Рефераты, курсовые, шпаргалки, сочинения, изложения
  • Дипломы, диссертации, решебники, рассказы, тезисы
  • Конспекты, отчеты, доклады, контрольные работы


    • Рефераты | Рефераты по информатике, программированию | Алгоритмы поиска в тексте


    Рефераты | Рефераты по информатике, программированию | Алгоритмы поиска в тексте

    Алгоритмы поиска в тексте




    Категория реферата: Рефераты по информатике, программированию
    Теги реферата: сочинение по английскому, реферат на
    Добавил(а) на сайт: Valentin.



    Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10 |



    Рефераты | Рефераты по информатике, программированию | Алгоритмы поиска в тексте 

    Заполнение таблицы начинается с последнего столбца. Самый правый столбец таблицы фактически соответствует массиву, который используется в упрощенном варианте алгоритма. Следующие столбцы содержат значения сдвига для образца при условии, что предыдущие (при движении справа налево) символы совпали. Проводя поиск при помощи этой таблицы, мы последовательно просматриваем значения ячеек, лежащих на пересечении столбца, соответствующего символу образца и строки, соответствующей символу текста. Просмотр начинается с последнего столбца. Если в каждом столбце выбранная ячейка содержит 0, значит, подстрока найдена. Если значение ячейки отличается от нуля, мы сдвигаем образец на соответствующее значение.

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

    Далее приводятся функции и определения, реализующие алгоритм для 256-символьного набора.

    type

      TIntVect = array [0..255] of Integer;

      TBMTable = array [0..0] of TIntVect;

      PBMTable = ^TBMTable;

    function FindRightmost( const S, P : String; 

      n : Integer) : Integer;

    var

      i, j, lp : Integer;

    begin

      Result := 0;

      lp := Length(P);

      if lp > n then Exit;

      for i := n - lp + 1 downto 1 do

      for j := 1 to lp do

      if P[j] <> S[i+j-1] then Break

      else if j = lp then

      begin

        Result := i;

        Exit;

      end;

    end;


    Рекомендуем скачать другие рефераты по теме: шпоры по праву, реферат по физкультуре.



    Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10 |




    Поделитесь этой записью или добавьте в закладки

       

    Категории:



    Разделы сайта




    •