Соответствующие подстановочные знаки

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

Проблема

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

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

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

В этой статье в основном обсуждается формулировка проблемы в 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 соответственно. Это формулировка, используемая алгоритмом Рихтера и алгоритмом фрагментов , найденным в коллекции Канаторе. Это описание похоже на расстояние Левенштейна .

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

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

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

История

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

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

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

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

• Rich Salt ( Алгоритм подстановочного мата синтаксис типа sh)
• Алгоритм Филипа и алгоритм Виньеша Муругесана
• Алгоритм Мартина Рихтера (идентично 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 против чрезмерной рекурсии (Ларс Матисен, 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"))

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

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

См. также

• Сопоставление с образцом
• Исчисление шаблонов
• Глоб (программирование)
• Подстановочный знак
• Список алгоритмов