Изменить расстояние

В лингвистике и информатике компьютерной расстояние редактирования — это строковая метрика , т. е. способ количественной оценки того, насколько две строки (например, слова) различны друг с другом, который измеряется путем подсчета минимального количества операций, необходимых для преобразования одной строки в другой. Расстояния редактирования находят применение в обработке естественного языка , где автоматическая коррекция орфографии может определять возможные исправления для слова с ошибкой, выбирая из словаря слова, которые имеют небольшое расстояние до рассматриваемого слова. В биоинформатике его можно использовать для количественной оценки сходства последовательностей ДНК , которые можно рассматривать как строки букв A, C, G и T.

Различные определения расстояния редактирования используют разные наборы подобных операций. Операции расстояния Левенштейна — это удаление, вставка или замена символа в строке. Будучи наиболее распространенной метрикой, термин « расстояние Левенштейна» часто используется как синоним расстояния редактирования . ^[1]

Типы расстояния редактирования [ править ]

Различные типы расстояния редактирования позволяют использовать разные наборы операций со строками. Например:


Алгоритм	Разрешенные операции
	Вставки	Удаление	Замены	Транспонирование
Расстояние Левенштейн	✓	✓	✓
Самая длинная общая подпоследовательность (LCS)	✓	✓
Расстояние Хэмминга			✓
Расстояние Дамерау–Левенштейн	✓	✓	✓	✓
Через год				✓

Некоторые расстояния редактирования определяются как параметризуемая метрика, рассчитанная с использованием определенного набора разрешенных операций редактирования, и каждой операции назначается стоимость (возможно, бесконечная). Это дополнительно обобщается с помощью алгоритмов выравнивания последовательностей ДНК, таких как алгоритм Смита-Уотермана , в которых стоимость операции зависит от того, где она применяется.

Формальное определение и свойства [ править ]

Учитывая две строки $a$ и $b$ в алфавите $Σ$ (например, набор символов ASCII , набор байтов [0..255] и т. д.), расстояние редактирования d( $a$ , $b$ ) является серией редактирования с минимальным весом. операции, преобразующие $a$ в $b$ . Один из простейших наборов операций редактирования — тот, который был определен Левенштейном в 1966 году: ^[2]

Вставка одного символа. Если

a

=

u

v

, то вставка символа

x

дает

u

x

v

. Это также можно обозначить ε→

x

, используя ε для обозначения пустой строки.

Удаление одного символа меняет

u

x

v

на

u

v

(

x

→ε).

Замена одного символа

x

на символ

y

≠

x

меняет

u

x

v

на

u

y

v

(

x

→

y

).

В исходном определении Левенштейна каждая из этих операций имеет стоимость единицы (за исключением того, что замена символа сама по себе имеет нулевую стоимость), поэтому расстояние Левенштейна равно минимальному количеству операций, необходимых для преобразования $a$ в $b$ . неотрицательные весовые функции $w$ _ins ( $x$ ), $w$ _del ( $x$ ) и $w$ _sub ( $x$ , $y ).$ Более общее определение связывает с операциями ^[2]

Были предложены дополнительные примитивные операции. Расстояние Дамерау-Левенштейна считается одним редактированием (распространенная ошибка: транспонирование двух соседних символов, формально характеризующееся операцией, которая меняет $u$ $x$ $y$ $v$ на $u$ $y$ $x$ $v )$ . ^[3]^[4]Для задачи исправления OCR вывода использовались операции слияния и разделения , которые заменяют один символ парой или наоборот. ^[4]

Другие варианты дистанции редактирования получаются за счет ограничения набора операций. Самое длинное расстояние общей подпоследовательности (LCS) — это расстояние редактирования, в котором вставка и удаление являются единственными двумя операциями редактирования, обе по стоимости за единицу. ^[1]^: 37 Аналогичным образом, допуская только замены (опять же по стоимости единицы), расстояние Хэмминга получается ; это должно быть ограничено строками одинаковой длины. ^[1]Расстояние Яро – Винклера можно получить из расстояния редактирования, где разрешены только транспозиции.

