문자열 검색 알고리즘

문자열 검색 알고리즘(string-searching algorithm), 때로는 문자열 일치 알고리즘(string-matching algorithm)이라고도 불리는 이 알고리즘은 문자열 본문에서 패턴과 일치하는 부분을 검색하는 알고리즘이다.

문자열 검색의 기본적인 예는 패턴과 검색되는 텍스트가 유한 집합 Σ의 알파벳 요소의 배열인 경우이다. Σ는 예를 들어 인간 언어의 알파벳(A부터 Z까지의 글자)일 수 있고, 다른 응용 분야에서는 이진 알파벳(Σ = {0,1}) 또는 생물정보학에서 DNA 알파벳(Σ = {A,C,G,T})을 사용할 수 있다.

실제로, 실현 가능한 문자열 검색 알고리즘의 방법은 문자열 인코딩에 영향을 받을 수 있다. 특히, 가변 너비 인코딩이 사용되는 경우, N번째 문자를 찾는 것이 더 느려질 수 있으며, N에 비례하는 시간이 필요할 수도 있다. 이는 일부 검색 알고리즘의 속도를 크게 저하시킬 수 있다. 가능한 많은 해결책 중 하나는 코드 단위의 시퀀스를 대신 검색하는 것이지만, 인코딩이 이를 피하도록 특별히 설계되지 않았다면 잘못된 일치(false matches)를 생성할 수 있다.

개요

문자열 검색의 가장 기본적인 경우는 하나(종종 매우 긴)의 문자열(때로는 건초 더미라고 불림)과 하나(종종 매우 짧은)의 문자열(때로는 바늘이라고 불림)을 포함한다. 목표는 건초 더미 내에서 바늘의 하나 이상의 발생을 찾는 것이다. 예를 들어, 다음에서 "to"를 검색할 수 있다.

Some books are to be tasted, others to be swallowed, and some few to be chewed and digested.

"to"의 첫 번째 발생(네 번째 단어) 또는 모든 발생(3개), 또는 마지막 발생(끝에서 다섯 번째 단어)을 요청할 수 있다.

그러나 매우 흔하게 다양한 제약 조건이 추가된다. 예를 들어, "바늘"이 하나(또는 그 이상)의 완전한 단어로 구성된 경우에만 일치시키기를 원할 수 있다. 이는 양쪽에 다른 글자가 즉시 인접하지 않는 것으로 정의될 수 있다. 이 경우 위 예문에서 "hew" 또는 "low"를 검색하면 해당 리터럴 문자열이 발생하더라도 실패해야 한다.

또 다른 흔한 예는 "정규화"를 포함한다. 많은 목적을 위해, "to be"와 같은 구문을 검색하면 "to"와 "be" 사이에 다른 것이 끼어들어도 성공해야 한다.

• 하나 이상의 공백
• 탭, 줄 바꿈 없는 공백, 줄 바꿈 등과 같은 다른 "공백" 문자
• 덜 흔하게, 하이픈 또는 소프트 하이픈
• 구조화된 텍스트에서는 태그 또는 심지어 임의로 크지만 "괄호형"인 것들(예: 각주, 목록 번호 또는 기타 표식, 포함된 이미지 등)

많은 기호 체계는 (적어도 일부 목적을 위해) 동의어인 문자를 포함한다.

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

마지막으로, 자연어를 나타내는 문자열의 경우 언어 자체의 측면이 관련된다. 예를 들어, 대체 철자, 접두사 또는 접미사 등이 있음에도 불구하고 "단어"의 모든 발생을 찾고 싶을 수 있다.

또 다른 더 복잡한 유형의 검색은 정규 표현식 검색으로, 사용자가 문자 또는 다른 기호의 패턴을 구성하고, 패턴과의 일치가 검색을 충족해야 한다. 예를 들어, 미국식 영어 단어 "color"와 영국식 등가어 "colour"를 모두 잡기 위해 두 개의 다른 리터럴 문자열을 검색하는 대신 다음과 같은 정규 표현식을 사용할 수 있다.

colou?r

여기서 "?"는 관례적으로 선행 문자("u")를 선택 사항으로 만든다.

이 기사는 주로 더 간단한 종류의 문자열 검색을 위한 알고리즘에 대해 다룬다.

생물정보학 및 유전체학 분야에서 도입된 유사한 문제는 최대 정확 일치(MEM)이다.^[1] 두 문자열이 주어졌을 때, MEM은 불일치를 일으키지 않고 왼쪽이나 오른쪽으로 확장될 수 없는 공통 부분 문자열이다.^[2]

