Подстановочные знаки соответствия - Matching wildcards

В информатике алгоритм сопоставления подстановочных знаков (также известный как подстановка ) полезен при сравнении текстовых строк, которые могут содержать синтаксис подстановочных знаков . Обычно эти алгоритмы используют интерфейсы командной строки , например, оболочку Bourne или командную строку Microsoft Windows, текстовый редактор или файловый менеджер, а также интерфейсы для некоторых поисковых систем и баз данных. Сопоставление с подстановочными знаками - это подмножество проблемы сопоставления регулярных выражений и сопоставления строк в целом.

Эта проблема

Средство сопоставления подстановочных знаков проверяет подстановочный образец p по входной строке s . Он выполняет привязанное сопоставление, возвращает истину только тогда, когда p совпадает полностью с s .

Шаблон может быть основан на любом распространенном синтаксисе (см. Подстановку ), но в Windows программисты склонны обсуждать только упрощенный синтаксис, поддерживаемый встроенной средой выполнения C:

Не определены escape-символы
Подстановочные знаки: ?соответствует ровно одному вхождению любого символа. *соответствует произвольному количеству (включая ноль) вхождений любого символа.

В этой статье в основном обсуждается постановка проблемы Windows, если не указано иное.

Определение

Указанная в индексах с нулевым отсчетом проблема сопоставления подстановочных знаков может быть определена рекурсивно как:

{\ displaystyle {\ begin {align} m_ {00} & = (p_ {0} = t_ {0}) \\ m_ {0j} & = (p_ {j-1} = {\ text {'*'} }) \ land m_ {0, j-1} \\ m_ {i0} & = {\ text {false}} \\ m_ {ij} & = {\ begin {cases} m_ {i-1, j-1 } & {\ text {for}} \; p_ {i-1} = t_ {j-1} \ lor p_ {i-1} = {\ text {'?'}} \\ m_ {i, j- 1} \ lor m_ {i-1, j} & {\ text {for}} \; p_ {i-1} = {\ text {'*'}} \\ {\ text {false}} & {\ текст {for}} \; p_ {i-1} \ neq t_ {j-1} \ end {cases}} && \ quad {\ text {for}} \; 1 \ leq i \ leq | p |, 1 \ leq j \ leq | t |. \ конец {выровнено}}}

где m _ij - результат сопоставления образца p с текстом t, усеченным до i и j символов соответственно. Это формулировка, используемая алгоритмом Рихтера и алгоритмом фрагментов , найденным в коллекции Кантаторе. Это описание похоже на расстояние Левенштейна .

Связанные проблемы

К непосредственно связанным проблемам информатики относятся:

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

История

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

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

Рекурсивные алгоритмы

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

Богатые Salz ' wildmat алгоритм (ш-подобный синтаксис)
Алгоритм Филипа и алгоритм Винеша Муругесана
Алгоритм Мартина Рихтера (идентичен Snippets и связан с алгоритмом 7-zip)
Реализации библиотеки C fnmatch
(поддерживает [...]и многобайтовые наборы символов):
- BSD libc fnmatch
Гвидо ван Россума , также часть Apple libc
Glibc fnmatch

Общий вид этих алгоритмов одинаков. При рекурсии алгоритм разделяет ввод на подстроки и считает, что совпадение произошло, когда ОДНА из подстрок возвращает положительное совпадение. Для dowild("*X", "abcX"), это было бы назвать жадностью dowild("X", "abcX"), dowild("X", "bcX"), dowild("X", "cX")и dowild("X", "X"). Обычно они отличаются менее важными вещами, такими как поддержка функций, и более важными факторами, такими как незначительные, но очень эффективные оптимизации. Некоторые из них включают:

Сигнал ABORT против чрезмерной рекурсии (Lars Mathiesen, 1991). Хотя наивно повторять все остальные строки (шаблон и текст) *и следить за тем, чтобы ОДНА из подстрок вернула положительное совпадение, время выполнения становится экспоненциальным для отклонения совпадений со многими *в тексте. Ларс Матизен изменяет возврат на три класса: совпадение, несоответствие и ABORT (совпадение невозможно для рекурсии звездочки). Значение ABORT возвращается, когда текст используется слишком рано или когда другое совпадение звездочки не удается, что гарантирует линейная производительность по количеству звездочек. (Общая сложность дополнительно квадратична по отношению к количеству оставшихся символов.) Подстановочное соответствие ABORT Git / Rsync также охватывает недопустимые входные данные. Новый ИНН uwildmat делает то же самое.
Улучшение рекурсии в Asterisk. Эта настройка wildmatch относительно менее важна. Это применимо, когда рекурсия хочет сопоставить «* X» на «abcX»: когда за звездочкой следует литерал вроде «X», очевидно, что только последнее сравнение с равной длиной может дать совпадение. . Это было замечено ранее в uwildmat в 2000 году и более косвенно в fnmatch ван Россума для FNM_PATHNAME.

Алгоритм Мартина Рихтера является исключением из этого шаблона, хотя в целом операция эквивалентна. На * он повторяется в увеличении любого из индексов в соответствии с формулировкой задачи динамическим программированием. К нему применима и техника «ABORT». На типичных шаблонах (как было проверено Cantatore) он медленнее, чем реализации жадного вызова.

О рекурсивных алгоритмах в целом легче рассуждать, а с модификацией ABORT они работают приемлемо с точки зрения сложности наихудшего случая. В строках без * для сопоставления требуется время линейного размера, поскольку существует фиксированное взаимно-однозначное отношение.

Нерекурсивные алгоритмы

Критики рекурсивных алгоритмов разработали следующее:

Алгоритм сопоставления подстановочных знаков Кирка Дж. Краусса , используемый IBM
Коллекция алгоритмов сопоставления подстановочных знаков Алессандро Кантаторе
Итеративный сопоставитель Догана Курта и более медленный сопоставитель NFA.
Неправильный алгоритм Сайлера (не работает MATCH("da*da*da*", "daaadabadmanda"))

Следующее не является:

Неправильный алгоритм Джека Хэнди (не работает MATCH("*?", "xx"))

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

Кроме того, проблема сопоставления подстановочных знаков может быть преобразована в сопоставление регулярных выражений с использованием наивного подхода с заменой текста . Хотя нерекурсивные средства сопоставления регулярных выражений, такие как конструкция Томпсона, менее используются на практике из-за отсутствия поддержки обратных ссылок, сопоставление с подстановочными знаками в целом не имеет столь же богатого набора функций. (Фактически, многие из вышеперечисленных алгоритмов поддерживают только ?и *.) Реализация NFA Томпсона Рассом Коксом может быть тривиально модифицирована для этого. Алгоритм nrgrep Густаво Наварро, основанный на BDM , обеспечивает более оптимизированную реализацию с упором на эффективные суффиксы. См. Также § реализации регулярных выражений .

Languages

In other projects