Пример [ править ]

между Расстояние Левенштейна «котёнком» и «сидением» равно 3. Минимальный сценарий редактирования, преобразующий первое во второе:

k itten → s itten (замените «k» на «s»)
sitt e n → sitt i n (замените «e» на «i»)
сидеть → сидеть г (вставить «г» в конце)

Расстояние LCS (только вставки и удаления) дает другое расстояние и минимальный сценарий редактирования:

k itten → itten (удалить «k» в цифре 0)
itten → s itten (вставьте «s» в 0)
sitt e n → sittn (удалить «e» в цифре 4)
sittn → sitt i n (вставьте «i» в цифру 4)
сидеть → сидеть г (вставить «г» в цифре 6)

общая стоимость/расстояние 5 операций.

Свойства [ править ]

Расстояние редактирования с неотрицательной стоимостью удовлетворяет аксиомам метрики , создавая метрическое пространство строк, когда выполняются следующие условия: ^[1]^: 37

Каждая операция редактирования имеет положительную стоимость;
для каждой операции существует обратная операция с равной стоимостью.

Благодаря этим свойствам метрические аксиомы выполняются следующим образом:

d

(

a

,

b

) = 0 тогда и только тогда, когда a=b, поскольку каждую строку можно тривиально преобразовать в саму себя, используя ровно ноль операций.

d

(

a

,

b

) > 0, когда

a

≠

b

, поскольку для этого потребуется хотя бы одна операция с ненулевой стоимостью.

d

(

a

,

b

) =

d

(

b

,

a

) в силу равенства стоимости каждой операции и ее обратной.

Неравенство треугольника:

d

(

a

,

c

) ≤

d

(

a

,

b

) +

d

(

b

,

c

). ^[5]

Расстояние Левенштейна и расстояние LCS с удельной стоимостью удовлетворяют вышеуказанным условиям и, следовательно, метрическим аксиомам. В литературе также рассматривались варианты расстояния редактирования, которые не являются собственными метриками. ^[1]

Другие полезные свойства расстояний редактирования удельной стоимости включают в себя:

Расстояние LCS ограничено сверху суммой длин пары строк. ^[1]^: 37
Расстояние LCS является верхней границей расстояния Левенштейна.
Для строк одинаковой длины расстояние Хэмминга является верхней границей расстояния Левенштейна. ^[1]

Независимо от стоимости/веса, для всех расстояний редактирования сохраняется следующее свойство:

Если $a$ и $b$ имеют общий префикс, этот префикс не влияет на расстояние. Формально, когда $a$ = $uv$ и $b$ = $uw$ , тогда $d$ ( $a$ , $b$ ) = $d$ ( $v$ , $w$ ). ^[4] Это позволяет ускорить многие вычисления, связанные с расстоянием редактирования и сценариями редактирования, поскольку общие префиксы и суффиксы можно пропускать за линейное время.

Вычисление [ править ]

Первый алгоритм вычисления минимального расстояния редактирования между парой строк был опубликован Дамерау в 1964 году. ^[6]

Общий алгоритм [ править ]

Используя оригинальные операции Левенштейна, (несимметричное) расстояние редактирования от $a=a_{1}\ldots a_{m}$ к $b=b_{1}\ldots b_{n}$ дается $d_{mn}$ , определяемый повторением ^[2]

