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

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

Проблема

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

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

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

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

Определение

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

куда мij результат сопоставления с шаблоном п против текста т усечен на я и j персонажей соответственно. Это формулировка, используемая алгоритмом Рихтера и Фрагменты алгоритм найден в коллекции Кантаторе.[9][10] Это описание похоже на Расстояние Левенштейна.

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

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

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

История

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

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

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

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

  • Рич Зальц ' Wildmat алгоритм (sh-подобный синтаксис)[14]
  • Алгоритм Филипа[15] и алгоритм Винеша Муругесана[16]
  • Алгоритм Мартина Рихтера[9] (идентично Фрагменты и связанные с алгоритмом 7-zip)[17]
  • Библиотека C fnmatch реализации (поддерживает [...] и многобайтовые наборы символов):

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

  • Сигнал ABORT против чрезмерной рекурсии (Lars Mathiesen, 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] В типичных шаблонах (как проверено Cantatore) он медленнее, чем реализации жадного вызова.[10]

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

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

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

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

  • Алгоритм Джека Хэнди[25] (не удается ПОИСКПОЗ ("*?", "Xx"))

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

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

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

Рекомендации

  1. ^ «Подстановочные знаки». ScienceDirect. 2018.
  2. ^ Куигли, Элли (2005). Краткое руководство по программированию в оболочке UNIX. InformIT.com.
  3. ^ «Подстановочные знаки MS-DOS и Windows». Сеть разработчиков Microsoft Библиотека.
  4. ^ «Apache Lucene - синтаксис парсера запросов». Apache Lucene 2.9.4 Документация. 2006 г.
  5. ^ "Подстановочные знаки SQL". W3Школы. 2018.
  6. ^ Гойвертс, янв (2018). "Добро пожаловать на Regular-Expressions.info". RegularExpressions.info.
  7. ^ «Расширение с подстановочными знаками». docs.microsoft.com.
  8. ^ а б c Краусс, Кирк (2008). «Подстановочные знаки соответствия: алгоритм». Журнал доктора Добба.
  9. ^ а б c Тупик (2015). "Рекурсивный алгоритм сопоставления с подстановочными знаками C ++". Переполнение стека.
  10. ^ а б c d Кантаторе, Алессандро (2003). "Алгоритмы сопоставления подстановочных знаков".
  11. ^ Iliopoulos, Costas S .; Рахман, М. Сохель (2007). "Алгоритмы сопоставления с образцом с Don't Cares" (PDF). СОФСЕМ 2007: Теория и практика информатики, 33-я конференция «Современные тенденции в теории и практике информатики». Гаррахов, Чехия.
  12. ^ Клиффорд, Питер; Клиффорд, Рафаэль (январь 2007 г.). «Простое детерминированное сопоставление подстановочных знаков». Письма об обработке информации. 101 (2): 53–54. Дои:10.1016 / j.ipl.2006.08.002.
  13. ^ У, Синьдун; Цян, Цзи-Пэн; Се, Фэй (12 сентября 2014 г.). «Сопоставление шаблонов с гибкими подстановочными знаками». Журнал компьютерных наук и технологий. 29 (5): 740–750. Дои:10.1007 / s11390-014-1464-3.
  14. ^ а б Зальц, Рич (1991). "wildmat.c". GitHub.
  15. ^ Филип (2014). «Сравнить строки с подстановочным знаком». Переполнение стека.
  16. ^ Муругесан, Виньеш (2014). «Алгоритм сопоставления WildCard».
  17. ^ а б c Курт, Доган. «Методы сопоставления с подстановочными знаками».
  18. ^ ван Россум, Гвидо (20 ноября 2019 г.). "freebsd / lib / libc / gen / fnmatch.c". Получено 21 ноября 2019.
  19. ^ "fnmatch.c". opensource.apple.com. 1999 г.
  20. ^ "fnmatch_internal.c". Зеркала Берена Минора. 21 ноября 2019.
  21. ^ а б "git / git: wildmatch.c". GitHub. 2020-01-20.
  22. ^ а б "uwildmat.c в trunk / lib - ИНН". inn.eyrie.org. Получено 27 ноября 2019.
  23. ^ Краусс, Кирк (2018). «Подстановочные знаки соответствия: улучшенный алгоритм для больших данных». Развивайте производительность.
  24. ^ Силер (2013). «Рекурсивные решения для сопоставления глобальных шаблонов». Переполнение стека.
  25. ^ Хэнди, Джек (2005). "Сравнение строк с подстановочными знаками (подстановка}". Код проекта.
  26. ^ Кокс, Росс. «Сопоставление регулярных выражений может быть простым и быстрым».
  27. ^ Наварро, Гонсало (10 ноября 2001 г.). «NR ‐ grep: быстрый и гибкий инструмент сопоставления с образцом» (PDF). Программное обеспечение: практика и опыт. 31 (13): 1265–1312. Дои:10.1002 / spe.411.