문자열 알고리즘은 대부분 라이브러리와 도구 안에 숨어 있습니다. 이 장에서는 실제 시스템에서 어떤 알고리즘이 쓰이는지, 직접 구현할 때 자주 빠지는 함정이 무엇인지 정리합니다.
실제 시스템 속 문자열 알고리즘
- 표준 라이브러리 검색: CPython의
str.find와 in은 Boyer-Moore-Horspool을 단순화한 방식을 바탕으로 하고, Python 3.10부터는 긴 패턴에 Crochemore-Perrin의 Two-Way 알고리즘을 씁니다. glibc의 memmem, strstr도 긴 패턴에 Two-Way를 씁니다. Two-Way는 추가 메모리를 상수만 쓰면서 최악에도 선형 시간을 보장합니다. - grep 계열 도구: GNU grep은 Boyer-Moore 계열 검색과 여러 키워드를 위한 알고리즘을 조합합니다. ripgrep이 쓰는 Rust 크레이트
aho-corasick과 memchr는 다중 패턴 검색과 SIMD 가속을 제공합니다. - 침입 탐지와 백신: 수천 개의 시그니처를 패킷이나 파일에서 한 번에 찾아야 하므로 Aho-Corasick과 그 변형이 널리 쓰입니다.
- 파일 동기화와 중복 제거: rsync는 굴러가는 체크섬으로 바뀐 블록만 찾아 보냅니다. 백업 도구들은 Rabin 지문 같은 굴러가는 해시로 내용 기준 청크 경계를 정합니다.
- 표절 검사: 문서를 k-그램 해시로 바꾸고 일부만 지문으로 고르는 winnowing 기법이 쓰입니다.
- 라우팅과 사전: IP 라우팅의 최장 접두사 일치에는 트라이 변형이 쓰이며, Linux 커널의 IPv4 라우팅 테이블은 LC-trie를 씁니다. 검색창 자동 완성, 맞춤법 사전, 키-값 저장소의 접두사 질의에도 트라이나 radix tree가 등장합니다.
- 생물정보학: 짧은 서열을 참조 유전체에 정렬하는 도구들은 접미사 배열과 BWT 기반 FM 인덱스로 거대한 텍스트를 색인합니다.
함정 1: 유니코드
문자열 길이와 위치를 셀 단위가 언어마다 다릅니다.
Java나 JavaScript에서 계산한 위치를 Python 서비스에 넘기면 이모지가 섞인 텍스트에서 위치가 어긋납니다. API로 위치를 주고받을 때는 단위를 명시합니다.
const s = "a😀b";
console.log(s.length); // 4 (UTF-16 코드 단위)
console.log([...s].length); // 3 (코드 포인트)
const seg = new Intl.Segmenter("ko", { granularity: "grapheme" });
console.log([...seg.segment("👍🏽")].length); // 1 (사용자가 보는 글자)
또한 같은 글자가 여러 방식으로 표현될 수 있습니다. 한글 한은 완성형 한 글자(U+D55C)일 수도 있고, 자모 세 개(ㅎ, ㅏ, ㄴ)를 이은 것일 수도 있습니다. macOS 파일 이름처럼 NFD로 저장된 텍스트를 NFC 검색어로 찾으면 실패합니다. 대소문자 무시 비교도 lower()보다 casefold()가 정확합니다.
import unicodedata
nfd = unicodedata.normalize("NFD", "한글")
print(len("한글"), len(nfd)) # 2 6
print("한" in nfd) # False
print("한" in unicodedata.normalize("NFC", nfd)) # True
print("Straße".lower() == "STRASSE".lower()) # False
print("Straße".casefold() == "STRASSE".casefold()) # True
검색 파이프라인에서는 저장할 때와 질의할 때 같은 정규화와 대소문자 접기를 적용하는 것이 기본입니다.
함정 2: 해시 충돌과 공격 입력
Rabin-Karp에서 해시가 같을 때 확인을 생략하면 틀린 답을 낼 수 있습니다. 기수와 모듈러가 고정되어 있으면 공격자가 충돌하는 입력을 만들 수 있으므로, 실행할 때마다 기수를 무작위로 고르고 모듈러는 2^61 - 1 같은 큰 소수를 쓰거나 두 개의 해시를 함께 씁니다.
import random
MOD = (1 << 61) - 1
BASE = random.randrange(256, MOD - 1) # 실행마다 다른 기수
def poly_hash(s: str) -> int:
h = 0
for ch in s:
h = (h * BASE + ord(ch)) % MOD
return h
print(poly_hash("abc") == poly_hash("abc"), poly_hash("abc") == poly_hash("acb"))
# True False (충돌 확률은 아주 작지만 0은 아님)
함정 3: 메모리와 재귀
- 트라이는 노드 객체가 많아 메모리를 많이 씁니다. 단어가 수백만 개라면 radix tree, 이중 배열 트라이, 정렬 리스트와 이진 탐색 같은 압축 구조를 검토합니다.
- 재귀 DFS로 트라이를 훑으면 매우 긴 키에서 Python의 재귀 제한에 걸릴 수 있습니다. 명시적 스택을 씁니다.
- 정규 표현식은 편리하지만 역추적 엔진에서
(a+)+ 같은 패턴은 지수 시간이 걸릴 수 있습니다(ReDoS). 사용자 입력을 패턴으로 쓸 때는 re.escape로 이스케이프합니다.
무엇을 고를까
정리
- 표준 라이브러리와 도구는 Two-Way, Boyer-Moore, Aho-Corasick, 굴러가는 해시, 트라이를 상황에 맞게 씁니다.
- 유니코드에서는 인덱스 단위와 정규화, 대소문자 접기를 먼저 맞춥니다.
- 해시 충돌은 무작위 기수와 확인 단계로 막고, 큰 사전은 압축 구조를 검토합니다.
더 읽을거리
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.