검색 알고리즘의 예시

순진한 문자열 검색

한 문자열이 다른 문자열 안에 어디에 나타나는지 확인하는 간단하고 비효율적인 방법은 각 인덱스에서 하나씩 확인하는 것이다. 먼저, 건초 더미의 첫 번째 문자에서 시작하는 바늘의 복사본이 있는지 확인한다. 없으면, 건초 더미의 두 번째 문자에서 시작하는 바늘의 복사본이 있는지 확인하는 식으로 계속한다. 일반적인 경우, 각 잘못된 위치에 대해 한두 문자만 확인하면 잘못된 위치임을 알 수 있으므로, 평균적으로 O(n + m) 단계가 소요되며, 여기서 n은 건초 더미의 길이이고 m은 바늘의 길이이다. 하지만 최악의 경우, "aaaaaaaaab"와 같은 문자열에서 "aaaab"와 같은 문자열을 검색하는 데 O(nm)이 소요된다.

유한 상태 오토마타 기반 검색

이 접근 방식에서는 저장된 검색 문자열을 인식하는 결정론적 유한 오토마타(DFA)를 구성하여 백트래킹을 피한다. 이들은 구성하는 데 비용이 많이 들지만(일반적으로 멱집합 구성을 사용하여 생성됨), 사용하기에는 매우 빠르다. 예를 들어, 오른쪽에 표시된 DFA는 "MOMMY"라는 단어를 인식한다. 이 접근 방식은 실제로는 임의의 정규 표현식을 검색하도록 자주 일반화된다.

스텁

커누스-모리스-프랫 알고리즘은 검색할 문자열을 접미사로 가지는 입력을 인식하는 DFA를 계산한다. 보이어-무어는 바늘의 끝에서부터 검색을 시작하므로, 각 단계에서 전체 바늘 길이만큼 건너뛸 수 있다. 바에자-야테스(Baeza–Yates)는 이전 J개 문자가 검색 문자열의 접두사였는지 추적하므로, 퍼지 문자열 검색에 적용 가능하다. 비트맵 알고리즘은 바에자-야테스의 접근 방식의 응용이다.

인덱스 방식

더 빠른 검색 알고리즘은 텍스트를 미리 처리한다. 예를 들어 접미사 트리나 접미사 배열과 같은 부분 문자열 인덱스를 구축한 후에는 패턴의 발생을 빠르게 찾을 수 있다. 예를 들어, 접미사 트리는 ${\displaystyle \Theta (n)}$ 시간에 구축될 수 있으며, 알파벳이 일정한 크기를 가지고 접미사 트리의 모든 내부 노드가 그 아래에 어떤 리프가 있는지 알고 있다고 가정하면 패턴의 모든 ${\displaystyle z}$ 발생은 ${\displaystyle O(m)}$ 시간에 찾을 수 있다. 후자는 접미사 트리의 루트에서 DFS 알고리즘을 실행함으로써 달성될 수 있다.

기타 변형

일부 검색 방법, 예를 들어 삼진 검색은 검색 문자열과 텍스트 사이의 "일치/불일치"보다는 "근접성" 점수를 찾는 것을 목표로 한다. 이들은 때때로 "퍼지" 검색이라고 불린다.

검색 알고리즘의 분류

패턴 개수에 따른 분류

다양한 알고리즘들은 각자가 사용하는 패턴의 개수에 따라 분류될 수 있다.

단일 패턴 알고리즘

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

알고리즘	전처리 시간	일치 시간	공간
순진한 알고리즘	없음	평균 Θ(n+m), O(mn)	없음
오토마타 기반 일치	Θ(km)	Θ(n)	Θ(km)
라빈-카프	Θ(m)	평균 Θ(n), 최악 O(mn)	O(1)
커누스-모리스-프랫	Θ(m)	Θ(n)	Θ(m)
보이어-무어	Θ(m + k)	최선 O(n/m), 최악 O(mn)	Θ(k)
양방향 알고리즘[3]	Θ(m)	O(n)	O(log(m))
역방향 비결정적 DAWG 매칭 (BNDM)[4]	O(m)	최선 Ω(n/m), 최악 O(mn)
역방향 오라클 매칭 (BOM)[5]	O(m)	O(mn)

