Алгоритм сопоставления подстановочных знаков Краусса

В информатике алгоритм сопоставления подстановочных знаков Краусса представляет собой алгоритм сопоставления с образцом . Основанный на синтаксисе подстановочных знаков широко распространенном Microsoft Windows , например, в интерфейсе командной строки , алгоритм обеспечивает нерекурсивный механизм сопоставления шаблонов в программных приложениях, основанный на более простом синтаксисе, чем тот, который обычно предлагается регулярными выражениями .

История

Алгоритм основан на истории разработки, тестировании на корректность и производительность, а также на отзывах программистов, которые начались с неудачного поиска надежного нерекурсивного алгоритма сопоставления подстановочных знаков. Первоначальный алгоритм, реализованный в одном цикле while, быстро вызвал комментарии разработчиков программного обеспечения, что привело к улучшениям. ^[1] Постоянные комментарии и предложения ^[2]^[3] Кульминацией стал пересмотренный алгоритм, который все еще реализован в одном цикле while, но усовершенствован на основе набора тестовых примеров и профилировщика производительности . ^[4] Опыт настройки одного цикла while с помощью профилировщика побудил к разработке стратегии с двумя циклами, которая позволила добиться дальнейшего повышения производительности, особенно в ситуациях, связанных с пустыми входными строками или входными данными, не содержащими подстановочных знаков. ^[5] Двухконтурный алгоритм доступен для использования сообществом разработчиков программного обеспечения с открытым исходным кодом на условиях лицензии Apache версии 2.0 и сопровождается кодом тестового примера.

Использование

Алгоритм, доступный по лицензии Apache, реализован как на на указателях основанном C++, , так и на переносимом C++ (реализованном без указателей). Код тестового примера, также доступный по лицензии Apache, можно применять к любому алгоритму, который обеспечивает приведенные ниже операции сопоставления с образцом. Реализация в закодированном виде не может обрабатывать многобайтовые наборы символов и создает проблемы, когда искомый текст может содержать несколько несовместимых наборов символов.

Операции сопоставления с образцом

Алгоритм поддерживает три операции сопоставления с образцом:

Между шаблоном и источником, подлежащим проверке, выполняется однозначное совпадение, за исключением символов звездочки ( * ) или вопросительного знака ( ? ) в шаблоне.
Символ звездочки ( * ) соответствует любой последовательности, состоящей из нуля или более символов.
Символ вопросительного знака ( ? ) соответствует любому отдельному символу.

Примеры

*foo* соответствует любой строке, содержащей «foo».
mini* соответствует любой строке, начинающейся с «mini» (включая саму строку «mini»).
?* соответствует любой строке из трех и более букв.

Приложения

Исходный алгоритм был перенесен на язык программирования DataFlex Ларри Хейгесом. ^[6] для использования с библиотекой кодов Data Access Worldwide . Он был опубликован на GitHub в измененной форме как часть программы чтения файлов журналов. ^[7] Алгоритм 2014 года является частью Unreal Model Viewer, встроенного в Epic Games Unreal Engine игровой движок . ^[8]^[9]

См. также

Ссылки

^ Краусс, Кирк (2008). «Сопоставление подстановочных знаков: алгоритм» . Журнал доктора Добба .
^ «поиск по шаблону» . alt.os.development. 2008.
^ ТиДжей (2014). «сопоставление подстановочных знаков в текстовой строке» . Переполнение стека.
^ Краусс, Кирк (2014). «Сопоставление подстановочных знаков: эмпирический способ приручить алгоритм» . Журнал доктора Добба .
^ Краусс, Кирк (2018). «Сопоставление подстановочных знаков: улучшенный алгоритм для больших данных» . Развивайтесь ради производительности.
^ Хейгес, Ларри (2008). «Функция сравнения текста — GeneralTextCompare.txt» . Всемирная библиотека кодов доступа к данным .
^ Денискоре (2013). "Deniskore/wildcard/CLogReader.cpp" . Популярные репозитории . Гитхаб. Строки 173–279.
^ гилдор2 (2016). "UModel/Core/Core.cpp" . Средство просмотра моделей Unreal Engine (UE Viewer) . Гитхаб. {{cite web}}: CS1 maint: числовые имена: список авторов ( ссылка ) Строки 334-435.
^ гилдор2 (2016). «История UModel/Core/Core.cpp» . Средство просмотра моделей Unreal Engine (UE Viewer) . {{cite web}}: CS1 maint: числовые имена: список авторов ( ссылка )

[1] Краусс, Кирк (2008). «Сопоставление подстановочных знаков: алгоритм» . Журнал доктора Добба .

[2] «поиск по шаблону» . alt.os.development. 2008.

[3] ТиДжей (2014). «сопоставление подстановочных знаков в текстовой строке» . Переполнение стека.

[4] Краусс, Кирк (2014). «Сопоставление подстановочных знаков: эмпирический способ приручить алгоритм» . Журнал доктора Добба .

[5] Краусс, Кирк (2018). «Сопоставление подстановочных знаков: улучшенный алгоритм для больших данных» . Развивайтесь ради производительности.

[6] Хейгес, Ларри (2008). «Функция сравнения текста — GeneralTextCompare.txt» . Всемирная библиотека кодов доступа к данным .

[7] Денискоре (2013). "Deniskore/wildcard/CLogReader.cpp" . Популярные репозитории . Гитхаб. Строки 173–279.

[8] гилдор2 (2016). "UModel/Core/Core.cpp" . Средство просмотра моделей Unreal Engine (UE Viewer) . Гитхаб. {{cite web}}: CS1 maint: числовые имена: список авторов ( ссылка ) Строки 334-435.

[9] гилдор2 (2016). «История UModel/Core/Core.cpp» . Средство просмотра моделей Unreal Engine (UE Viewer) . {{cite web}}: CS1 maint: числовые имена: список авторов ( ссылка )

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]