Алгоритм поиска строк Бойера – Мура

Поиск строки Бойера – Мура
Сорт	Строковый поиск
Структура данных	Нить
Худшая производительность	Предварительная обработка Θ(m) + сопоставление O(mn)
Лучшая производительность	Предварительная обработка Θ(m) + сопоставление Ω(n/m)
Наихудшая пространственная сложность	Θ(к+м)

В информатике алгоритм поиска строк Бойера -Мура представляет собой эффективный алгоритм поиска строк , который является стандартным эталоном для практической литературы по поиску строк. ^{[ 1 ]} Он был разработан Робертом С. Бойером и Дж. Стротером Муром в 1977 году. ^{[ 2 ]} Исходная статья содержала статические таблицы для расчета сдвигов шаблона без объяснения того, как их производить. Алгоритм создания таблиц был опубликован в следующей статье; эта статья содержала ошибки, которые позже были исправлены Войцехом Риттером в 1980 году. ^{[ 3 ]}^{[ 4 ]}

Алгоритм предварительно обрабатывает искомую строку . (шаблон), но не искомую строку (текст) Таким образом, он хорошо подходит для приложений, в которых шаблон намного короче текста или где он сохраняется при многократном поиске. Алгоритм Бойера-Мура использует информацию, собранную на этапе предварительной обработки, для пропуска разделов текста, что приводит к более низкому постоянному коэффициенту, чем многие другие алгоритмы поиска строк. В общем, алгоритм работает быстрее с увеличением длины шаблона. Ключевыми особенностями алгоритма являются поиск совпадений по хвосту шаблона, а не по его началу, а также пропуск по тексту скачками по нескольким символам вместо поиска каждого отдельного символа в тексте.

Определения

А	Н	П	А	Н	М	А	Н	-
П	А	Н	-	-	-	-	-	-
-	П	А	Н	-	-	-	-	-
-	-	П	А	Н	-	-	-	-
-	-	-	П	А	Н	-	-	-
-	-	-	-	П	А	Н	-	-
-	-	-	-	-	П	А	Н	-

Выравнивание рисунка PAN по тексту ANPANMAN ,
от k=3 до k=8 . Соответствие происходит при k=5 .

T обозначает входной текст, который нужно найти. Его длина равна n .
P обозначает строку, которую нужно найти, называемую шаблоном . Его длина м .
S [ i ] обозначает символ с индексом i строки S , считая с 1.
S [ i .. j ] обозначает подстроку строки S, начинающуюся с индекса i и заканчивающуюся j включительно.
Префикс l S S подстрока — это [1.. i ] для некоторого i в диапазоне [1, , где l — длина S. ]
Суффиксом l S l является подстрока S [ i .. l ] для некоторого i в диапазоне [1, ] , где — длина S .
Выравнивание — P T по T индекс k в T такой, что последний символ P выравнивается по индексу k в это .
Совпадение если или появление P эквивалентно происходит при выравнивании k, P [ T - ( k . m +1).. k ]

Описание

Алгоритм Бойера-Мура ищет вхождения $P$ в $T$ , выполняя явное сравнение символов при разных выравниваниях. Вместо перебора всех раскладов (коих есть ⁠ $n-m+1$ ⁠ ), Бойер-Мур использует информацию, полученную в результате предварительной обработки $P$ , чтобы пропустить как можно больше выравниваний.

До появления этого алгоритма обычным способом поиска в тексте было изучение каждого символа текста на предмет первого символа шаблона. Как только это будет найдено, последующие символы текста будут сравниваться с символами шаблона. Если совпадений не обнаружено, текст снова проверяется посимвольно, чтобы найти совпадение. Таким образом, почти каждый символ в тексте нуждается в проверке.

Ключевая идея этого алгоритма заключается в том, что если конец шаблона сравнивается с текстом, то можно выполнять переходы по тексту, а не проверять каждый символ текста. Причина, по которой это работает, заключается в том, что при выравнивании шаблона по тексту последний символ шаблона сравнивается с символом в тексте. Если символы не совпадают, продолжать поиск назад по тексту нет необходимости. Если символ в тексте не соответствует ни одному из символов шаблона, то следующий проверяемый символ текста располагается $на m$ символов дальше по тексту, где $m$ — длина шаблона. Если символ в тексте находится в шаблоне, то производится частичный сдвиг шаблона по тексту для выравнивания по совпадающему символу и процесс повторяется. Прыжки по тексту для сравнения вместо проверки каждого символа в тексте уменьшают количество сравнений, которые необходимо выполнить, что является ключом к эффективности алгоритма.