1.^ 점근 시간은 O, Ω, Θ 표기법을 사용하여 표현된다.

2.^ Glibc^[6] 및 Musl^[7] C 표준 라이브러리의 memmem 및 strstr 검색 함수를 구현하는 데 사용된다.

3.^ 근사 문자열 매칭 및 정규 언어로 표현되는 (잠재적으로 무한한) 패턴 집합을 처리하도록 확장할 수 있다.

보이어-무어 문자열 검색 알고리즘은 실용적인 문자열 검색 문헌의 표준 벤치마크였다.^[8]

유한 패턴 집합을 사용하는 알고리즘

다음 컴파일에서 M은 가장 긴 패턴의 길이이고, m은 이들의 총 길이, n은 검색 가능한 텍스트의 길이, o는 발생 횟수이다.

알고리즘	확장	전처리 시간	일치 시간	공간
아호-코라식	커누스-모리스-프랫	Θ(m)	Θ(n + o)	Θ(m)
콤멘츠-월터	보이어-무어	Θ(m)	최악 O(M * n) 평균 준선형[9]	Θ(m)
Set-BOM	역방향 오라클 매칭

무한 패턴 집합을 사용하는 알고리즘

당연히, 이 경우 패턴을 유한하게 열거할 수 없다. 이들은 일반적으로 정규 문법 또는 정규 표현식으로 표현된다.

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

다른 분류 접근 방식도 가능하다. 가장 일반적인 것 중 하나는 전처리를 주요 기준으로 사용한다.

문자열 검색 알고리즘 분류^[10]

	텍스트 전처리 없음	텍스트 전처리됨
패턴 전처리 없음	기본 알고리즘	인덱스 방법
패턴 전처리됨	구축된 검색 엔진	시그니처 방법[11]

매칭 전략에 따른 분류

또 다른 분류는 알고리즘을 매칭 전략에 따라 분류한다.^[12]

• 접두사 먼저 매칭 (커누스-모리스-프랫, 시프트-앤드, 아호-코라식)
• 접미사 먼저 매칭 (보이어-무어 및 변형, 콤멘츠-월터)
• 최적의 인자 먼저 매칭 (BNDM, BOM, Set-BOM)
• 기타 전략 (순진한, 라빈-카프, 벡터화)

실시간 문자열 매칭

실시간 문자열 매칭에서는, 매처가 텍스트의 각 문자를 읽은 후 일치 여부를 나타내는 응답을 출력해야 한다. 응답은 상수 시간 내에 주어져야 한다. 전처리 요구 사항은 다양하다: 패턴을 읽은 후(텍스트를 읽기 전) O(m) 전처리가 허용될 수도 있고, 패턴의 어떤 문자(마지막 문자 포함)를 읽은 후에도 매처가 최대 상수 시간 동안만 멈춰야 한다는 더 엄격한 요구 사항이 부과될 수도 있다. 더 관대한 버전의 경우, 전처리 시간과 메모리 요구 사항이 알파벳 크기에 의존하는 것을 신경 쓰지 않는다면, 오토마타 매칭을 통해 실시간 솔루션이 제공된다. 즈비 갈릴은 특정 알고리즘을 실시간 알고리즘으로 전환하는 방법을 개발했으며, 이를 적용하여 엄격한 요구 사항 하에 실시간으로 실행되는 KMP 매처의 변형을 만들었다.^[13]

와일드카드 문자열 검색

이 문자열 검색 문제의 변형에서는 특별한 기호 ø (읽기: 와일드카드)가 있는데, 이는 다른 어떤 기호(다른 ø 포함)와도 일치할 수 있다. 와일드카드 기호는 패턴이나 텍스트에 나타날 수 있다. 2002년에 이 문제에 대해 ${\displaystyle O(n\log m)}$ 시간에 실행되는 알고리즘이 리처드 콜과 라메시 하리하란에 의해 제시되었는데, 이는 1973년 피셔와 패터슨의 ${\displaystyle O(n\log m\log k)}$ 복잡도를 가지는 솔루션을 개선한 것으로, 여기서 k는 알파벳의 크기이다.^[14] 더 간단하다고 주장되는 또 다른 알고리즘은 피터 클리포드와 라파엘 클리포드에 의해 제안되었다.^[15]

같이 보기

• 서열 정렬
• 그래프 매칭
• 패턴 매칭
• 압축 패턴 매칭
• 와일드카드 매칭
• 근사 문자열 매칭
• 전문 검색