Commentz-Walter 알고리즘

Commentz-Walter algorithm

컴퓨터 과학에서 Commentz-Walter 알고리즘은 Beate Commentz-Walter에 의해 발명된 문자열 검색 알고리즘입니다.[1]Aho-Corasick 문자열 매칭 알고리즘처럼 여러 패턴을 한 번에 검색할 수 있습니다.이것은 아호-코라식의 아이디어와 보이어-무어 문자열 검색 알고리즘의 빠른 매칭을 결합합니다.텍스트 길이가 n이고 최대 패턴 길이가 m인 경우 최악의 경우 실행 시간은 O(mn)이지만, 평균 경우가 훨씬 더 나은 경우가 많습니다.[2]

GNU grep은 Commentz-Walter와 매우 유사한 문자열 매칭 알고리즘을 구현한 적이 있습니다.[3]

역사

알고리즘에 대한 논문은 1979년 Beate Commentz-Walter에 의해 Saarland 대학을 통해 처음 발표되었고 "R"로 타이핑되었습니다.슈어너."[1]이 논문은 그가 주장한 두 가지 상이한 알고리즘을 상세히 설명했는데, 이는 그가 알고리즘 B와 B1이라고 부르는 아호-코라식과 보이어-무어 알고리즘의 아이디어를 결합한 것입니다.그러나 이 논문은 대부분 알고리즘 B에 초점을 맞추고 있습니다.

알고리즘 작동 방식

샘플 반전 패턴 트리

Commentz-Walter 알고리즘은 다중 패턴 매칭 문제를 더 잘 해결하기 위해 두 개의 알려진 알고리즘을 결합합니다.이 두 알고리즘은 필터링을 사용하여 단일 패턴 매칭을 처리하는 보이어-무어와 아호-코라식입니다.이를 위해 알고리즘은 접미사 오토마톤을 구현하여 입력 문자열 내의 패턴을 검색하는 동시에 Aho-Corasick와는 달리 역패턴을 사용합니다.[4]

Commentz-Walter는 컴퓨팅 전 단계와 매칭 단계라는 두 단계를 거쳐야 합니다.첫 번째 단계에서 Commentz-Walter 알고리즘은 반전 패턴을 사용하여 패턴 트리를 구축하며, 이는 컴퓨팅 전 단계로 간주됩니다.매칭 단계로 알려진 두 번째 단계는 다른 두 알고리즘을 고려합니다.Commentz-Walter 알고리즘은 Boyer-Moore의 시프트 기법과 Aho-Corasick의 유한 오토마타 기법을 이용하여 정합을 시작할 수 있습니다.[4]

Commentz-Walter 알고리즘은 입력 문자열 전체에서 뒤로 스캔하여 불일치 여부를 검사합니다.알고리즘이 일치하지 않는 경우 알고리즘은 일치하는 문자 중 일부를 이미 알고 있으며 이 정보를 인덱스로 사용합니다.알고리즘은 인덱스를 사용하여 사전 계산된 테이블을 확인하여 이동해야 할 거리를 찾고, 이후 알고리즘은 다시 한 번 일치 시도를 시작합니다.

시간 복잡도

Aho-Corasick을 Commentz-Walter 알고리즘과 비교하면 시간 복잡도 개념으로 결과가 나옵니다.Aho-Corasick은 선형 O(m+n+k)로 간주되며, k는 일치 횟수입니다.Commentz-Walter는 2차 O(mn)로 간주될 수 있습니다.이에 대한 이유는 Commentz-Walter가 Boyer-Moore 문자열 검색 알고리즘 내의 이동을 Aho-Corasick에 추가하여 개발되어 복잡성이 선형에서 2차로 이동했기 때문입니다.

"The Journal of National Science Foundation of Srikan 46"에서 한 연구에 따르면 Commentz-Walter는 일반적으로 Aho-Corasick 문자열 일치 알고리즘보다 더 빠른 것으로 보입니다.저널에 의하면, 이것은 긴 패턴을 사용할 때만 존재한다고 합니다.그러나 저널은 이 진술에 대해 비판적인 분석이 없으며 알고리즘의 성능에 대한 일반적인 합의가 부족하다고 말합니다.[5]

"The International Journal of Advanced Computer Science and Information Technology"의 연구에서 알고리즘의 실행 시간을 시각화한 것에서 볼 수 있듯이, 패턴 세트 내에서 가장 짧은 패턴이 증가함에 따라 알고리즘의 성능은 선형적으로 증가했습니다.[4]

얼터너티브

원래 Commentz-Walter 논문에서는 대체 알고리즘도 작성되었습니다.B1이라고 알려진 이 알고리즘은 스캔 단계에서 패턴 트리가 사용되는 방식에 유일한 차이점이 있는 주 Commentz-Walter 알고리즘과 유사하게 작동합니다.

이 논문은 또한 이 알고리즘이 전처리 단계와 검색 단계의 실행 시간과 공간을 증가시키는 비용으로 더 잘 수행된다고 주장합니다.그러나 이 알고리즘은 다른 연구에서 공식적으로 테스트되지 않았기 때문에 실제 성능은 알 수 없습니다.[1]

참고문헌

  1. ^ a b c Commentz-Walter, Beate (1979). A String Matching Algorithm Fast on the Average (PDF). International Colloquium on Automata, Languages and Programming. LNCS. Vol. 71. Graz, Austria: Springer. pp. 118–132. doi:10.1007/3-540-09510-1_10. ISBN 3-540-09510-1. Archived from the original (PDF) on 2017-10-10.
  2. ^ Watson, Bruce William (1995-09-15). Taxonomies and toolkits of regular language algorithms. Eindhoven University of Technology. doi:10.6100/IR444299. ISBN 90-386-0396-7.
  3. ^ "grep: remove Commentz-Walter code". GNU grep. 2017-01-18. Retrieved 2022-05-15.
  4. ^ a b c Akinul Islam Jony (2014). "Analysis of Multiple String Pattern Matching Algorithms" (PDF). International Journal of Advanced Computer Science and Information Technology (IJACSIT). 3 (4): 344–353. ISSN 2296-1739.
  5. ^ Dewasurendra, SD; Vidanagamachchi, SM (2018). "Average time complexity analysis of Commentz-Walter algorithm". Journal of the National Science Foundation of Sri Lanka. 46 (4): 547–557. doi:10.4038/jnsfsr.v46i4.8630.