크라우스 와일드카드 매칭알고리즘

Krauss wildcard-matching algorithm

컴퓨터 과학에서 크라우스 와일드카드 매칭 알고리즘은 패턴 매칭 알고리즘입니다.이 알고리즘은 Microsoft Windows 명령줄 인터페이스 등 일반적으로 사용되는 와일드카드 구문을 기반으로 정규 표현보다 간단한 구문을 기반으로 소프트웨어 응용 프로그램의 패턴을 일치시키기 위한 비재귀적 메커니즘을 제공합니다.

역사

이 알고리즘은 개발, 정확성 및 성능 테스트, 그리고 와일드카드 매칭에 대한 신뢰할 수 있는 비재귀 알고리즘 검색 실패에서 시작된 프로그래머 피드백의 이력을 기반으로 합니다.싱글와이루프(single while loop)로 구현된 초기 알고리즘은 소프트웨어 개발자의 코멘트를 신속하게 유도하여 [1]개선으로 이어졌습니다.계속적인 코멘트와 제안으로[2][3] 인해 여전히 싱글와이루프 형태로 구현되고 있는 개정 알고리즘은 테스트 케이스와 퍼포먼스 [4]프로파일러의 컬렉션에 근거해 개량되었습니다.프로파일러를 사용한 single while loop 조정 경험은 특히 빈 입력 문자열 또는 와일드카드 [5]문자를 포함하지 않는 입력이 포함된 상황에서 성능을 향상시키는 2-loop 전략의 개발을 촉진했습니다.2루프 알고리즘은 Apache License v.2.0의 조건에 따라 오픈 소스 소프트웨어 개발 커뮤니티에서 사용할 수 있으며 테스트 케이스 코드가 포함되어 있습니다.

사용.

Apache 라이선스로 제공되는 알고리즘은 포인터 기반 C++와 휴대용 C++(포인터 없이 구현됨) 모두에서 구현됩니다.Apache 라이선스로도 사용할 수 있는 테스트 케이스 코드는 아래의 패턴 매칭 연산을 제공하는 모든 알고리즘에 적용할 수 있습니다.코드화된 구현에서는 멀티바이트 문자 집합을 처리할 수 없으며 검색 중인 텍스트에 호환되지 않는 문자 집합이 여러 개 포함되어 있을 경우 문제가 발생합니다.

패턴 매칭 조작

알고리즘은 다음 3가지 패턴 매칭 연산을 지원합니다.

  • 패턴내의 아스타리스크(*) 또는 물음표(?) 문자를 제외하고, 패턴과 일치하고 있는 송신원간에 1 대 1의 일치가 실행됩니다.
  • 아스타리스크(*) 문자는 0 이상의 임의의 시퀀스와 일치합니다.
  • 물음표(?) 문자는 임의의 단일 문자와 일치합니다.

예

  • *foo*는 "foo"를 포함하는 모든 문자열과 일치합니다.
  • mini*는 "mini"로 시작하는 모든 문자열과 일치합니다("mini" 문자열 자체 포함).
  • ?*는 3글자 이상의 문자열과 일치합니다.

적용들

원래 알고리즘은 Data Access Worldwide 코드 라이브러리에서 사용하기 위해 Larry Heiges에[6] 의해 DataFlex 프로그래밍 언어로 이식되었습니다.로그 파일 [7]리더의 일부로 수정된 형태로 GitHub에 게시되었습니다.2014 알고리즘은 Epic Games Unreal Engine 게임 [8][9]엔진에 내장된 Unreal Model Viewer의 일부입니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Krauss, Kirk (2008). "Matching Wildcards: An Algorithm". Dr. Dobb's Journal.
  2. ^ "wild card searching". alt.os.development. 2008.
  3. ^ T.J. (2014). "wild card matching in text string". Stack Overflow.
  4. ^ Krauss, Kirk (2014). "Matching Wildcards: An Empirical Way to Tame an Algorithm". Dr. Dobb's Journal.
  5. ^ Krauss, Kirk (2018). "Matching Wildcards: An Improved Algorithm for Big Data". Develop for Performance.
  6. ^ Heiges, Larry (2008). "Text compare function - generalTextCompare.txt". Data Access Worldwide Code Library.
  7. ^ Deniskore (2013). "Deniskore/wildcard/CLogReader.cpp". Popular repositories. GitHub. 173-279호선
  8. ^ gildor2 (2016). "UModel/Core/Core.cpp". Unreal Engine Model Viewer (UE Viewer). GitHub. 334-435번 라인
  9. ^ gildor2 (2016). "History for UModel/Core/Core.cpp". Unreal Engine Model Viewer (UE Viewer).