Более формально, алгоритм начинается с выравнивания ⁠ $k=m$ ⁠ , поэтому начало $P$ совпадает с началом $T$ . Затем символы в $P$ и $T$ сравниваются, начиная с индекса $m$ в $P$ и $k$ в $T$ , двигаясь назад. Строки сопоставляются от конца $P$ до начала $P$ . Сравнения продолжаются до тех пор, пока либо не будет достигнуто начало $P$ (что означает совпадение), либо не произойдет несовпадение, при котором выравнивание смещается вперед (вправо) в соответствии с максимальным значением, разрешенным рядом правил. Сравнения выполняются снова при новом выравнивании, и процесс повторяется до тех пор, пока выравнивание не сместится за конец $T$ , что означает, что дальнейшие совпадения найдены не будут.

Правила сдвига реализованы как поиск в таблице с постоянным временем с использованием таблиц, сгенерированных во время предварительной обработки $P$ .

Правила смены

Сдвиг рассчитывается с применением двух правил: правила плохих символов и правила хорошего суффикса. Фактическое смещение переключения является максимальным из смещений, рассчитанных по этим правилам.

Правило плохого характера

Описание

-	-	-	-	Х	-	-	К	-	-	-
А	Н	П	А	Н	М	А	Н	А	М	-
-	Н	Н	А	А	М	А	Н	-	-	-
-	-	-	Н	Н	А	А	М	А	Н	-

Демонстрация правила плохого характера с образцом P = NNAAMAN . , имеется несоответствие между N (во входном тексте) и A (в шаблоне) В столбце, отмеченном X . следующее вхождение символа N (в шаблоне P ) слева от текущего символа (который является средним A ). Шаблон сдвигается вправо (в данном случае на 2), так что находится

Правило недопустимых символов учитывает символ в $T,$ на котором произошел сбой в процессе сравнения (при условии, что такой сбой произошел). Находится следующее вхождение этого символа слева в $P$ сдвиг, который приводит это вхождение в соответствие с несовпадающим вхождением в $T.$ и предлагается Если несовпадающий символ не встречается слева в $P$ , предлагается сдвиг, который перемещает весь $P$ за точку несовпадения.

Предварительная обработка

Методы различаются в зависимости от того, какую именно форму должна принимать таблица для правила недопустимых символов, но простое решение поиска с постоянным временем заключается в следующем: создайте двумерную таблицу, которая индексируется сначала индексом символа $c$ в алфавите, а затем индексом индекс $i$ в шаблоне. Этот поиск вернет вхождение $c$ в $P$ со следующим по величине индексом ⁠ $j<i$ ⁠ или -1, если такого события нет. Тогда предлагаемый сдвиг будет ⁠ $i-j$ ⁠ , с ⁠ $O(1)$ ⁠ время поиска и ⁠ $O(km)$ ⁠ пространство, предполагая конечный алфавит длины $k$ .

Реализации C и Java, приведенные ниже, имеют ⁠ $O(k)$ ⁠ сложность пространства (make_delta1, makeCharTable). Это то же самое, что исходная delta1 и таблица недопустимых символов BMH . Эта таблица отображает символ в позиции ⁠. $i$ ⁠ сдвинуть на ⁠ $\operatorname {len} (p)-1-i$ ⁠ , причем последний экземпляр (наименьшая сумма смещения) имеет приоритет. Все неиспользуемые символы установлены как ⁠. $\operatorname {len} (p)$ ⁠ как контрольное значение.

Правило хорошего суффикса

Описание

-

Х

-

К

-

М

А

Н

П

А

Н

А

М

А

Н

А

П

-

А

Н

А

М

П

Н

А

М

-

А

Н

А

М

П

Н

А

М

-

