📚 지식 노트

단순 탐색: 모든 자리에 대 보기

길이 n인 본문(text)에서 길이 m인 패턴(pattern)이 나오는 자리를 모두 찾는 것이 문자열 탐색(string searching)이다. 편집기의 찾기, grep, 바이러스 시그니처 검사, DNA 서열 검색이 모두 이 문제다. 가장 먼저 떠오르는 방법은 패턴을 본문의 0번 자리부터 n − m번 자리까지 차례로 대 보며, 자리마다 왼쪽부터 글자를 비교하는 것이다.

자리 n − m + 1개마다 최대 m번을 비교하니 최악은 O(nm)이다. 본문이 AAAA…A이고 패턴이 AAAB 같은 경우가 그렇다. 다만 보통의 글에서는 대부분 첫 글자나 둘째 글자에서 틀리므로 평균은 O(n)에 가깝고, 구현이 단순해 짧은 패턴에서는 오히려 빠르다. 실제 라이브러리는 단순 탐색에 첫 글자를 메모리에서 빠르게 찾는 기법(memchr, SIMD)을 섞거나, 패턴의 뒤부터 비교해 크게 건너뛰는 보이어-무어(Boyer-Moore) 계열을 쓴다.

문자열을 다루는 기본 비용에도 단골 함정이 둘 있다. 첫째, 파이썬 str은 바꿀 수 없어서(immutable) s += c가 매번 새 문자열을 만든다. 반복문 안에서 이렇게 이어 붙이면 전체 길이에 대해 제곱 시간이 들 수 있다고 파이썬 문서가 경고하고, 조각을 리스트에 모았다가 마지막에 join하라고 권한다. 둘째, "길이"가 글자 수가 아닐 수 있다. JavaScript의 length는 UTF-16 코드 단위 수라 이모지 "😄" 하나가 2로 나오고, 사람이 보는 글자 단위로 세려면 Intl.Segmenter를 써야 한다(MDN의 String length). 문자열 길이를 n으로 적을 때는 무엇을 센 n인지부터 정한다.

문제 풀기 →Python 코드 →

KMP의 실패 함수: 틀렸을 때 얼마나 되돌릴까

단순 탐색의 낭비는 이미 맞춘 글자를 다시 비교하는 데 있다. 0번 자리에서 ABABA까지 맞췄다면, 본문의 그 다섯 글자는 이미 안다. 그 안에서 패턴의 앞부분과 겹칠 수 있는 곳은 패턴만 보고도 미리 계산할 수 있다. KMP(Knuth–Morris–Pratt) 알고리즘은 이 계산을 실패 함수(failure function, prefix function) 표에 담아 둔다.

π[i]는 패턴의 앞 i + 1글자에서 접두사이면서 동시에 접미사인 가장 긴 부분(자기 자신 전체는 빼고)의 길이다. 예를 들어 ABABA는 앞의 ABA와 뒤의 ABA가 같으므로 π[4] = 3이다. j글자를 맞춘 뒤 틀리면 패턴을 j − π[j − 1]칸 밀고, 겹친 π[j − 1]글자는 이미 맞은 것으로 치고 이어서 비교한다.

failure[0] = 0, k = 0
for i = 1 .. m-1:
  while k > 0 and p[i] ≠ p[k]: k = failure[k-1]
  if p[i] == p[k]: k += 1
  failure[i] = k

표를 만드는 일 자체가 패턴으로 패턴을 찾는 KMP다. k는 한 번에 1씩만 늘고 while에서 줄기만 하므로, 줄어드는 총량이 늘어난 총량을 넘을 수 없다. 그래서 이중 반복처럼 보여도 O(m)이다. 자세한 증명과 응용은 cp-algorithms의 Prefix function에 정리돼 있다.

문제 풀기 →Python 코드 →

KMP로 찾기

탐색은 본문 위치 i와 맞춘 글자 수 j를 들고 간다. 본문 글자와 패턴 글자가 같으면 둘 다 한 칸 나아간다. 다르면 i는 그대로 두고 j만 π[j − 1]로 되돌려 다시 비교한다. j가 m에 닿으면 하나를 찾은 것이고, 겹치는 다음 일치도 놓치지 않도록 j를 π[m − 1]로 되돌려 이어 간다.

i가 한 번도 뒤로 가지 않으므로 비교는 많아야 2n번이고, 표 만들기까지 합쳐 O(n + m)이다. 본문을 앞에서부터 한 번만 읽으면 되니 되감을 수 없는 스트림(네트워크 패킷, 파일을 읽어 들이는 중)에서도 쓸 수 있다. 실패 함수는 탐색 말고도 쓸모가 많다. 문자열의 가장 짧은 반복 단위는 m − π[m − 1]로 바로 나온다.

여러 패턴을 한꺼번에 찾을 때는 KMP를 트라이(trie) 위로 넓힌 아호-코라식(Aho–Corasick)을 쓴다. 침입 탐지 시스템이 수천 개의 공격 시그니처를 패킷에서 동시에 찾는 방식이다. 트라이는 트리 노트에 있다.

문제 풀기 →Python 코드 →

라빈-카프: 해시로 먼저 거르기

라빈-카프(Rabin–Karp)는 비교를 해시로 대신한다. 패턴의 해시를 한 번 구해 두고, 본문의 길이 m짜리 창(window)마다 해시를 구해 같을 때만 글자를 비교한다. 핵심은 창을 한 칸 밀 때 해시를 처음부터 다시 계산하지 않는 것이다. 문자열을 B진법 수로 보면, 나가는 글자의 몫을 빼고 B를 곱한 뒤 들어오는 글자를 더하면 새 창의 해시가 O(1)에 나온다. 이것을 굴리는 해시(rolling hash)라 한다.

