Алгоритм сопоставления подстановочных знаков Краусса - Википедия - Krauss wildcard-matching algorithm

В Информатика, то Алгоритм сопоставления подстановочных знаков Краусса это сопоставление с образцом алгоритм. На основе синтаксис подстановочного знака в общем использовании, например в Майкрософт Виндоус Интерфейс командной строки, алгоритм обеспечивает не-рекурсивный механизм сопоставления шаблонов в программных приложениях, основанный на синтаксисе более простом, чем тот, который обычно предлагается обычные выражения.

История

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

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

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

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

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

  • Однозначное соответствие выполняется между шаблоном и источником, который необходимо проверить на совпадение, за исключением звездочки (* ) или вопросительный знак (? ) символов в шаблоне.
  • Звездочка (* ) соответствует любой последовательности из нуля или более символов.
  • Знак вопроса (? ) соответствует любому одиночному символу.

Примеры

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

Приложения

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

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

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

  1. ^ Краусс, Кирк (2008). «Подстановочные знаки соответствия: алгоритм». Журнал доктора Добба.
  2. ^ "поиск по дикой карте". alt.os.development. 2008 г.
  3. ^ T.J. (2014). "сопоставление подстановочных знаков в текстовой строке". Переполнение стека.
  4. ^ Краусс, Кирк (2014). «Подстановочные знаки соответствия: эмпирический способ приручить алгоритм». Журнал доктора Добба.
  5. ^ Краусс, Кирк (2018). «Подстановочные знаки соответствия: улучшенный алгоритм для больших данных». Развивайте производительность.
  6. ^ Хейгес, Ларри (2008). «Функция сравнения текста - generalTextCompare.txt». Всемирная библиотека кодов доступа к данным.
  7. ^ Денискоре (2013). "Deniskore / wildcard / CLogReader.cpp". Популярные репозитории. GitHub. Строки 173-279.
  8. ^ gildor2 (2016). "UModel / Core / Core.cpp". Средство просмотра моделей Unreal Engine (средство просмотра пользовательского интерфейса). GitHub. Строки 334-435.
  9. ^ gildor2 (2016). «История UModel / Core / Core.cpp». Средство просмотра моделей Unreal Engine (средство просмотра пользовательского интерфейса).