{\begin{aligned}d_{i0}&=\sum _{k=1}^{i}w_{\mathrm {del} }(a_{k}),&&\quad {\text{for}}\;1\leq i\leq m\\d_{0j}&=\sum _{k=1}^{j}w_{\mathrm {ins} }(b_{k}),&&\quad {\text{for}}\;1\leq j\leq n\\d_{ij}&={\begin{cases}d_{i-1,j-1}&{\text{for}}\;a_{i}=b_{j}\\\min {\begin{cases}d_{i-1,j}+w_{\mathrm {del} }(a_{i})\\d_{i,j-1}+w_{\mathrm {ins} }(b_{j})\\d_{i-1,j-1}+w_{\mathrm {sub} }(a_{i},b_{j})\end{cases}}&{\text{for}}\;a_{i}\neq b_{j}\end{cases}}&&\quad {\text{for}}\;1\leq i\leq m,1\leq j\leq n.\end{aligned}}

Этот алгоритм можно обобщить для обработки транспозиций, добавив еще один термин в минимизацию рекурсивного предложения. ^[3]

Прямой рекурсивный способ оценки повторения требует экспоненциального времени . Поэтому он обычно вычисляется с использованием алгоритма динамического программирования , авторство которого обычно приписывают Вагнеру и Фишеру . ^[7] хотя он имеет историю множества изобретений. ^[2]^[3]После завершения алгоритма Вагнера-Фишера минимальная последовательность операций редактирования может быть считана как обратная трассировка операций, используемых в алгоритме динамического программирования, начиная с $d_{mn}$ .

Этот алгоритм имеет временную сложность Θ( $m$ $n$ ), где $m$ и $n$ — длины строк. Когда полная таблица динамического программирования построена, ее пространственная сложность также равна Θ( $m$ $n$ ) ; это можно улучшить до Θ(min( $m$ , $n$ )), заметив, что в любой момент алгоритму требуется только две строки (или два столбца) в памяти. Однако такая оптимизация делает невозможным считывание минимальной серии операций редактирования. ^[3] Решение этой проблемы в линейном пространстве предлагает алгоритм Хиршберга . ^[8]^: 634 Общая рекурсивная структура «разделяй и властвуй» для решения таких повторений и извлечения оптимальной последовательности операций с эффективностью кэширования в пространстве, линейном по размеру входных данных, предложена Чоудхури, Ле и Рамачандраном. ^[9]

Улучшенные алгоритмы [ править ]

Улучшая описанный выше алгоритм Вагнера-Фишера, Укконен описывает несколько вариантов: ^[10] один из которых принимает две строки и максимальное расстояние редактирования $s$ и возвращает min( $s$ , $d$ ) . Это достигается за счет вычисления и сохранения только части таблицы динамического программирования вокруг ее диагонали. Этот алгоритм требует времени O( $s$ ×min( $m$ , $n$ )) , где $m$ и $n$ — длины строк. Пространственная сложность равна O( $s$ ²) или O( $s$ ) в зависимости от того, нужно ли считывать последовательность редактирования. ^[3]

Дальнейшие улучшения Ландау , Майерса и Шмидта [1] дают O( $s$ ² + max( $m$ , $n$ )) алгоритм времени. ^[11]

Для конечного алфавита и затрат на редактирование, которые кратны друг другу, самый быстрый известный точный алгоритм принадлежит Масеку и Патерсону. ^[12] время выполнения в худшем случае составляет O (нм/logn).

Приложения [ править ]

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

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

Алгоритм Хиршберга вычисляет оптимальное выравнивание двух строк, где оптимальность определяется как минимизация расстояния редактирования.
Приблизительное соответствие строк можно определить с точки зрения расстояния редактирования. Алгоритм Укконена 1985 года принимает строку $p$ , называемую шаблоном, и константу $k$ ; затем он строит детерминированный конечный автомат , который находит в произвольной строке $s$ подстроку, расстояние редактирования которой до $p$ не превышает $k.$ ^[13] (ср. алгоритм Ахо-Корасика , который аналогичным образом конструирует автомат для поиска любого из множества шаблонов, но не допускает операций редактирования). Аналогичным алгоритмом приблизительного сопоставления строк является битовый алгоритм , также определяемый с точки зрения расстояния редактирования.
Автоматы Левенштейна — это конечные автоматы, которые распознают набор строк на ограниченном расстоянии редактирования фиксированной ссылочной строки. ^[4]

