Последовательное сравнение нескольких строк: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 23: | Строка 23: | ||
Чтобы избежать возвратов по ссылкам для несовпадений при вычислении этих ссылок, а также для обхода символов текста, для которых не был определен переход от корны на этапе поиска, к корню бора добавляется цикл для этих символов. В результате получаем механизм поиска совпадений с шаблонами или конечный автомат Ахо-Корасик (см. рис. 1). | Чтобы избежать возвратов по ссылкам для несовпадений при вычислении этих ссылок, а также для обхода символов текста, для которых не был определен переход от корны на этапе поиска, к корню бора добавляется цикл для этих символов. В результате получаем механизм поиска совпадений с шаблонами или конечный автомат Ахо-Корасик (см. рис. 1). | ||
[[Файл:SMSM_1.png]] | |||
Рисунок 1. Механизм поиска совпадений с шаблонами или конечный автомат Ахо-Корасик для множества строк {search, ear, arch, chart} | Рисунок 1. Механизм поиска совпадений с шаблонами или конечный автомат Ахо-Корасик для множества строк {search, ear, arch, chart} | ||
| Строка 39: | Строка 41: | ||
Алгоритм сравнения с помощью ОАГС является обобщением алгоритма BDM для точного сравнения строк. Он включает построение точной индексной структуры для обращенных строк P, такой как фактор-автомат или обобщенное суффиксное дерево, вместо протого бора, как в предыдущем варианте (см. рис. 2). Алгоритм в целом может быть сделан оптимальным за счет использования как индексной структуры для обращенных шаблонов, так и конечного автомата Ахо-Корасик для шаблонов. Поиск в этом случае включает сканирование некоторых фрагментов текста слева направо, а некоторых – справа налево. Это позволяет пропускать большие фрагменты текста T. | Алгоритм сравнения с помощью ОАГС (DAWG) является обобщением алгоритма BDM для точного сравнения строк. Он включает построение точной индексной структуры для обращенных строк P, такой как фактор-автомат или обобщенное суффиксное дерево, вместо протого бора, как в предыдущем варианте (см. рис. 2). Алгоритм в целом может быть сделан оптимальным за счет использования как индексной структуры для обращенных шаблонов, так и конечного автомата Ахо-Корасик для шаблонов. Поиск в этом случае включает сканирование некоторых фрагментов текста слева направо, а некоторых – справа налево. Это позволяет пропускать большие фрагменты текста T. | ||
[[Файл:SMSM_2.png]] | |||
Рисунок 2. Пример ОАГС | Рисунок 2. Пример ОАГС, индексной структуры, используемой для сравнения множества строк {search, ear, arch, chart}. Конечный автомат принимает обращенные префиксы строк | ||