Демонстрация правила хорошего суффикса с шаблоном P = ANAMPNAM . Здесь t представляет собой T [6..8], а t ′ представляет собой P [2..4].

Правило хороших суффиксов значительно сложнее как по концепции, так и по реализации, чем правило плохих символов. Как и правило плохих символов, оно также использует особенность алгоритма, заключающуюся в том, что сравнения начинаются с конца шаблона и продолжаются к его началу. Его можно описать следующим образом: ^{[ 5 ]}

Предположим, что для данного выравнивания P и T подстрока t из T соответствует суффиксу P и предположим, что t является самой большой такой подстрокой для данного выравнивания.

Затем найдите, если она существует, самую правую копию t ′ слова t в P такую, что t ′ не является суффиксом P и символ слева от t ′ в P отличается от символа слева от t в P . Сдвиньте P вправо так, чтобы подстрока t ′ в P совпала с подстрокой t в T .

Если t ′ не существует, то сдвиньте левый конец P вправо на наименьшую величину (за левый конец t в T ), чтобы префикс сдвинутого шаблона соответствовал суффиксу t в T . Сюда входят случаи, когда t является точным совпадением P .

Если такой сдвиг невозможен, то сдвиньте P на m (длину P) мест вправо.

Предварительная обработка

Правило хорошего суффикса требует наличия двух таблиц: одну для использования в общем случае (когда найдена копия t ′ ), а другую для использования, когда общий случай не возвращает значимого результата. Эти таблицы будут обозначаться $L$ и $H$ соответственно. Их определения следующие: ^{[ 5 ]}

Для каждого $i$ , ⁠ $L[i]$ ⁠ — это наибольшая позиция меньше $m,$ такая что строка ⁠ $P[i..m]$ ⁠ соответствует суффиксу ⁠ $P[1..L[i]]$ ⁠ и такой, что символ, предшествующий этому суффиксу, не равен ⁠ $P[i-1]$ ⁠ . ⁠ $L[i]$ ⁠ определяется как ноль, если нет позиции, удовлетворяющей условию.

Пусть ⁠ $H[i]$ ⁠ обозначает длину наибольшего суффикса ⁠ $P[i..m]$ ⁠ это также префикс $P$ , если он существует. Если такового не существует, пусть ⁠ $H[i]$ ⁠ быть нулевым.

Обе эти таблицы можно построить в ⁠ $O(m)$ ⁠ время и использование ⁠ $O(m)$ ⁠ космос. Сдвиг выравнивания для индекса $i$ в $P$ определяется выражением ⁠ $m-L[i]$ ⁠ или ⁠ $m-H[i]$ ⁠ . $H$ следует использовать только в том случае, если ⁠ $L[i]$ ⁠ равен нулю или совпадение найдено.

Пример смены с использованием шаблона ANPANMAN

Index| Mismatch | Shift   
 0   |         N|   1    
 1   |        AN|   8    
 2   |       MAN|   3    
 3   |      NMAN|   6   
 4   |     ANMAN|   6   
 5   |    PANMAN|   6  
 6   |   NPANMAN|   6  
 7   |  ANPANMAN|   6

Объяснение:

Индекс 0, совпадений нет, прочитанный символ не был N. Длина хорошего суффикса равна нулю. Поскольку в шаблоне много букв, которые тоже не являются N, информации у нас здесь минимум — сдвиг на 1 — наименее интересный результат.

В Idnex 1 мы сопоставили N, и ему предшествовало что-то отличное от A. Теперь посмотрите на шаблон, начиная с конца, где у нас N предшествует что-то кроме A? Есть еще две N, но обеим предшествует A. Это означает, что никакая часть хорошего суффикса не может быть нам полезна — сдвиг на полную длину шаблона 8.

Индекс 2: Мы сопоставили AN, и ему предшествовал не M. В середине шаблона находится AN, которому предшествует P, поэтому он становится кандидатом на сдвиг. Сдвиг AN вправо, чтобы он соответствовал нашему совпадению, — это сдвиг на 3.

Индекс 3 и выше: совпадающие суффиксы не соответствуют ничему другому в шаблоне, но конечный суффикс AN соответствует началу шаблона, поэтому все сдвиги здесь равны 6. ^{[ 6 ]}

Правило Галила