Расстояние редактирования языка [ изменить ]

Обобщением расстояния редактирования между строками является расстояние редактирования языка между строкой и языком, обычно формальным языком . Вместо того, чтобы учитывать расстояние редактирования между одной строкой и другой, расстояние редактирования языка — это минимальное расстояние редактирования, которое может быть достигнуто между фиксированной строкой и любой строкой, взятой из набора строк. Более формально, для любого языка L и строки x в алфавите $Σ$ d расстояние редактирования языка ( L , x ) определяется выражением ^[14] $d(L,x)=\min _{y\in L}d(x,y)$ , где $d(x,y)$ расстояние редактирования строки. Когда язык L является контекстно-свободным , существует алгоритм динамического программирования кубического времени, предложенный Ахо и Петерсоном в 1972 году, который вычисляет расстояние редактирования языка. ^[15] Для менее выразительных семейств грамматик, таких как обычные грамматики , существуют более быстрые алгоритмы вычисления расстояния редактирования. ^[16]

Расстояние языкового редактирования нашло множество разнообразных применений, таких как сворачивание РНК, исправление ошибок и решение проблемы генерации оптимального стека. ^[14]^[17]

См. также [ править ]

Ссылки [ править ]

^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Наварро, Гонсало (1 марта 2001 г.). «Экскурсия по приблизительному сопоставлению строк» (PDF) . Обзоры вычислительной техники ACM . 33 (1): 31–88. CiteSeerX 10.1.1.452.6317 . дои : 10.1145/375360.375365 . S2CID 207551224 . Проверено 19 марта 2015 г.
^ Jump up to: Перейти обратно: ^а ^б ^с ^д Дэниел Юрафски; Джеймс Х. Мартин. Речевая и языковая обработка . Пирсон Эдьюкейшн Интернэшнл. стр. 107–111.
^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и Эско Укконен (1983). О приблизительном сопоставлении строк . Основы теории вычислений. Спрингер. стр. 487–495. дои : 10.1007/3-540-12689-9_129 .
^ Jump up to: Перейти обратно: ^а ^б ^с ^д Шульц, Клаус У.; Михов, Стоян (2002). «Быстрая коррекция струн с помощью автоматов Левенштейна». Международный журнал анализа и распознавания документов . 5 (1): 67–85. CiteSeerX 10.1.1.16.652 . дои : 10.1007/s10032-002-0082-8 . S2CID 207046453 .
^ Лэй Чен; Раймонд Нг (2004). О браке L _п -нормы и дистанции редактирования (PDF) . Учеб. 30-я Международная конференция. по очень большим базам данных (VLDB). Том. 30. дои : 10.1016/b978-012088469-8.50070-x .
^ Кукич, Карен (1992). «Методы автоматического исправления слов в тексте» (PDF) . Обзоры вычислительной техники ACM . 24 (4): 377–439. дои : 10.1145/146370.146380 . S2CID 5431215 . Архивировано из оригинала (PDF) 27 сентября 2016 г. Проверено 9 ноября 2017 г.
^ Р. Вагнер; М. Фишер (1974). «Проблема построчной коррекции» . Дж. АКМ . 21 : 168–178. дои : 10.1145/321796.321811 . S2CID 13381535 .
^ Скиена, Стивен (2010). Руководство по разработке алгоритмов (2-е изд.). Springer Science+Business Media . Бибкод : 2008адм..книга.....С . ISBN 978-1-849-96720-4 .
^ Чоудхури, Резаул; Ле, Хай-Сон; Рамачандран, Виджая (июль 2010 г.). «Динамическое программирование без учета кэша для биоинформатики» . Транзакции IEEE/ACM по вычислительной биологии и биоинформатике . 7 (3): 495–510. дои : 10.1109/TCBB.2008.94 . ПМИД 20671320 . S2CID 2532039 .
^ Укконен, Эско (1985). «Алгоритмы приблизительного сопоставления строк» (PDF) . Информация и контроль . 64 (1–3): 100–118. дои : 10.1016/S0019-9958(85)80046-2 .
^ Ландо; Майерс; Шмидт (1998). «Инкрементное сравнение строк». SIAM Journal по вычислительной технике . 27 (2): 557–582. CiteSeerX 10.1.1.38.1766 . дои : 10.1137/S0097539794264810 .
^ Масек, Уильям Дж.; Патерсон, Майкл С. (февраль 1980 г.). «Более быстрый алгоритм вычисления расстояний редактирования строк» . Журнал компьютерных и системных наук . 20 (1): 18–31. дои : 10.1016/0022-0000(80)90002-1 . ISSN 0022-0000 .
^ Эско Укконен (1985). «Нахождение примерных закономерностей в строках». Дж. Алгоритмы . 6 : 132–137. дои : 10.1016/0196-6774(85)90023-9 .
^ Jump up to: Перейти обратно: ^а ^б Брингманн, Карл; Грандони, Фабрицио; Саха, Барна ; Уильямс, Вирджиния Василевска (2016). «Поистине субкубические алгоритмы для языкового редактирования расстояния и сворачивания РНК с помощью быстрого произведения минимальной плюс минимальной разницы с ограниченной разностью» (PDF) . 57-й ежегодный симпозиум IEEE по основам информатики (FOCS) , 2016 г. стр. 375–384. arXiv : 1707.05095 . дои : 10.1109/focs.2016.48 . ISBN 978-1-5090-3933-3 . S2CID 17064578 .
^ Ахо, А.; Петерсон, Т. (1 декабря 1972 г.). «Парсер с коррекцией ошибок на минимальном расстоянии для контекстно-свободных языков». SIAM Journal по вычислительной технике . 1 (4): 305–312. дои : 10.1137/0201022 . ISSN 0097-5397 .
^ Вагнер, Роберт А. (1974). «Порядок n исправлений для обычных языков» . Коммуникации АКМ . 17 (5): 265–268. дои : 10.1145/360980.360995 . S2CID 11063282 .
^ Саха, Б. (01 октября 2014 г.). Проблема расстояния редактирования языка Дейка в почти линейном времени . 55-й ежегодный симпозиум IEEE по основам информатики, 2014 г. стр. 611–620. дои : 10.1109/FOCS.2014.71 . ISBN 978-1-4799-6517-5 . S2CID 14806359 .

