문자열 검색 알고리즘

컴퓨터 과학에서 문자열 검색 알고리즘은 문자열 매칭 알고리즘이라고도 불리며 큰 문자열 또는 텍스트 내에서 하나 또는 여러 문자열(패턴이라고도 함)이 발견되는 위치를 찾는 중요한 문자열 알고리즘 클래스입니다.

문자열 검색의 기본적인 예로는 패턴과 검색된 텍스트가 알파벳(소수 집합) δ의 요소의 배열인 경우를 들 수 있다. δ는 인간의 언어 알파벳일 수 있다.예를 들어 A에서 Z까지의 애플리케이션은 바이너리 알파벳(소수 = {0,1}) 또는 바이오 인폼에서 DNA 알파벳(소수 = {A, C, C)을 사용할 수 있다.

실제로 실행 가능한 문자열 검색 알고리즘 방식은 문자열 인코딩의 영향을 받을 수 있습니다.특히 가변폭 인코딩을 사용하는 경우 N번째 문자를 찾는 데 시간이 걸릴 수 있습니다.이로 인해 일부 검색 알고리즘이 상당히 느려질 수 있습니다.가능한 해결책 중 하나는 코드 유닛의 시퀀스를 검색하는 것이지만,^{[citation needed]} 이를 회피하도록 특별히 설계된 인코딩이 아닌 이상 잘못된 일치가 발생할 수 있습니다.

개요

문자열 검색의 가장 기본적인 예로는 건초 더미라고 불리는 1개의 (종종 매우 긴) 문자열과 바늘이라고 불리는 1개의 (종종 매우 짧은) 문자열이 있습니다.목표는 건초더미에서 바늘이 하나 이상 발생하는 것을 찾는 것입니다.예를 들어 다음과 같은 범위 내에서 검색할 수 있습니다.

어떤 책은 맛보고, 어떤 책은 삼키고, 어떤 책은 씹고 소화해야 한다.

4번째 단어인 "to"의 첫 번째 오카렌스나 3번째 오카렌스 또는 마지막 오카렌스인 "to"의 마지막 오카렌스를 요구할 수 있습니다.

단, 매우 일반적으로 다양한 제약이 추가됩니다.예를 들어, "니들"은 1개 이상의 완전한 단어로 구성되어 있는 경우에만 일치시킬 수 있습니다.어느 쪽이든 바로 옆에 다른 문자가 없는 것으로 정의되어 있을 수 있습니다.이 경우 위의 예문에 대해 "hew" 또는 "low" 검색은 실패하지만 리터럴 문자열은 발생합니다.

또 다른 일반적인 예로는 "정규화"가 있습니다.많은 목적을 위해, "to"와 "be" 사이에 다른 무언가가 개입하는 장소에서도 "be"와 같은 문구를 찾는 것은 성공해야 한다.

여러 공간
탭, 구분 없는 공백, 줄 바꿈 등과 같은 기타 "공백" 문자.
하이픈 또는 소프트하이픈은 거의 없습니다.
구조화된 텍스트, 태그 또는 각주, 목록 번호 또는 기타 마커, 내장된 이미지 등과 같이 임의로 크지만 "가상"인 것들도 있습니다.

많은 기호 시스템에는 동의어 문자가 포함되어 있습니다(적어도 일부 목적의 경우).

라틴 베이스의 알파벳은 소문자와 대소문자를 구별하지만, 많은 목적으로 문자열 검색은 그 구별을 무시합니다.
많은 언어에는 하나의 복합 문자가 두 개 이상의 다른 문자와 동일한 연결자가 포함되어 있습니다.
많은 문자 체계는 악센트나 모음 포인트와 같은 발음 구별 기호를 포함하고 있으며, 사용법이 다양하거나 일치에 있어 중요도가 다를 수 있습니다.
DNA 염기서열은 어떤 목적을 위해 무시될 수 있는 비부호화 세그먼트 또는 다른 목적을 위해 진정한 차이로 간주되지 않을 수 있는 부호화 단백질의 변화를 초래하지 않는 다형성을 포함할 수 있다.
일부 언어에는 단어의 시작, 중간 또는 끝에 다른 문자나 형식을 사용해야 하는 규칙이 있습니다.

마지막으로, 자연어를 나타내는 문자열은 언어 자체의 측면이 관여하게 됩니다.예를 들어, 대체 철자, 접두사 또는 접미사 등을 가지고 있음에도 불구하고 "단어"의 모든 항목을 찾고자 할 수 있습니다.

또 다른 복잡한 유형의 검색은 정규 표현식 검색입니다.이 검색에서는 사용자가 문자나 기타 기호의 패턴을 작성하고 패턴과 일치하는 경우 검색을 완료해야 합니다.예를 들어, 미국 영어 단어 "color"와 이에 상응하는 영국 영어 단어 "color"를 모두 잡으려면 두 개의 다른 문자 문자열을 검색하는 대신 다음과 같은 정규 표현을 사용할 수 있습니다.

colu?r

여기서 "?"는 일반적으로 앞의 문자("u")를 옵션으로 만듭니다.

이 기사에서는 보다 단순한 종류의 문자열 검색을 위한 알고리즘에 대해 주로 설명합니다.

생물정보학 및 유전체학 분야에서도 마찬가지로 MEM(^[1]Maximal exact matching)이 있습니다.두 개의 문자열이 주어졌을 때 MEM은 ^[2]불일치를 일으키지 않고 좌우로 확장할 수 없는 일반적인 기판입니다.

검색 알고리즘의 예

단순 문자열 검색

하나의 문자열이 다른 문자열 내에서 발생하는 위치를 확인하는 간단하고 비효율적인 방법은 각 인덱스를 하나씩 확인하는 것입니다.우선 건초 더미의 첫 번째 문자로 시작하는 바늘 복사본이 있는지 확인하고, 없으면 건초 더미의 두 번째 문자로 시작하는 바늘 복사본이 있는지 확인합니다.통상적인 경우 잘못된 위치별로 1~2자만 보면 위치가 잘못되었음을 알 수 있습니다.따라서 평균적인 경우 O(n+m) 스텝이 필요합니다.여기서 n은 건초 더미의 길이, m은 바늘의 길이입니다.그러나 최악의 경우 "aaaaaaab"과 같은 문자열에서 "aaaaaaaaaaab"를 검색하면 됩니다.O(nm)

유한 상태 자동 기반 검색

이 접근법에서는 저장된 검색 문자열을 인식하는 결정론적 유한 오토마톤(DFA)을 구성함으로써 역추적이 회피됩니다.이것들은 구축 비용이 많이 듭니다.일반적으로 파워셋 구조를 사용하여 작성되지만 매우 빠르게 사용할 수 있습니다.예를 들어 오른쪽에 표시된 DFA는 "MOMMY"라는 단어를 인식합니다. 이 접근법은 실제로 임의의 정규 표현을 검색하기 위해 일반화되어 있는 경우가 많습니다.

스텁

Knuth-Morris-Pratt는 검색할 문자열이 있는 입력을 접미사로 인식하는 DFA를 계산하고, Boyer-Moore는 바늘 끝에서 검색을 시작하므로 보통 각 단계에서 바늘 길이만큼 앞으로 점프할 수 있습니다.Baeza – Yates는 이전 j 문자가 검색 문자열의 접두사인지 여부를 추적하므로 퍼지 문자열 검색에 적용할 수 있습니다.비트맵 알고리즘은 Baeza-Yates 접근방식을 적용한 것입니다.

인덱스 방식

빠른 검색 알고리즘이 텍스트를 사전 처리합니다.예를 들어 접미사 트리나 접미사 배열과 같은 서브스트링 인덱스를 구축한 후 패턴 발생을 빠르게 찾을 수 있습니다.예를 들어 접미사 트리는 $\Theta (n)$ δ ( n ) \Displaystyle $\Theta ( n$ 내에 구축할 수 있으며 패턴의 모든z \ $displaystyle z$ 는 $z$ 알파벳의 크기가 일정하고 트리의 모든 $내부$ 노드가 그 아래에 무엇이 있는지 알고 있다고 가정할 때 $O(m)$ O ( $)시간$ $O(m)$ 에 찾을 수 있습니다.후자는 서픽스트리의 루트에서 DFS 알고리즘을 실행하여 실행할 수 있습니다.

기타 변종

예를 들어 trigram 검색과 같은 일부 검색 방법은 "일치/비일치"가 아니라 검색 문자열과 텍스트 사이의 "근접성" 점수를 찾기 위한 것입니다.이러한 검색은 "퍼지" 검색이라고도 합니다.

검색 알고리즘의 분류

여러 패턴에 따른 분류

다양한 알고리즘은 각각 사용하는 패턴의 수에 따라 분류할 수 있습니다.

단일 패턴 알고리즘

다음 컴파일에서 m은 패턴의 길이, n은 검색 가능한 텍스트의 길이, k = δ는 알파벳의 크기이다.

알고리즘.	전처리시간	매칭^[1] 타임	공간
Nave 알고리즘	없음.	δ(mn)	없음.
라빈카르프	θ(m)	평균 Ω(n) 최악의 경우 O(mn)	O(1)
크누트-모리스-프랫	θ(m)	θ(n)	θ(m)
보이어-무어	δ(m + k)	기껏해야 Ω(n/m), 최악의 경우 O(mn)	θ(k)
이원 알고리즘^[3]^[2]	θ(m)	O(n)	O(1)
역방향 비결정적 DAWG 매칭(BNDM)^[4]^[3]	O(m)	O(n)
역방향 Oracle 매칭(BOM)^[5]	O(m)	O(mn)

1.^ 점근 시간은 O, δ 및 δ 표기로 표현됩니다.

2.^ glibc^[6] 및 musl [7] C 표준 라이브러리에서 memem 및 strstr 검색 기능을 구현하기 위해 사용합니다.

3.^ 정규언어로 표현되는 대략적인 문자열 매칭 및 (잠재적으로 무한)^{[citation needed]} 패턴 세트를 처리하도록 확장할 수 있습니다.

Boyer-Moore 문자열 검색 알고리즘은 실제 문자열 검색 ^[8]문헌의 표준 벤치마크가 되어 왔습니다.

한정된 패턴 세트를 사용하는 알고리즘

다음 컴파일에서 M은 가장 긴 패턴의 길이, 총 길이, 검색 가능한 텍스트의 길이, 발생 횟수입니다.

알고리즘.	확장	전처리시간	매칭^[4] 타임	공간
아호코라식	크누트모리스프라트	θ(m)	δ(n + o)	θ(m)
코멘트 발터	보이어무어	θ(m)	δ(M * n) 최악의 경우 평균^[9] 준선형의	θ(m)
Set-BOM	역방향 Oracle 매칭

무한한 수의 패턴을 사용하는 알고리즘

당연히 이 경우 패턴을 완전히 열거할 수 없습니다.그것들은 보통 정규 문법이나 정규 표현으로 표현된다.

전처리 프로그램 사용에 따른 분류

다른 분류 접근법이 가능하다.가장 일반적인 기준 중 하나는 전처리를 주요 기준으로 사용합니다.

문자열 검색 알고리즘^[10] 클래스

	텍스트가 전처리되지 않았습니다.	텍스트 전처리
전처리되지 않은 패턴	기본 알고리즘	인덱스 방식
전처리된 패턴	구성된 검색 엔진	서명 방식:^[11]

전략별 분류

또 다른 알고리즘은 일치 ^[12]전략에 따라 알고리즘을 분류합니다.

접두사를 먼저 일치시킵니다(Knuth-Morris-Pratt, Shift-And, Aho-Corasick).
접미사를 먼저 일치시킵니다(Boyer-Moore 및 변종, Commentz-Walter).
최적 요인(BNDM, BOM, Set-BOM)을 먼저 일치시킵니다.
기타 전략(Nave, Rabin-Karp)

「」를 참조해 주세요.

레퍼런스

^ Kurtz, Stefan; Phillippy, Adam; Delcher, Arthur L; Smoot, Michael; Shumway, Martin; Antonescu, Corina; Salzberg, Steven L (2004). "Versatile and open software for comparing large genomes". Genome Biology. 5 (2): R12. doi:10.1186/gb-2004-5-2-r12. ISSN 1465-6906. PMC 395750. PMID 14759262.
^ Khan, Zia; Bloom, Joshua S.; Kruglyak, Leonid; Singh, Mona (2009-07-01). "A practical algorithm for finding maximal exact matches in large sequence datasets using sparse suffix arrays". Bioinformatics. 25 (13): 1609–1616. doi:10.1093/bioinformatics/btp275. PMC 2732316. PMID 19389736.
^ Crochemore, Maxime; Perrin, Dominique (1 July 1991). "Two-way string-matching" (PDF). Journal of the ACM. 38 (3): 650–674. doi:10.1145/116825.116845. S2CID 15055316. Archived (PDF) from the original on 24 November 2021. Retrieved 5 April 2019.
^ Navarro, Gonzalo; Raffinot, Mathieu (1998). "A bit-parallel approach to suffix automata: Fast extended string matching" (PDF). Combinatorial Pattern Matching. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 1448: 14–33. doi:10.1007/bfb0030778. ISBN 978-3-540-64739-3. Archived (PDF) from the original on 2019-01-05. Retrieved 2019-11-22.
^ Fan, H.; Yao, N.; Ma, H. (December 2009). "Fast Variants of the Backward-Oracle-Marching Algorithm" (PDF). 2009 Fourth International Conference on Internet Computing for Science and Engineering: 56–59. doi:10.1109/ICICSE.2009.53. ISBN 978-1-4244-6754-9. S2CID 6073627. Archived from the original on 2022-05-10. Retrieved 2019-11-22.
^ "glibc/string/str-two-way.h". Archived from the original on 2020-09-20. Retrieved 2022-03-22.
^ "musl/src/string/memmem.c". Archived from the original on 1 October 2020. Retrieved 23 November 2019.
^ Hume; Sunday (1991). "Fast String Searching". Software: Practice and Experience. 21 (11): 1221–1248. doi:10.1002/spe.4380211105. S2CID 5902579. Archived from the original on 2022-05-10. Retrieved 2019-11-29.
^ 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.
^ 멜리차, 보리보이, 얀 홀럽, J. 폴카.텍스트 검색 알고리즘.Volume I: Forward String Matching(전방향 문자열 매칭)제1.2권, 2005년http://stringology.org/athens/TextSearchingAlgorithms/ Wayback Machine에 2016-03-04 아카이브 완료.
^ Riad Mokadem; Witold Litwin http://www.cse.scu.edu/~tschwarz/Papers/vldb07_final.pdf (2007), Fast nGramBased String Search Over Data Encoded Using Algebraic Signatures, 33rd International Conference on Very Large Data Bases (VLDB) {{citation}}:외부 링크 surname2=(도움말)
^ Gonzalo Navarro; Mathieu Raffinot (2008), Flexible Pattern Matching Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences, ISBN 978-0-521-03993-2

R. S. Boyer와 J. S. Moore, 빠른 문자열 검색 알고리즘 Carom.ACM 20, (10), 262~272(1977)
토마스 H. 코먼, 찰스 E. 리저슨, 로널드 L. 리베스트, 클리포드 스타인.알고리즘 소개, 제3판MIT Press and McGraw-Hill, 2009.ISBN 0-262-03293-7.32장: 문자열 매칭, 페이지 985–1013.

외부 링크

패턴 매칭 링크의 방대한 리스트 최종 갱신일 : 2008년 12월 27일 20:18:38
문자열 일치 알고리즘의 대규모(유지 관리) 목록
NIST 문자열 일치 알고리즘 목록
String Search – Java에서의 고성능 패턴 매칭 알고리즘– Java에서의 다수의 String-Matching-Algorithm 구현 (BNDM, Boyer-Moore-Horspool, Boyer-Moore-Raita, Shift-Or)
Strings And Chars – Java에서 다수의 String-Matching-Algorithm 구현(단일 및 복수 패턴용)
정확한 문자열 매칭 알고리즘 - Java 애니메이션, 상세 설명 및 많은 알고리즘의 C 구현.
(PDF) 개량된 싱글 및 복수 근사 문자열 매칭
Kalign2: 단백질과 뉴클레오티드 배열의 고성능 다중 배열로 외부 특징 가능
NyoTengu – C의 고성능 패턴 매칭 알고리즘– C의 벡터 및 스칼라 문자열 매칭 알고리즘 구현

[1] Kurtz, Stefan; Phillippy, Adam; Delcher, Arthur L; Smoot, Michael; Shumway, Martin; Antonescu, Corina; Salzberg, Steven L (2004). "Versatile and open software for comparing large genomes". Genome Biology. 5 (2): R12. doi:10.1186/gb-2004-5-2-r12. ISSN 1465-6906. PMC 395750. PMID 14759262.

[2] Khan, Zia; Bloom, Joshua S.; Kruglyak, Leonid; Singh, Mona (2009-07-01). "A practical algorithm for finding maximal exact matches in large sequence datasets using sparse suffix arrays". Bioinformatics. 25 (13): 1609–1616. doi:10.1093/bioinformatics/btp275. PMC 2732316. PMID 19389736.

[3] Crochemore, Maxime; Perrin, Dominique (1 July 1991). "Two-way string-matching" (PDF). Journal of the ACM. 38 (3): 650–674. doi:10.1145/116825.116845. S2CID 15055316. Archived (PDF) from the original on 24 November 2021. Retrieved 5 April 2019.

[4] Navarro, Gonzalo; Raffinot, Mathieu (1998). "A bit-parallel approach to suffix automata: Fast extended string matching" (PDF). Combinatorial Pattern Matching. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 1448: 14–33. doi:10.1007/bfb0030778. ISBN 978-3-540-64739-3. Archived (PDF) from the original on 2019-01-05. Retrieved 2019-11-22.

[5] Fan, H.; Yao, N.; Ma, H. (December 2009). "Fast Variants of the Backward-Oracle-Marching Algorithm" (PDF). 2009 Fourth International Conference on Internet Computing for Science and Engineering: 56–59. doi:10.1109/ICICSE.2009.53. ISBN 978-1-4244-6754-9. S2CID 6073627. Archived from the original on 2022-05-10. Retrieved 2019-11-22.

[6] "glibc/string/str-two-way.h". Archived from the original on 2020-09-20. Retrieved 2022-03-22.

[7] "musl/src/string/memmem.c". Archived from the original on 1 October 2020. Retrieved 23 November 2019.

[:0-8] Hume; Sunday (1991). "Fast String Searching". Software: Practice and Experience. 21 (11): 1221–1248. doi:10.1002/spe.4380211105. S2CID 5902579. Archived from the original on 2022-05-10. Retrieved 2019-11-29.

[Commentz-Walter-9] 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.

[10] 멜리차, 보리보이, 얀 홀럽, J. 폴카.텍스트 검색 알고리즘.Volume I: Forward String Matching(전방향 문자열 매칭)제1.2권, 2005년http://stringology.org/athens/TextSearchingAlgorithms/ Wayback Machine에 2016-03-04 아카이브 완료.

[11] Riad Mokadem; Witold Litwin http://www.cse.scu.edu/~tschwarz/Papers/vldb07_final.pdf (2007), Fast nGramBased String Search Over Data Encoded Using Algebraic Signatures, 33rd International Conference on Very Large Data Bases (VLDB) {{citation}}:외부 링크 surname2=(도움말)

[12] Gonzalo Navarro; Mathieu Raffinot (2008), Flexible Pattern Matching Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences, ISBN 978-0-521-03993-2

[1]

[2]

[1]

[3]

[2]

[4]

[3]

[5]

[6]

[8]

[9]

[10]

[11]

[12]

v t 줄들
문자열 메트릭	대략적인 문자열 매칭 비트맵 알고리즘 다메라우-레벤슈테인 거리 거리 편집 게스탈트 패턴 매칭 해밍 거리 자로-윙클러 거리 리 거리 레벤슈테인 오토마톤 레벤슈테인 거리 바그너-피셔 알고리즘
문자열 검색 알고리즘	사도-장칼로 알고리즘 Boyer-Moore 문자열 검색 알고리즘 보이어-무어-호스풀 알고리즘 크누스-모리스-프랫 알고리즘 라빈-카르프 알고리즘
다중 문자열 검색	아호코라식 Commentz-Walter 알고리즘
정규 표현	정규 표현 엔진 비교 정규 문법 톰슨 구조 비결정론적 유한 오토마톤
시퀀스 얼라인먼트	히르슈베르크 알고리즘 니들맨분쉬 알고리즘 스미스-워터맨 알고리즘
data 구조	DAFSA 서픽스 배열 서픽스 오토마톤 접미사 트리 일반 접미사 트리 출렁 삼원 검색 트리 트리
다른.	해석 패턴 매칭 압축 패턴 매칭 최장 공통 서브시퀀스 최장 공통 서브스트링 순차적 패턴 마이닝 정렬

Search

문자열 검색 알고리즘

네임스페이스

더

목차

개요