Соответствие подстановочных знаков

В информатике алгоритм сопоставления подстановочных знаков (также известный как подстановка ) полезен при сравнении текстовых строк, которые могут содержать синтаксис подстановочных знаков . ^[1] Обычно эти алгоритмы используются в интерфейсах командной строки , например, в оболочке Bourne ^[2] или командной строке Microsoft Windows ^[3] или текстовом редакторе или файловом менеджере, а также в интерфейсах некоторых поисковых систем ^[4] и баз данных. ^[5] Сопоставление подстановочных знаков является подмножеством проблемы сопоставления регулярных выражений и сопоставления строк в целом. ^[6]

Проблема

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

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

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

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

Определение

Задачу сопоставления с помощью индексов, начинающихся с нуля, можно рекурсивно определить следующим образом:

{\begin{aligned}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}}&{\text{for}}\;p_{i-1}\neq t_{j-1}\end{cases}}&&\quad {\text{for}}\;1\leq i\leq |p|,1\leq j\leq |t|.\end{aligned}}

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

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

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

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

История

Ранние алгоритмы для сопоставления подстановочных знаков часто полагались на рекурсию , но эта техника подвергалась критике по соображениям производительности ^[10] и надежности ^[8] . Нерекурсивные алгоритмы для сопоставления подстановочных знаков получили признание в свете этих соображений.

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

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

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

Алгоритм подстановочного мата Rich Salz ( sh-подобный синтаксис) ^[14]
Алгоритм Филипа ^[15] и алгоритм Виньеша Муругесана ^[16]
Алгоритм Мартина Рихтера ^[9] (идентичен Snippets и связан с алгоритмом 7-zip) ^[17]
Реализации fnmatch библиотеки C (поддерживает [...]многобайтовые наборы символов):
- BSD libc fnmatch Гвидо ван Россума ^[18] , также часть Apple libc ^[19]
- Glibc fnmatch ^[20]

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

Ссылки

^ "Подстановочные знаки". ScienceDirect . 2018.
^ Куигли, Элли (2005). Краткое руководство по программированию оболочки UNIX. InformIT.com.
^ "MS-DOS и подстановочные знаки Windows". Библиотека Microsoft Developer Network . 31 мая 2018 г.
^ "Apache Lucene - Синтаксис парсера запросов". Документация Apache Lucene 2.9.4. 2006.
^ "SQL Wildcards". W3Schools . 2018.
^ Гойвартс, Ян (2018). «Добро пожаловать на Regular-Expressions.info». RegularExpressions.info.
^ «Wildcard Expansion». docs.microsoft.com . 8 февраля 2022 г.
^ abc Krauss, Kirk (2008). «Сопоставление подстановочных знаков: алгоритм». Журнал доктора Добба .
^ abc Deadlock (2015). "Рекурсивный алгоритм сопоставления подстановочных знаков C++". Stack Overflow .
^ abcd Кантаторе, Алессандро (2003). «Алгоритмы сопоставления с подстановочными знаками».
^ Iliopoulos, Costas S.; Rahman, M. Sohel (2007). «Pattern Matching Algorithms with Don't Cares» (PDF) . SOFSEM 2007: Теория и практика компьютерных наук, 33-я конференция по современным тенденциям в теории и практике компьютерных наук . Гаррахов, Чешская Республика. S2CID 14538871. Архивировано из оригинала (PDF) 2019-12-17.
^ Клиффорд, Питер; Клиффорд, Рафаэль (январь 2007 г.). «Простое детерминированное сопоставление подстановочных знаков». Information Processing Letters . 101 (2): 53–54. doi :10.1016/j.ipl.2006.08.002.
^ Wu, Xindong; Qiang, Ji-Peng; Xie, Fei (12 сентября 2014 г.). «Соответствие шаблону с гибкими подстановочными знаками». Журнал компьютерной науки и технологий . 29 (5): 740–750. doi :10.1007/s11390-014-1464-3. S2CID 16824910.
^ аб Зальц, Рич (1991). "wildmat.c". Гитхаб .
^ Filip (2014). «Сравнение строк с подстановочным знаком». Stack Overflow .
^ Муругесан, Вигнеш (2014). «Алгоритм сопоставления WildCard».
^ abc Курт, Доган. «Методы сопоставления с подстановочными знаками».
^ ван Россум, Гвидо (20 ноября 2019 г.). "freebsd/lib/libc/gen/fnmatch.c". GitHub . Получено 21 ноября 2019 г. .
^ "fnmatch.c". opensource.apple.com. 1999.
^ "fnmatch_internal.c". Зеркала Берена Минора. 21 ноября 2019 г.
^ ab "git/git: wildmatch.c". GitHub . 2020-01-20.
^ ab "uwildmat.c in trunk/lib – INN". inn.eyrie.org . Получено 27 ноября 2019 г. .
^ Краусс, Кирк (2018). «Соответствие подстановочных знаков: улучшенный алгоритм для больших данных». Разработка для производительности.
^ Siler (2013). «Рекурсивные решения для сопоставления шаблонов glob». Stack Overflow .
^ Handy, Jack (2005). "Сравнение строк с подстановочными знаками (глоббинг)". Code Project .
^ Кокс, Росс. «Соответствие регулярным выражениям может быть простым и быстрым».
^ Наварро, Гонсало (10 ноября 2001 г.). «NR-grep: быстрый и гибкий инструмент сопоставления с образцом» (PDF) . Программное обеспечение: практика и опыт . 31 (13): 1265–1312. doi :10.1002/spe.411. S2CID 3175806.