[navarnarutoro-1] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Наварро, Гонсало (1 марта 2001 г.). «Экскурсия по приблизительному сопоставлению строк» (PDF) . Обзоры вычислительной техники ACM . 33 (1): 31–88. CiteSeerX 10.1.1.452.6317 . дои : 10.1145/375360.375365 . S2CID 207551224 . Проверено 19 марта 2015 г.

[slp-2] Jump up to: Перейти обратно: ^а ^б ^с ^д Дэниел Юрафски; Джеймс Х. Мартин. Речевая и языковая обработка . Пирсон Эдьюкейшн Интернэшнл. стр. 107–111.

[ukkonen83-3] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и Эско Укконен (1983). О приблизительном сопоставлении строк . Основы теории вычислений. Спрингер. стр. 487–495. дои : 10.1007/3-540-12689-9_129 .

[ssm-4] Jump up to: Перейти обратно: ^а ^б ^с ^д Шульц, Клаус У.; Михов, Стоян (2002). «Быстрая коррекция струн с помощью автоматов Левенштейна». Международный журнал анализа и распознавания документов . 5 (1): 67–85. CiteSeerX 10.1.1.16.652 . дои : 10.1007/s10032-002-0082-8 . S2CID 207046453 .

[5] Лэй Чен; Раймонд Нг (2004). О браке L _п -нормы и дистанции редактирования (PDF) . Учеб. 30-я Международная конференция. по очень большим базам данных (VLDB). Том. 30. дои : 10.1016/b978-012088469-8.50070-x .

