문자열 알고리즘 안내서 · 6/6

실무 활용

문자열 알고리즘은 대부분 라이브러리와 도구 안에 숨어 있습니다. 이 장에서는 실제 시스템에서 어떤 알고리즘이 쓰이는지, 직접 구현할 때 자주 빠지는 함정이 무엇인지 정리합니다.

실제 시스템 속 문자열 알고리즘

표준 라이브러리 검색: 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: 유니코드

문자열 길이와 위치를 셀 단위가 언어마다 다릅니다.

환경	인덱스 단위	`"😀"`의 길이
Python `str`	코드 포인트	1
Java `String`, JavaScript	UTF-16 코드 단위	2
C++ `std::string`, Rust `str::len`	UTF-8 바이트	4

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로 이스케이프합니다.

무엇을 고를까

상황	추천
한 번의 단순 검색	언어의 표준 함수(`in`, `find`, `indexOf`)
경계, 주기, 접두사 정보가 필요	접두사 함수(KMP) 또는 Z 배열
길이가 같은 패턴 여러 개, 부분 문자열 비교	굴러가는 해시
길이가 다른 패턴 수천 개	Aho-Corasick 라이브러리
사전에서 접두사 검색, 자동 완성	트라이 또는 정렬 리스트 + 이진 탐색
같은 큰 텍스트에 질의가 많음	접미사 배열, FM 인덱스, 검색 엔진

정리

표준 라이브러리와 도구는 Two-Way, Boyer-Moore, Aho-Corasick, 굴러가는 해시, 트라이를 상황에 맞게 씁니다.
유니코드에서는 인덱스 단위와 정규화, 대소문자 접기를 먼저 맞춥니다.
해시 충돌은 무작위 기수와 확인 단계로 막고, 큰 사전은 압축 구조를 검토합니다.

더 읽을거리

이 장에 대해 질문이 있나요?