Простая, но важная оптимизация Бойера-Мура была предложена Цви Галилом в 1979 году. ^{[ 7 ]} В отличие от смещения, правило Галила направлено на ускорение фактического сравнения, выполняемого при каждом выравнивании, за счет пропуска разделов, которые, как известно, совпадают. что при выравнивании $k 1$ Предположим , $P$ сравнивается с $T$ вплоть до символа $c$ из $T$ . Затем, если $P$ сдвигается на $k 2$ так, что его левый конец находится между $c$ и $k 1$ , на следующей фазе сравнения префикс $P$ должен соответствовать подстроке $T [(k 2 - n).. k 1]$ . Таким образом, если сравнения доходят до позиции $k 1$ в $T$ , появление $P$ может быть записано без явного сравнения прошлого $k 1$ . Помимо повышения эффективности Бойера-Мура, правило Галила необходимо для доказательства выполнения за линейное время в худшем случае.

Правило Галила в его исходной версии действует только для версий, выдающих несколько совпадений. Он обновляет диапазон подстроки только при $c = 0$ , то есть при полном совпадении. Обобщенная версия для работы с подсовпадениями была представлена в 1985 году как алгоритм Апостолико-Джанкарло . ^{[ 8 ]}

Производительность

Алгоритм Бойера-Мура, представленный в оригинальной статье, имеет время работы в наихудшем случае ⁠. $O(n+m)$ ⁠ только если шаблон не встречается в тексте. Впервые это было доказано Кнутом , Моррисом и Праттом в 1977 году. ^{[ 3 ]} за ним последовали Гибас и Одлызко в 1980 году. ^{[ 9 ]} с верхней границей в $5 n$ сравнений в худшем случае. Ричард Коул дал доказательство с верхней границей $3 n$ сравнений в худшем случае в 1991 году. ^{[ 10 ]}

Когда шаблон встречается в тексте, время работы исходного алгоритма составляет ⁠ $O(nm)$ ⁠ в худшем случае. Это легко увидеть, когда и шаблон, и текст состоят исключительно из одного и того же повторяющегося символа. Однако включение правила Галила приводит к линейному времени выполнения во всех случаях. ^{[ 7 ]}^{[ 10 ]}

Реализации

На разных языках программирования существуют различные реализации. В C++ он является частью стандартной библиотеки, поскольку C++17 и Boost предоставляют общую реализацию поиска Бойера-Мура в библиотеке алгоритмов . В Go (языке программирования) есть реализация в search.go . D (язык программирования) использует BoyerMooreFinder для сопоставления на основе предикатов внутри диапазонов как часть библиотеки времени выполнения Phobos.

Алгоритм Бойера-Мура также используется GNU grep в . ^{[ 11 ]}

Варианты

Алгоритм Бойера -Мура-Хорспула представляет собой упрощение алгоритма Бойера-Мура, использующее только правило недопустимых символов.

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

Алгоритм Райта повышает производительность алгоритма Бойера – Мура – Хорспула. Шаблон поиска конкретной подстроки в данной строке отличается от алгоритма Бойера – Мура – Хорспула.

Примечания

^ m — длина строки шаблона, которую мы ищем в тексте, длиной n . Эта среда выполнения предназначена для поиска всех вхождений шаблона без применения правила Галила.
^ k — размер алфавита. Это пространство предназначено для исходной таблицы недопустимых символов delta1 в реализациях C и Java, а также таблицы хороших суффиксов.

Ссылки