[6] Кукич, Карен (1992). «Методы автоматического исправления слов в тексте» (PDF) . Обзоры вычислительной техники ACM . 24 (4): 377–439. дои : 10.1145/146370.146380 . S2CID 5431215 . Архивировано из оригинала (PDF) 27 сентября 2016 г. Проверено 9 ноября 2017 г.

[7] Р. Вагнер; М. Фишер (1974). «Проблема построчной коррекции» . Дж. АКМ . 21 : 168–178. дои : 10.1145/321796.321811 . S2CID 13381535 .

[8] Скиена, Стивен (2010). Руководство по разработке алгоритмов (2-е изд.). Springer Science+Business Media . Бибкод : 2008адм..книга.....С . ISBN 978-1-849-96720-4 .

[CLR-08-9] Чоудхури, Резаул; Ле, Хай-Сон; Рамачандран, Виджая (июль 2010 г.). «Динамическое программирование без учета кэша для биоинформатики» . Транзакции IEEE/ACM по вычислительной биологии и биоинформатике . 7 (3): 495–510. дои : 10.1109/TCBB.2008.94 . ПМИД 20671320 . S2CID 2532039 .

[10] Укконен, Эско (1985). «Алгоритмы приблизительного сопоставления строк» (PDF) . Информация и контроль . 64 (1–3): 100–118. дои : 10.1016/S0019-9958(85)80046-2 .

[11] Ландо; Майерс; Шмидт (1998). «Инкрементное сравнение строк». SIAM Journal по вычислительной технике . 27 (2): 557–582. CiteSeerX 10.1.1.38.1766 . дои : 10.1137/S0097539794264810 .

[12] Масек, Уильям Дж.; Патерсон, Майкл С. (февраль 1980 г.). «Более быстрый алгоритм вычисления расстояний редактирования строк» . Журнал компьютерных и системных наук . 20 (1): 18–31. дои : 10.1016/0022-0000(80)90002-1 . ISSN 0022-0000 .

[13] Эско Укконен (1985). «Нахождение примерных закономерностей в строках». Дж. Алгоритмы . 6 : 132–137. дои : 10.1016/0196-6774(85)90023-9 .

[:0-14] Jump up to: Перейти обратно: ^а ^б Брингманн, Карл; Грандони, Фабрицио; Саха, Барна ; Уильямс, Вирджиния Василевска (2016). «Поистине субкубические алгоритмы для языкового редактирования расстояния и сворачивания РНК с помощью быстрого произведения минимальной плюс минимальной разницы с ограниченной разностью» (PDF) . 57-й ежегодный симпозиум IEEE по основам информатики (FOCS) , 2016 г. стр. 375–384. arXiv : 1707.05095 . дои : 10.1109/focs.2016.48 . ISBN 978-1-5090-3933-3 . S2CID 17064578 .

[15] Ахо, А.; Петерсон, Т. (1 декабря 1972 г.). «Парсер с коррекцией ошибок на минимальном расстоянии для контекстно-свободных языков». SIAM Journal по вычислительной технике . 1 (4): 305–312. дои : 10.1137/0201022 . ISSN 0097-5397 .

[16] Вагнер, Роберт А. (1974). «Порядок n исправлений для обычных языков» . Коммуникации АКМ . 17 (5): 265–268. дои : 10.1145/360980.360995 . S2CID 11063282 .

[17] Саха, Б. (01 октября 2014 г.). Проблема расстояния редактирования языка Дейка в почти линейном времени . 55-й ежегодный симпозиум IEEE по основам информатики, 2014 г. стр. 611–620. дои : 10.1109/FOCS.2014.71 . ISBN 978-1-4799-6517-5 . S2CID 14806359 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

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