아포토리코-지안카를로 알고리즘

컴퓨터 공학에서 아포툴리코-지안카를로 알고리즘은 보이어-모어 문자열 검색 알고리즘의 변형으로, 의 기본 적용은 텍스트 T ${\displaystyle T}$에서 $패턴{\displaystyle }$ P ${\displaystyle P}$의 발생을 검색하고 있다$.$ 다른 비교 기반 문자열 검색과 마찬가지로 $P{\displaystyle }$ ${\displaystytyle P$를 정렬하여 수행된다.$}$을(를$)$ $특정$ 인덱스 T {\displaystyle $T}$에 연결하고 해당 인덱스에서 일치하는지 확인하십시오.${\displaystyle }$그런 다음 보이어-모어 알고리즘의 규칙에 따라$$ $P{\displaystyle }$ ${\displaystyle P}$을(를) T ${\displaystyle T}$과(와) 비교하여 이동하며$$, 이 $프로세스$는$$T {\$displaystytle$ T$}$의 끝에 도달할$$ 때까지 반복된다.Boyer-Moore 시프트 규칙을 적용하면 텍스트의 상당 부분이 완전히 생략되는 경우가 많다.

교대작전에 관해서는 아포툴리코-지안카를로(Apropolico-Giancarlo)는 보이어-무어(Boyer-Moore)와 기능면에서 정확히 동일하다.아포툴리코-지안카를로의 효용은 어떤 지표에서든 매치 체크 작업을 빠르게 하는 것이다.Boyer-Moore의 경우 $T{\displaystyle }$ ${\displaystyle T}$에서 $P{\displaystyle }$ ${\displaystyle P}$의 $발생$을 찾으려면 $P{\displaystyle }$ ${\displaystyle N}$$자$ 모두가$$ 명시적으로 일치해야$$ 한다$$.특정 패턴과 텍스트의 경우 이는 매우 비효율적이다. 간단한 예는 패턴과 텍스트가 동일한 반복 문자로 구성되었을 때, 보이어-무어는 $O{\displaystyle }$ (${\displaystyle n}$m ${\displaystyle )}$ ${\displaystyle O(nm)$로 실행되며$,$ 여기서 $m{\displaystyle }$ ${\displaystyle m}$은 $T{\displaystyle }$ ${\displaystyty T}$의 문자 길이입니다$.$ 아포토리코-지안카를로 속도가 이 U.p 표에$$ $T{\displaystyle }$ ${\displaystyle T}$의 정렬에서 일치하는 문자 수를 기록하여 일치하는 것으로 알려진 문자 시퀀스에 대한 중복된 동일성 검사를 피하기 위해$$ $P{\displaystyle }$ ${\displaystyle P}$의 사전 처리 중에 수집된 데이터와 결합된다.갈일 통치의 일반화로 볼 수 있다.

참조

• Apostolico, Alberto; Giancarlo, Raffaele (1986). "The Boyer–Moore–Galil String Searching Strategies Revisited". SIAM Journal on Computing. 15: 98–105. doi:10.1137/0215007.
• Crochemore, Maxime; Lecroq, Thierry (1997). "Tight bounds on the complexity of the Apostolico-Giancarlo algorithm" (PDF). Information Processing Letters. 63 (4): 195–203. doi:10.1016/S0020-0190(97)00107-5.
• Crochemore, M.; Rytter, W. (1994). Text Algorithms. Oxford University Press.
• Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press. ISBN 0-521-58519-8.
• Lecroq, T. (1992). Recherches de Mots (Ph. D. Thesis). University of Orléans.
• Lecroq, Thierry (1995). "Experimental results on string matching algorithms". Software: Practice and Experience. 25 (7): 727–765. doi:10.1002/spe.4380250703. S2CID 15253073.