В информатике алгоритм сопоставления подстановочных знаков (также известный как подстановка ) полезен при сравнении текстовых строк, которые могут содержать синтаксис подстановочных знаков . [1] Обычно эти алгоритмы используют интерфейсы командной строки , например, оболочку Bourne [2] или командную строку Microsoft Windows [3], текстовый редактор или файловый менеджер, а также интерфейсы для некоторых поисковых систем [4] и базы данных. [5] Сопоставление с подстановочными знаками - это подмножество проблемы сопоставления регулярных выражений и сопоставления строк в целом.[6]
Проблема
Средство сопоставления подстановочных знаков проверяет подстановочный образец p по входной строке s . Он выполняет привязанное сопоставление, возвращает истину только тогда, когда p совпадает полностью с s .
Шаблон может быть основан на любом распространенном синтаксисе (см. Глобализация ), но программисты Windows склонны обсуждать только упрощенный синтаксис, поддерживаемый встроенной средой выполнения C: [7] [8]
- Не определены escape-символы
- Подстановочные знаки:
?
соответствует ровно одному вхождению любого символа.*
соответствует произвольному количеству (включая ноль) вхождений любого символа.
В этой статье в основном обсуждается постановка проблемы Windows, если не указано иное.
Определение
Задача сопоставления подстановочных знаков, указанная в индексах с нулевым отсчетом, может быть определена рекурсивно как:
где m ij - результат сопоставления образца p с текстом t, усеченным до i и j символов соответственно. Это формулировка, используемая алгоритмом Рихтера и алгоритмом фрагментов , найденным в коллекции Кантаторе. [9] [10] Это описание похоже на расстояние Левенштейна .
Связанные проблемы
К непосредственно связанным проблемам информатики относятся:
- Сопоставление с образцом с безразличием или пробелами, поиск незакрепленной строки только с эквивалентом
?
определенного. [11] [12] - Сопоставление с шаблоном с использованием подстановочных знаков, поиск незакрепленной строки с определением эквивалента обоих подстановочных знаков. Имеет экспоненциальное время выполнения, если не указана граница длины в сопоставлении с шаблоном с вариантом гибких подстановочных знаков. [13]
История
Ранние алгоритмы сопоставления подстановочных знаков часто полагались на рекурсию , но этот метод подвергался критике из-за соображений производительности [10] и надежности [8] . В свете этих соображений нерекурсивные алгоритмы сопоставления подстановочных знаков получили признание.
Как среди рекурсивных, так и среди нерекурсивных алгоритмов стратегии выполнения операции сопоставления с образцом широко различаются, о чем свидетельствует множество примеров алгоритмов, упомянутых ниже. Методы разработки тестовых примеров и оптимизации производительности были явно применены к определенным алгоритмам, особенно к тем, которые были разработаны критиками рекурсивных алгоритмов.
Рекурсивные алгоритмы
Рекурсия обычно происходит при сопоставлении, *
когда есть больше суффиксов для сопоставления. Это форма поиска с возвратом , также выполняемая некоторыми сопоставителями регулярных выражений.
- Богатые Salz ' wildmat алгоритм (ш-подобный синтаксис) [14]
- Алгоритм Филипа [15] и алгоритм Винеша Муругесана [16]
- Алгоритм Мартина Рихтера [9] (идентичен Snippets и связан с алгоритмом 7-zip) [17]
- Реализации библиотеки C fnmatch (поддерживает
[...]
и многобайтовые наборы символов):- 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 против чрезмерной рекурсии (Lars Mathiesen, 1991). Хотя наивно повторять все остальные строки (шаблон и текст)
*
и следить за тем, чтобы ОДНА из подстрок вернула положительное совпадение, время выполнения становится экспоненциальным для отклонения совпадений со многими*
в тексте. Ларс Матизен изменяет возврат на три класса: совпадение, несоответствие и ABORT (совпадение невозможно для рекурсии звездочки). Значение ABORT возвращается, когда текст используется слишком рано или когда другое совпадение звездочки не удается, что гарантирует линейная производительность по количеству звездочек. (Общая сложность дополнительно квадратична по отношению к количеству оставшихся символов.) [14] Git / Rsync's wildmatch ABORT также покрывает недопустимые входные данные. [21] Новое МНН uwildmat делает то же самое. [22] - Улучшение рекурсии в Asterisk. Эта настройка wildmatch относительно менее важна. Это применимо, когда рекурсия хочет сопоставить «* X» на «abcX»: когда за звездочкой следует литерал вроде «X», очевидно, что только последнее сравнение с равной длиной может дать совпадение. . [21] Это было замечено ранее в uwildmat в 2000 году [22] и более косвенно в fnmatch ван Россума для
FNM_PATHNAME
.
Алгоритм Мартина Рихтера является исключением из этого шаблона, хотя в целом операция эквивалентна. На * он повторяется в увеличении любого из индексов в соответствии с формулировкой задачи динамическим программированием. К нему применима и техника «ABORT». [9] В типичных шаблонах (как проверено Cantatore) он медленнее, чем реализации с жадным вызовом. [10]
О рекурсивных алгоритмах в целом легче рассуждать, а с модификацией ABORT они работают приемлемо с точки зрения сложности наихудшего случая. В строках без * для сопоставления требуется время линейного размера, поскольку существует фиксированное взаимно-однозначное отношение.
Нерекурсивные алгоритмы
Критики рекурсивных алгоритмов разработали следующее:
- Алгоритм сопоставления подстановочных знаков Кирка Дж. Краусса , используемый IBM [8] [23]
- Коллекция алгоритмов сопоставления с подстановочными знаками Алессандро Кантаторе [10]
- Итеративное сопоставление Догана Курта и более медленное сопоставление NFA. [17]
- Неправильный алгоритм Силлера (не работает
MATCH("da*da*da*", "daaadabadmanda")
) [24]
Следующее не является:
- Неправильный алгоритм Джека Хэнди [25] (не работает
MATCH("*?", "xx")
)
Приведенные выше итерационные функции реализуют отслеживание с возвратом, сохраняя старый набор указателей на шаблон / текст и возвращаясь к нему в случае сбоя сопоставления. По словам Курта, поскольку требуется только одно успешное совпадение, нужно сохранить только один такой набор. [17]
Кроме того, проблема сопоставления подстановочных знаков может быть преобразована в сопоставление регулярных выражений с использованием наивного подхода с заменой текста . Хотя нерекурсивные средства сопоставления регулярных выражений, такие как конструкция Томпсона, менее используются на практике из-за отсутствия поддержки обратных ссылок, сопоставление с подстановочными знаками в целом не имеет столь же богатого набора функций. (Фактически, многие из вышеперечисленных алгоритмов поддерживают только ?
и *
.) Реализация NFA Томпсона Рассом Коксом может быть тривиально модифицирована для этого. [26] Основанный на BDM алгоритм nrgrep Густаво Наварро обеспечивает более оптимизированную реализацию с упором на эффективные суффиксы. [27] См. Также § реализации регулярных выражений .
Смотрите также
- Сопоставление с образцом
- Исчисление паттернов
- Glob (программирование)
- Подстановочный знак
- Список алгоритмов
Рекомендации
- ^ "Подстановочные знаки" . ScienceDirect . 2018.
- ^ Куигли, Элли (2005). Краткое руководство по программированию в оболочке UNIX . InformIT.com.
- ^ «Подстановочные знаки MS-DOS и Windows» . Сетевая библиотека разработчика Microsoft .
- ^ «Apache Lucene - синтаксис парсера запросов» . Документация по Apache Lucene 2.9.4. 2006 г.
- ^ «Подстановочные знаки SQL» . W3Schools . 2018.
- ^ Гойвертс, янв (2018). «Добро пожаловать на Regular-Expressions.info» . RegularExpressions.info.
- ^ «Расширение с подстановочными знаками» . docs.microsoft.com .
- ^ а б в Краусс, Кирк (2008). «Подстановочные знаки соответствия: алгоритм» . Журнал доктора Добба .
- ^ а б в Тупик (2015). «Рекурсивный алгоритм сопоставления с подстановочными знаками C ++» . Переполнение стека .
- ^ а б в г Кантаторе, Алессандро (2003). «Алгоритмы сопоставления подстановочных знаков» .
- ^ Iliopoulos, Costas S .; Рахман, М. Сохель (2007). «Алгоритмы сопоставления с образцом без забот» (PDF) . СОФСЕМ 2007: Теория и практика информатики, 33-я конференция «Современные тенденции в теории и практике информатики» . Гаррахов, Чехия. Архивировано из оригинального (PDF) 17 декабря 2019 года.
- ^ Клиффорд, Питер; Клиффорд, Рафаэль (январь 2007 г.). «Простое детерминированное сопоставление подстановочных знаков». Письма об обработке информации . 101 (2): 53–54. DOI : 10.1016 / j.ipl.2006.08.002 .
- ^ У, Синьдун; Цян, Цзи-Пэн; Се, Фэй (12 сентября 2014 г.). «Сопоставление с шаблоном с гибкими подстановочными знаками». Журнал компьютерных наук и технологий . 29 (5): 740–750. DOI : 10.1007 / s11390-014-1464-3 .
- ^ а б Зальц, Рич (1991). "wildmat.c" . GitHub .
- ^ Филип (2014). «Сравнить строки с подстановочным знаком» . Переполнение стека .
- ^ Муругесан, Виньеш (2014). «Алгоритм сопоставления WildCard» .
- ^ а б в Курт, Доган. «Методы сопоставления с подстановочными знаками» .
- ^ ван Россум, Гвидо (20 ноября 2019 г.). "freebsd / lib / libc / gen / fnmatch.c" . Проверено 21 ноября 2019 . CS1 maint: обескураженный параметр ( ссылка )
- ^ "fnmatch.c" . opensource.apple.com. 1999 г.
- ^ "fnmatch_internal.c" . Зеркала Берена Минора. 21 ноября 2019.
- ^ а б "git / git: wildmatch.c" . GitHub . 2020-01-20.
- ^ а б "uwildmat.c в trunk / lib - ИНН" . inn.eyrie.org . Проверено 27 ноября 2019 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ Краусс, Кирк (2018). «Подстановочные знаки соответствия: улучшенный алгоритм для больших данных» . Развивайте для повышения производительности.
- ^ Силер (2013). «Рекурсивные решения для сопоставления глобальных шаблонов» . Переполнение стека .
- ^ Хэнди, Джек (2005). «Сравнение строк с подстановочными знаками (подстановка)» . Проект кода .
- ^ Кокс, Росс. «Сопоставление регулярных выражений может быть простым и быстрым» .
- ^ Наварро, Гонсало (10 ноября 2001 г.). «NR ‐ grep: быстрый и гибкий инструмент сопоставления с образцом» (PDF) . Программное обеспечение: практика и опыт . 31 (13): 1265–1312. DOI : 10.1002 / spe.411 .