해시가 같다고 글자가 같은 것은 아니다. 그림의 897처럼 해시만 같은 가짜 일치(spurious hit)가 있으므로 해시가 같을 때는 반드시 글자를 확인한다. 큰 소수를 법으로 쓰면 가짜 일치가 드물어 평균 O(n + m)이지만, 최악(모든 창이 가짜 일치)은 O(nm)이다. 법을 무작위로 고르면 공격자가 최악을 만들어 내기 어렵다.

라빈-카프가 빛나는 곳은 여러 패턴이나 긴 반복을 찾을 때다. 길이가 같은 패턴 k개의 해시를 해시 집합에 넣어 두면 창 하나당 집합 조회 한 번으로 k개를 함께 검사한다. 표절 검사가 글을 일정 길이 조각으로 잘라 해시를 비교하는 것(fingerprinting), rsync가 파일에서 바뀐 블록을 찾는 것도 굴리는 해시다. 해시 함수 자체는 해시 노트에서 다룬다. 굴리는 해시의 세부와 충돌 확률은 cp-algorithms의 Rabin-Karp가 자세하다.

문제 풀기 →Python 코드 →

편집 거리: 두 글이 얼마나 다른가

맞춤법 검사기의 "혹시 이 단어를 찾으셨나요?", diff 도구, DNA 서열 비교는 두 문자열이 얼마나 다른지 재야 한다. 편집 거리(edit distance, 레벤슈타인 거리 Levenshtein distance)는 한 글자 넣기, 지우기, 바꾸기를 각각 비용 1로 칠 때 한 문자열을 다른 문자열로 바꾸는 최소 비용이다.

경우의 수를 모두 해 보면 지수 시간이 들지만, 작은 문제의 답으로 큰 문제의 답을 만드는 동적 계획법(dynamic programming)으로 풀린다. D[i][j]를 앞 문자열의 앞 i글자를 뒤 문자열의 앞 j글자로 바꾸는 비용이라 하면, 마지막 글자를 어떻게 처리했느냐에 따라 세 경우뿐이다.

D[i][0] = i,  D[0][j] = j
D[i][j] = min( D[i-1][j] + 1,                 // a[i] 지우기
               D[i][j-1] + 1,                 // b[j] 넣기
               D[i-1][j-1] + (a[i] == b[j] ? 0 : 1) )   // 그대로 또는 바꾸기

표는 (n + 1) × (m + 1)칸이고 칸마다 O(1)이니 시간과 공간이 O(nm)이다. 거리 값만 필요하면 바로 윗줄만 남겨 공간을 O(min(n, m))으로 줄일 수 있다. 실제 편집 순서까지 필요하면 표를 남겨 두고 오른쪽 아래에서 어느 이웃에서 왔는지 거꾸로 되짚는다. 그림의 KITTEN → SITTING은 K→S 바꾸기, E→I 바꾸기, G 넣기로 3이다.

변형이 많다. 바꾸기를 빼고 넣기·지우기만 허용하면 최장 공통 부분 수열(LCS)과 같은 문제가 되고, git diff 같은 줄 단위 비교 도구가 이 계열이다. 이웃한 두 글자 맞바꾸기까지 1로 치면 다메라우-레벤슈타인(Damerau–Levenshtein) 거리다. 같은 표 채우기 기법은 설계 기법 노트의 동적 계획법 절에서 더 다룬다. 정의와 변형은 위키백과의 Levenshtein distance에 정리돼 있다.

문제 풀기 →Python 코드 →

접미사 배열: 한 번 정리해 두고 여러 번 찾기

KMP와 라빈-카프는 패턴이 올 때마다 본문 전체를 훑는다. 본문은 거의 바뀌지 않고 질의가 많이 온다면(유전체, 책 전체, 로그 보관소), 본문을 미리 정리해 두는 편이 낫다. 접미사 배열(suffix array)은 본문의 모든 접미사를 사전순으로 정렬한 뒤 그 시작 위치만 배열로 적은 것이다.

패턴이 나오는 모든 자리는 "패턴으로 시작하는 접미사"의 시작 위치이고, 그런 접미사는 정렬된 순서에서 한 구간에 모인다. 그래서 이진 탐색으로 구간 양 끝을 찾으면 된다. 비교 한 번에 최대 m글자를 보니 찾기는 O(m log n)이다. 메모리는 정수 n개뿐이라, 같은 일을 하는 접미사 트리(suffix tree)보다 몇 배 작다.

만들기는 접미사를 그냥 정렬하면 비교 하나가 O(n)이라 O(n² log n)이지만, 앞 1, 2, 4, 8…글자 순위를 두 배씩 늘려 가며 정렬하는 방법으로 O(n log n)에, SA-IS 같은 알고리즘으로 O(n)에 만든다. 이웃한 접미사의 공통 접두사 길이를 담은 LCP 배열을 함께 두면 서로 다른 부분 문자열의 개수, 가장 긴 반복 부분 문자열 같은 질문에도 답한다. bzip2 압축의 바탕인 버로스-휠러 변환(BWT)과, 유전체 정렬 도구가 쓰는 FM-인덱스도 접미사 배열에서 나온다(압축 이야기는 데이터 노트). 만드는 과정은 cp-algorithms의 Suffix Array와 VisuAlgo의 접미사 배열 시각화로 따라가 볼 수 있다.

문제 풀기 →Python 코드 →