Строковые операции . Символьные строки представляют основу большого количества источников, включающих научную, лингвистическую, специальную литературу и интернет. В качестве примера можно привести следующие строки. В этом разделе представлено несколько полезных операций, поддерживаемых строковым АТД при обработке строк. Несколько типичных операций для работы с текстом применяют разделение длинных строк на меньшие. Чтобы можно было оперировать результатами такого разделения, предлагаем использовать термин . В предельном случае это означает, что строка является подстрокой самое себя . Если требуется исключить такую возможность, следует ограничить определение правильной подстроки требованием, при котором либо . Для простоты будем использовать . Это означает, что . Будем считать, что . Чтобы различать особые виды подстрок, будем ссылаться на любую строку формата . Например, если вернуться к примеру строки Р как строки из ДНК. Заметим, что нулевая строка является префиксом и суффиксом любой строки. Строковые операции могут быть двух типов. Данное перечисление методов формирует набор типичных операций для неизменяемых строк. Рассмотрим следующий набор операций, выполняемых со строкой . устанавливает символу с индексом . возвращает символ с индексом . Ошибка возникает в случае, если индекс . Рассмотрим последовательность операций, выполняемых в изменяемой строке, первоначально имевшей вид . Таким образом, будем рассматривать методы класса . Алгоритмы шаблонного сопоставления В классической задаче сравнения с шаблоном . Следовательно, результатом алгоритма шаблонного согласования будет либо указание на то, что в Гнет Р, либо целое число, обозначающее индекс начала подстроки Р в Т. Это точное описание работы метода . Можно также определить все индексы, с которых начинается совпадение подстроки из Г со строкой Р. Чтобы сделать понятие символьной строки более универсальным, не ограничимся использованием только символов из хорошо известной таблицы типа . Вместо этого используем символ . Но поскольку большинство алгоритмов обработки текста используется в приложениях, применяющих указанные системы символов, исходим из того, что размерность алфавита . В этом разделе представлены три алгоритма сопоставления . Силовое решение Проектная модель алгоритма силового решения . Применение такой методики в обычных ситуациях сводится к перебору возможных конфигураций исходных данных и. Силовое шаблонное сопоставление При использовании этой методики для проектирования алгоритма силового шаблонного сопоставления . Этот алгоритм достаточно прост, смотрите фрагмент кода . Алгоритм силового шаблонного сопоставления Упростить алгоритм силового шаблонного сопоставления просто невозможно. Он состоит из двух вложенных циклов. Внешний цикл проходит все возможные индексы начала шаблона в тексте, внутренний цикл — все символы шаблона, сравнивая их с потенциальными символами текста. Таким образом, правильность алгоритма силового шаблонного сопоставления вытекает из такого тщательного поискового подхода. Производительность Нельзя сказать, однако, что время выполнения силового шаблонного сопоставления в наихудших случаях будет очень хорошим, так как для каждого символа . Следовательно, время выполнения метода силового согласования составит . Таким образом, в наихудшем случае, когда пит приблизительно равны, этот алгоритм имеет квадратичное время выполнения. Допустим, имеется текстовая строка Т . Видимо, автор допустил ошибку в рассуждениях. Обработка текста . ь а с . Пример выполнения алгоритма силового шаблонного согласования. Но только не в случае с алгоритмом Бойера. Следует только предупредить, что силовой алгоритм может работать даже с потенциально неограниченными словарями, в то время как БМ. Он работает быстрее, если алфавит имеет разумный размер, а шаблон достаточно велик. В этом разделе опишем упрощенный вариант оригинального алгоритма Бойера. Основной задачей БМ. Если с отсутствует в Р, . Формализуем вкратце эти эвристики, но интуитивно они воспринимаются как одно действие. Зеркальная эвристика настраивает вторую эвристику во избежание сравнений Рсо всеми группами символов в Т. По крайней мере, в этом случае можно ускорить просмотр, двигаясь в обратном направлении. Тогда, при обнаружении несоответствия при сопоставлении Р с некоторым местом в Т, возможно избежать излишних сравнений простым перемещением Р относительно Т с помощью эвристики пропуска символов. Применение этой эвристики наиболее эффективно, если Р сопоставляется с потенциальным местом его расположения в Т. Теперь перейдем к определению способа интегрирования эвристики пропуска символов в алгоритм шаблонного сопоставления строк. Для реализации этой эвристики определим функцию . Если символы используются в массиве в качестве индексов, то функция . Метод создания такой таблицы за . Во фрагменте кода . Стадия пропуска символов в БМ. Здесь различаются два случая. одну клетку Верное выполнение шаблонного алгоритма Бойера. И это связано с тем, что . При этом вычисление функции . В качестве примера такой пары . Однако для текста на английском языке наихудший случай маловероятен. а . Имеются экспериментальные свидетельства, что для английского текста среднее количество сравнений шаблона из пяти букв на один символ текста составляет примерно . Однако такая результативность недостаточна в случае с бинарными строками, где более приемлем КМП. Обработка текста а Р а . Обратите внимание, что не все символы текста проверяются на соответствие . Алгоритмы шаблонного сопоставления . Алгоритм выражен двумя статическими методами. Здесь приведен упрощенный вариант алгоритма Бойера. Оригинальный же вариант алгоритма обеспечивает время выполнения . В основу такой эвристики перемещения заложен принцип шаблонного алгоритма Кнута. В частности, можно произвести множество сравнительных операций при определении потенциального места расположения шаблона в тексте, при этом, если совпадающие символы не обнаруживаются, вся полученная в процессе сравнения информация отбрасываетсячи все начинается заново с нового отрезка текста.