Алгоритмы поиска в тексте
| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: сочинение по английскому, реферат на
| Добавил(а) на сайт: 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 | Следующая страница реферата Поделитесь этой записью или добавьте в закладки |
|
Главная