^ Хьюм, Эндрю; Воскресенье, Дэниел (ноябрь 1991 г.). «Быстрый поиск строки». Программное обеспечение: практика и опыт . 21 (11): 1221–1248. дои : 10.1002/спе.4380211105 . S2CID 5902579 .
^ Бойер, Роберт С .; Мур, Дж. Стротер (октябрь 1977 г.). «Алгоритм быстрого поиска строк» . Комм. АКМ . 20 (10). Нью-Йорк: Ассоциация вычислительной техники: 762–772. дои : 10.1145/359842.359859 . ISSN 0001-0782 . S2CID 15892987 .
^ Jump up to: ^а ^б Кнут, Дональд Э .; Моррис, Джеймс Х. младший ; Пратт, Воган Р. (1977). «Быстрое сопоставление с образцом в строках» . SIAM Journal по вычислительной технике . 6 (2): 323–350. CiteSeerX 10.1.1.93.8147 . дои : 10.1137/0206024 . ISSN 0097-5397 .
^ Риттер, Войцех (1980). «Правильный алгоритм предварительной обработки для поиска строк Бойера – Мура». SIAM Journal по вычислительной технике . 9 (3): 509–512. дои : 10.1137/0209037 . ISSN 0097-5397 .
^ Jump up to: ^а ^б Гасфилд, Дэн (1999) [1997], «Глава 2 - Точное сопоставление: классические методы, основанные на сравнении», Алгоритмы для строк, деревьев и последовательностей (1-е изд.), Cambridge University Press, стр. 19–21, ISBN 0-521-58519-8
^ «Построение хорошей таблицы суффиксов — понимание примера» . Переполнение стека . 11 декабря 2014 года . Проверено 30 июля 2024 г. В эту статью включен текст из этого источника, доступного по лицензии CC BY-SA 3.0 .
^ Jump up to: ^а ^б Галил, З. (сентябрь 1979 г.). «Об улучшении времени работы алгоритма сопоставления строк Бойера – Мура в наихудшем случае» . Комм. АКМ . 22 (9). Нью-Йорк: Ассоциация вычислительной техники: 505–508. дои : 10.1145/359146.359148 . ISSN 0001-0782 . S2CID 1333465 .
^ Апостолико, Альберто; Джанкарло, Рафаэле (февраль 1986 г.). «Возвращение к стратегиям поиска строк Бойера-Мура-Галиля» . SIAM Journal по вычислительной технике . 15 : 98–105. дои : 10.1137/0215007 .
^ Гибас, Леонидас ; Одлыжко, Андрей (1977). «Новое доказательство линейности алгоритма поиска строк Бойера – Мура» . Материалы 18-го ежегодного симпозиума по основам информатики . СФКС '77. Вашингтон, округ Колумбия: Компьютерное общество IEEE: 189–195. дои : 10.1109/SFCS.1977.3 . S2CID 6470193 .
^ Jump up to: ^а ^б Коул, Ричард (сентябрь 1991 г.). «Жесткие границы сложности алгоритма сопоставления строк Бойера – Мура» . Материалы 2-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Газировка 91 года. Филадельфия, Пенсильвания: Общество промышленной и прикладной математики: 224–233. ISBN 0-89791-376-0 .
^ Хертель, Майк (21 августа 2010 г.). «почему GNU grep работает быстро» . Архив текущего списка рассылки FreeBSD .

Внешние ссылки

Оригинальная статья об алгоритме Бойера-Мура
Пример алгоритма Бойера-Мура с домашней страницы Дж. Стротера Мура , соавтора алгоритма.
Статья Ричарда Коула 1991 года, доказывающая линейность во время выполнения

[1] — длина строки шаблона, которую мы ищем в тексте, длиной n . Эта среда выполнения предназначена для поиска всех вхождений шаблона без применения правила Галила.

[2] — размер алфавита. Это пространство предназначено для исходной таблицы недопустимых символов delta1 в реализациях C и Java, а также таблицы хороших суффиксов.

[3] Хьюм, Эндрю; Воскресенье, Дэниел (ноябрь 1991 г.). «Быстрый поиск строки». Программное обеспечение: практика и опыт . 21 (11): 1221–1248. дои : 10.1002/спе.4380211105 . S2CID 5902579 .

[original-4] Бойер, Роберт С .; Мур, Дж. Стротер (октябрь 1977 г.). «Алгоритм быстрого поиска строк» . Комм. АКМ . 20 (10). Нью-Йорк: Ассоциация вычислительной техники: 762–772. дои : 10.1145/359842.359859 . ISSN 0001-0782 . S2CID 15892987 .

[Knuth_Morris_Pratt-5] Jump up to: ^а ^б Кнут, Дональд Э .; Моррис, Джеймс Х. младший ; Пратт, Воган Р. (1977). «Быстрое сопоставление с образцом в строках» . SIAM Journal по вычислительной технике . 6 (2): 323–350. CiteSeerX 10.1.1.93.8147 . дои : 10.1137/0206024 . ISSN 0097-5397 .

