В информатике , то алгоритм подстановочных сопоставлений Krauss является сопоставление с образцом алгоритмом. Основанный на широко используемом синтаксисе с подстановочными знаками , например в интерфейсе командной строки Microsoft Windows , алгоритм обеспечивает нерекурсивный механизм сопоставления шаблонов в программных приложениях, основанный на синтаксисе, более простом, чем тот, который обычно предлагается регулярными выражениями .
История [ править ]
Алгоритм основан на истории разработки, тестировании корректности и производительности, а также на отзывах программистов, которые начались с безуспешного поиска надежного нерекурсивного алгоритма сопоставления подстановочных знаков. Первоначальный алгоритм, реализованный в одном цикле while, быстро вызвал комментарии от разработчиков программного обеспечения, что привело к улучшениям. [1] Постоянные комментарии и предложения [2] [3] привели к появлению пересмотренного алгоритма, все еще реализованного в едином цикле while, но доработанного на основе набора тестовых примеров и профилировщика производительности . [4]Опыт настройки одиночного цикла while с помощью профилировщика побудил к разработке стратегии двух циклов, которая позволила добиться дальнейшего повышения производительности, особенно в ситуациях, связанных с пустыми входными строками или входными данными, не содержащими подстановочных знаков. [5] Двухпетлевой алгоритм доступен для использования сообществом разработчиков программного обеспечения с открытым исходным кодом в соответствии с условиями Apache License v. 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]
См. Также [ править ]
- сопоставление с образцом
- glob (программирование)
- Wildmat
Ссылки [ править ]
- ^ Краусс, Кирк (2008). «Подстановочные знаки соответствия: алгоритм» . Журнал доктора Добба .
- ^ "поиск по шаблону" . alt.os.development. 2008 г.
- Перейти ↑ TJ (2014). «сопоставление подстановочных знаков в текстовой строке» . Переполнение стека.
- ^ Краусс, Кирк (2014). «Подстановочные знаки соответствия: эмпирический способ приручить алгоритм» . Журнал доктора Добба .
- ^ Краусс, Кирк (2018). «Подстановочные знаки соответствия: улучшенный алгоритм для больших данных» . Развивайте для повышения производительности.
- ^ Heiges, Ларри (2008). «Функция сравнения текста - generalTextCompare.txt» . Всемирная библиотека кодов доступа к данным .
- ^ Deniskore (2013). "Deniskore / wildcard / CLogReader.cpp" . Популярные репозитории . GitHub. Строки 173-279.
- ^ gildor2 (2016). «UModel / Core / Core.cpp» . Средство просмотра моделей Unreal Engine (UE Viewer) . GitHub. Строки 334-435.
- ^ gildor2 (2016). «История UModel / Core / Core.cpp» . Средство просмотра моделей Unreal Engine (UE Viewer) .
