일치 와일드카드

컴퓨터 과학에서 와일드카드 일치 알고리즘(글로빙이라고도 함)은 와일드카드 구문을 포함할 수 있는 텍스트 문자열을 비교하는 데 유용하다.^[1]이러한 알고리즘의 일반적인 용도는 본 셸^[4] 또는 마이크로소프트 윈도우즈[2] 명령줄^[3] 또는 텍스트 편집기 또는 파일 매니저와 같은 명령줄 인터페이스와 일부 검색 엔진 및 데이터베이스용 인터페이스를 포함한다.^[5]와일드카드 매칭은 일반적으로 정규식과 문자열 매칭을 일치시키는 문제의 하위 집합이다.^[6]

문제

와일드카드 계산자는 와일드카드 패턴 p를 입력 문자열 s에 대해 테스트한다.고정된 경기를 수행하고, p가 전체 s와 일치해야 true를 반환한다.

이 패턴은 모든 공통 구문에 기초할 수 있지만(글로빙 참조), Windows 프로그래머들은 기본 C 런타임에 의해 지원되는 단순화된 구문에 대해서만 논하는 경향이 있다.^[7][8]

• 이스케이프 문자가 정의되지 않음
• 와일드카드:?어떤 등장인물이든 정확히 일치한다. *임의의 많은 (0 포함) 문자 발생을 일치시킨다.

이 글에서는 달리 명시되지 않는 한 주로 윈도우의 문제 제형에 대해 논한다.

정의

제로 기반 인덱스에 명시된 와일드카드 매칭 문제는 다음과 같이 재귀적으로 정의할 수 있다.

${\displaystyle {\begin{aligned}m_{00}&=(p_{0}=t_{0})\\m_{0j}&=(p_{j-1}={\text{‘*’}})\land m_{0,j-1}\\m_{i0}&={\text{false}}\\m_{ij}&={\begin{cases}m_{i-1,j-1}&{\text{for}}\;p_{i-1}=t_{j-1}\lor p_{i-1}={\text{‘?’}}\\m_{i,j-1}\lor m_{i-1,j}&{\text{for}}\;p_{i-1}={\text{‘*’}}\\{\text{false}}&{\text{for}}\;p_{i-1}\neq t_{j-1}\end{cases}}&&\quad {\text{for}}\;1\leq i\leq p ,1\leq j\leq t .\end{aligned}}}$

여기서 m은_ij 각각 i와 j 문자로 잘린 텍스트와 패턴 p를 일치시킨 결과물이다.이것은 리히터의 알고리즘과 칸타토어의 컬렉션에서 발견된 스니펫 알고리즘에 의해 사용되는 공식이다.^[9][10]이 설명은 레벤슈테인 거리와 유사하다.

관련 문제

컴퓨터 과학에서 직접적으로 관련된 문제에는 다음이 포함된다.

• 상관 없음 또는 공백과의 패턴 매칭, 의 등가만 있는 연결되지 않은 문자열 검색?규정된^[11][12]
• 와일드카드를 사용한 패턴 일치, 두 와일드카드를 모두 정의한 연결되지 않은 문자열 검색.유연한 와일드카드 변종과의 패턴 매칭에서 길이 바운드가 주어지지 않는 한 지수 런타임을 가진다.^[13]

역사

와일드카드를 매칭하는 초기 알고리즘은 재귀에 의존하는 경우가 많았지만 성능과^[10] 신뢰성^[8] 등을 고려해 비판받았다.와일드카드를 매칭하기 위한 비반복 알고리즘은 이러한 고려사항에 비추어 인기를 얻었다.

재귀 알고리즘과 비재귀 알고리즘 모두 아래에서 참조하는 다양한 예제 알고리즘에서 입증되었듯이 패턴 매칭 연산을 수행하기 위한 전략은 매우 다양하다.테스트 사례 개발 및 성능 최적화 기법은 특히 재귀 알고리즘의 비평가들에 의해 개발된 특정 알고리즘에 대해 입증된 바 있다.

재귀 알고리즘

재귀는 일반적으로 일치할 때 발생한다.*더 많은 접미사가 있을 때이것은 일종의 역추적(backtracking)으로, 어떤 규칙적인 표현 매칭자들에 의해서도 행해진다.

• Rich Salz의 와일드매트 알고리즘(sh 유사 구문)^[14]
• 필리핀의 알고리즘과^[15] 비그네스 무루게산의 알고리즘^[16]
• 마틴 리히터의 알고리즘^[9](^[17]Snippets와 동일하고 7-zip 알고리즘과 관련됨)
• C 라이브러리 fnmatch 구현(지원)[...]및 다중 바이트 문자 집합:
  • 구이도 판 로섬의 BSD libc fnmatch,^[18] 애플 libc의^[19] 일부분
  • Glibc fnmatch^[20]