[Rytter1980-6] Риттер, Войцех (1980). «Правильный алгоритм предварительной обработки для поиска строк Бойера – Мура». SIAM Journal по вычислительной технике . 9 (3): 509–512. дои : 10.1137/0209037 . ISSN 0097-5397 .

[ASTS-7] Jump up to: ^а ^б Гасфилд, Дэн (1999) [1997], «Глава 2 - Точное сопоставление: классические методы, основанные на сравнении», Алгоритмы для строк, деревьев и последовательностей (1-е изд.), Cambridge University Press, стр. 19–21, ISBN 0-521-58519-8

[8] «Построение хорошей таблицы суффиксов — понимание примера» . Переполнение стека . 11 декабря 2014 года . Проверено 30 июля 2024 г. В эту статью включен текст из этого источника, доступного по лицензии CC BY-SA 3.0 .

[galil-9] Jump up to: ^а ^б Галил, З. (сентябрь 1979 г.). «Об улучшении времени работы алгоритма сопоставления строк Бойера – Мура в наихудшем случае» . Комм. АКМ . 22 (9). Нью-Йорк: Ассоциация вычислительной техники: 505–508. дои : 10.1145/359146.359148 . ISSN 0001-0782 . S2CID 1333465 .

[10] Апостолико, Альберто; Джанкарло, Рафаэле (февраль 1986 г.). «Возвращение к стратегиям поиска строк Бойера-Мура-Галиля» . SIAM Journal по вычислительной технике . 15 : 98–105. дои : 10.1137/0215007 .

[go-11] Гибас, Леонидас ; Одлыжко, Андрей (1977). «Новое доказательство линейности алгоритма поиска строк Бойера – Мура» . Материалы 18-го ежегодного симпозиума по основам информатики . СФКС '77. Вашингтон, округ Колумбия: Компьютерное общество IEEE: 189–195. дои : 10.1109/SFCS.1977.3 . S2CID 6470193 .

[cole-12] Jump up to: ^а ^б Коул, Ричард (сентябрь 1991 г.). «Жесткие границы сложности алгоритма сопоставления строк Бойера – Мура» . Материалы 2-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Газировка 91 года. Филадельфия, Пенсильвания: Общество промышленной и прикладной математики: 224–233. ISBN 0-89791-376-0 .

[13] Хертель, Майк (21 августа 2010 г.). «почему GNU grep работает быстро» . Архив текущего списка рассылки FreeBSD .

[ примечание 1 ]

[ примечание 2 ]

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

v т и Струны
Строковая метрика	Примерное соответствие строк Алгоритм битап Расстояние Дамерау – Левенштейна Изменить расстояние Сопоставление гештальт-образцов Расстояние Хэмминга Расстояние Яро – Винклера Расстояние Ли Автомат Левенштейна Расстояние Левенштейна Алгоритм Вагнера-Фишера
Алгоритм поиска строк	Алгоритм Апостола – Джанкарло Алгоритм поиска строк Бойера – Мура Алгоритм Бойера – Мура – Хорспула Алгоритм Кнута – Морриса – Пратта Алгоритм Рабина – Карпа Алгоритм Райта Триграммный поиск Алгоритм двустороннего сопоставления строк Алгоритм сопоставления строк Чжу – Такаока
Поиск нескольких строк	Ахо – Корасик Алгоритм Комментца-Вальтера
Регулярное выражение	Сравнение механизмов регулярных выражений Регулярная грамматика Конструкция Томпсона Недетерминированный конечный автомат
Выравнивание последовательности	ВЗРЫВ Алгоритм Хиршберга Алгоритм Нидлмана – Вунша Алгоритм Смита – Уотермана
Структура данных	ДАФСА Суффиксный массив Суффиксный автомат Суффиксное дерево Обобщенное суффиксное дерево Веревка Тернарное дерево поиска Три
Другой	Разбор Сопоставление с образцом Сопоставление сжатого шаблона Самая длинная общая подпоследовательность Самая длинная общая подстрока Последовательный анализ шаблонов Сортировка Системы перезаписи строк Строковые операции