이러한 알고리즘의 일반적인 형태는 같다.재귀 시 알고리즘은 입력을 서브스트링으로 자르고, 서브스트링 중 하나가 양의 일치를 반환할 때 일치가 발생한 것으로 간주한다.을 위해dowild("*X", "abcX"), 그것은 탐욕스럽게 부를 것이다.dowild("X", "abcX"),dowild("X", "bcX"),dowild("X", "cX"), 그리고dowild("X", "X")일반적으로 기능 지원 같은 덜 중요한 사항과 작지만 매우 효과적인 최적화와 같은 더 중요한 요인에 의해 차이가 난다.그 중 일부는 다음과 같다.

• 과대 재호출에 대한 ATABT 신호(Lars Mathiesen 1991).문자열(패턴 및 텍스트)의 나머지 부분까지 순진하게 반복하는 것이 올바르지만*그리고 서브스트링 중 하나가 양의 일치를 반환하도록 하고, 실행 시간은 많은 일치를 거부하는 지수적인 시간이 된다.*본문에서라르스 마티센은 반환점을 매치, 노매치, ARBAG(별표 재귀에 대해서는 전혀 매치할 수 없음)의 3개 클래스로 변경한다.ARBORT 값은 텍스트가 너무 일찍 소비되거나 다른 별표 일치에 실패할 때 반환되어 별표 수에 대한 선형 성능을 보장한다. (전체적으로 복잡성은 일치하도록 남겨진 문자 수에 2차적으로 추가된다.)^[14]Git/Rsync의 와일드매치 ABORT도 유효하지 않은 입력을 다룬다.^[21]새로운 INN Uwildmat도 마찬가지다.^[22]
• 재귀에 별표가 전진한다.이 와일드매치 트위크는 비교적 경미하다.그것은 재귀가 "abcX"에서 "*X"와 일치하기를 원하는 경우에 적용된다: 별표 뒤에 "X"와 같은 리터럴이 뒤따를 때, 동일한 길이의 마지막 비교만이 성냥을 만들 기회를 가질 것이 분명하다.^[21]이것은 2000년의^[22] 우와일드마트에서 더 일찍 보여지고 밴 로섬의 fnmatch에서 더 암시적으로 보여진다.FNM_PATHNAME.

마틴 리히터의 알고리즘은 전체 연산은 등가지만 이 패턴의 예외다.*에서는 문제의 동적 프로그래밍 공식에 따라 두 인덱스 중 하나를 증가시킨다."ABORT" 기법도 여기에 적용된다.^[9](칸타토어가 테스트한 대로) 일반적인 패턴에서, 그것은 탐욕스러운 호출 구현보다 느리다.^[10]

재귀 알고리즘은 일반적으로 추론하기가 더 쉬우며, ABORT 수정으로 최악의 경우 복잡성을 허용 가능한 수준으로 수행한다.*가 없는 문자열에서는 고정된 일대일 관계가 있기 때문에 일치하는데 선형 대 문자열 크기 시간이 걸린다.

비복귀 알고리즘

다음은 재귀 알고리즘 비평가들에 의해 개발되었다.

• IBM이^[8][23] 사용하는 Kirk J. Krauss의 와일드카드 매칭 알고리즘
• 알레산드로 칸타토어의 와일드카드 매칭 알고리즘^[10] 모음
• Dogan Kurt의 반복적인 매처와 느린 NFA 매처.^[17]
• 실러의 잘못된 알고리즘(메일)MATCH("da*da*da*", "daaadabadmanda"))^[24]

다음은 아니다.

• 잭 핸디의 잘못된 알고리즘^[25](메일)MATCH("*?", "xx"))

위의 반복 기능은 오래된 패턴/텍스트 포인터 세트를 저장하여 역추적을 구현하고, 일치가 실패할 경우 역추적을 실행한다.커트에 따르면, 성공적인 경기는 단 한 번만 필요하므로, 그러한 세트는 단 한 세트만 저장하면 된다.^[17]

또 와일드카드 매칭 문제는 순진한 문자교체 방식을 이용해 정규식 매칭으로 전환할 수 있다.톰프슨의 구축과 같은 비복귀적 정규 표현 매칭은 역참조 지원이 없어 실제 사용량이 적지만, 일반적으로 와일드카드 매칭은 유사한 풍부한 기능 집합을 가지고 있지 않다.(사실, 위의 알고리즘 중 많은 것은 에 대한 지원만 가지고 있다.?, 그리고*.) Thompson NFA의 Russ Cox 구현은 이를 위해 사소한 수정도 할 수 있다.^[26]구스타보 나바로의 기반 nrgrep 알고리즘은 효율적인 접미사를 강조하여 보다 효율적인 구현을 제공한다.^[27]정규식 § 구현을 참조하십시오.

참고 항목

• 패턴 매칭
• 패턴 미적분학
• 글로브(프로그래밍)
• 와일드카드 문자
• 알고리즘 목록

참조