키워드 수만 개를 텍스트에서 한 번에 찾기

키워드 수만 개를 거르는 필터가 느려서, AI에게 방법을 물어 먼저 적용부터 했습니다. 왜 빠른지는 나중에 공부했습니다. 그 단계는 확실히 빨라졌지만 전체로 보면 개선이 미미했던 이야기까지 남깁니다

개요

텍스트에서 특정 단어들을 찾아 마스킹하는 필터 기능이 있었습니다. 유지보수하는 내내 느리다는 게 계속 걸리던 기능이라, 이번에 시간을 좀 줄여보려고 방법을 찾다가 먼저 기존 코드를 열어봤습니다. 그랬더니 이렇게 짜여 있었습니다. 찾을 단어들을 리스트에 담고, 하나씩 돌면서 텍스트에 있는지 확인하는 방식이었습니다

for (String word : dictionary) {
    if (text.contains(word)) {
        result = result.replace(word, mask(word));
    }
}

단어가 몇십 개일 때는 문제가 없던 구조였습니다. 그런데 찾을 단어가 수만 개로 늘면서 눈에 띄게 느려져 있었습니다. 처음에는 contains가 느린 함수인가 싶었는데, 다시 보니 문제는 함수가 아니라 구조에 있었습니다

왜 느렸는지 계산해봤습니다

contains는 텍스트를 한 번 훑어야 하니까 텍스트 길이 N에 비례하는 비용이 듭니다. 그런데 저는 그걸 단어 수 D만큼 반복하고 있었습니다. 단어가 5만 개면 텍스트를 5만 번 다시 읽는 셈이었습니다

정리하면 이런 구조였습니다

텍스트를 한 번 읽는 비용: 텍스트 길이만큼
그걸 단어 수만큼 반복: 단어가 늘면 그대로 비례해서 느려짐

즉 텍스트를 단어 개수만큼 반복해서 읽는 게 문제였습니다. 그래서 텍스트를 한 번만 읽으면서 모든 단어를 찾을 수는 없을까 하는 생각을 하게 됐습니다

공부보다 적용이 먼저였습니다

솔직히 저는 이걸 알고리즘부터 공부하고 적용한 게 아니었습니다. 알고리즘 이름도 몰랐고, 먼저 한 건 AI에게 "텍스트를 한 번만 읽으면서 여러 단어를 동시에 찾는 방법이 없냐"고 물어본 것이었습니다. 거기서 Aho-Corasick이라는 답을 받았고, 돌아가는 코드까지 받아서 일단 적용부터 해봤습니다. 눈에 띄게 빨라지는 걸 확인하고 나서야, 이게 왜 빠른지가 궁금해졌습니다

그래서 이번엔 순서를 거꾸로 밟았습니다. 적용해서 효과를 본 다음, 트라이와 실패 링크 개념을 he, she, his, hers 같은 작은 예시로 하나씩 따라가며 뒤늦게 이해했습니다. 아래는 그렇게 나중에 공부해서 제 말로 다시 정리한 내용입니다

먼저 트라이로 단어들을 겹쳐 담습니다

Aho-Corasick을 이해하려면 두 가지를 먼저 알아야 했습니다. 첫 번째는 트라이(trie)였습니다 찾을 단어가 he, she, his, hers라고 해봤습니다. 이걸 트라이에 담으면 이렇게 됩니다

(루트)
 ├─ h ─ e●          ("he")
 │       └─ r ─ s●  ("hers")
 │   └─ i ─ s●      ("his")
 └─ s ─ h ─ e●      ("she")

he와 hers가 앞부분(he)을 공유하는 게 보입니다. 이렇게 담아두면 텍스트의 한 글자에서 시작해 트라이를 따라 내려가는 것만으로, 그 자리에서 시작하는 단어들을 한 번에 확인할 수 있었습니다. 단어마다 따로 검사하던 걸 하나로 합친 셈입니다

그런데 트라이만으로는 부족했습니다. 따라 내려가다가 중간에 막히면, 텍스트를 한 글자 뒤로 돌려서 루트부터 다시 시작해야 했습니다. 뒤로 돌아가는 비용이 남아 있었습니다

실패했을 때 뒤로 안 가는 장치 - 실패 링크

두 번째로 알아야 했던 게 실패 링크였습니다. 이건 KMP에서 쓰는 아이디어랑 같았습니다. 매칭이 끊겼을 때 처음부터 다시 하지 말고, 지금까지 본 것 중에 재활용할 수 있는 부분에서 이어가자는 것입니다

트라이의 각 노드에 실패 링크를 답니다. 이 링크는 "지금 노드까지 온 글자들의 접미사 중에, 트라이에 존재하는 가장 긴 것"으로 가는 지름길입니다. 매칭이 끊기면 루트로 돌아가는 대신 이 링크를 타고 점프해서 이어갔습니다. 그래서 텍스트를 읽는 포인터가 한 번도 뒤로 가지 않았습니다

Aho-Corasick은 결국 이 둘을 합친 것이었습니다. 트라이를 만들고, 그 모든 노드에 실패 링크를 달아둔 것입니다

손으로 한 번 따라가 봤습니다

단어가 he, she, his, hers이고 텍스트가 ushers일 때를 직접 따라가 봤습니다

u - 루트에서 갈 곳이 없어서 루트에 머묾
s - s 노드로
h - sh 노드로
e - she 노드 도착, 여기서 "she"를 찾음 이 노드의 실패 링크가 he 노드를 가리켜서 "he"도 같이 찾음
r - she에서 r로 가는 길이 없어서 실패 링크로 he로 점프, he에는 r 길이 있어서 her 노드로
s - hers 노드 도착, "hers"를 찾음

두 가지가 눈에 들어왔습니다. 텍스트 6글자를 정확히 6번만 읽었고, 4번처럼 한 노드에 도착하면 실패 링크로 연결된 단어들까지 같이 찾아졌습니다

구현

실패 링크는 BFS로 만들었습니다. 루트에서 가까운 노드부터 계산하면 부모의 실패 링크를 재활용할 수 있기 때문입니다

class AhoCorasick {
    static class Node {
        Map<Character, Node> next = new HashMap<>();
        Node fail;
        List<String> outputs = new ArrayList<>();   // 이 노드에서 끝나는 단어들
    }

    private final Node root = new Node();

    void insert(String word) {
        Node cur = root;
        for (char c : word.toCharArray())
            cur = cur.next.computeIfAbsent(c, k -> new Node());
        cur.outputs.add(word);
    }

    void buildFailureLinks() {
        Deque<Node> queue = new ArrayDeque<>();
        for (Node child : root.next.values()) {
            child.fail = root;                       // 깊이 1은 전부 루트로
            queue.add(child);
        }
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            for (var e : cur.next.entrySet()) {
                char c = e.getKey();
                Node child = e.getValue();
                Node f = cur.fail;                   // 부모의 실패 링크에서 출발
                while (f != null && !f.next.containsKey(c)) f = f.fail;
                child.fail = (f == null) ? root : f.next.get(c);
                child.outputs.addAll(child.fail.outputs);  // 출력 병합
                queue.add(child);
            }
        }
    }

    List<String> findAll(String text) {
        List<String> found = new ArrayList<>();
        Node cur = root;
        for (char c : text.toCharArray()) {
            while (cur != root && !cur.next.containsKey(c)) cur = cur.fail;
            cur = cur.next.getOrDefault(c, root);
            found.addAll(cur.outputs);
        }
        return found;
    }
}

무엇이 바뀌었나

두 방식의 비용을 정리하면 이렇게 됐습니다

기준	for + contains	Aho-Corasick
사전 준비	없음	트라이 + 실패 링크 빌드(기동 시 한 번)
검색 비용	단어 수에 비례해서 커짐	텍스트 길이에만 비례
단어가 늘어날 때	그대로 느려짐	검색 속도는 그대로

처음 방식은 단어가 늘면 검색도 같이 느려졌는데, Aho-Corasick은 단어 수가 검색 비용에서 빠졌습니다. 단어가 5만 개든 50만 개든 텍스트를 한 번 읽는 비용은 같았습니다. 대신 트라이를 미리 만들어두는 준비 비용이 생겼는데, 이건 기동할 때 한 번만 내면 되는 비용이라 괜찮다고 생각했습니다

제가 겪은 사례에서는 키워드가 수만 개 규모였는데, for + contains를 Aho-Corasick으로 바꾸니 그 필터 단계의 처리 시간 자체는 큰 폭으로 줄었습니다. 단어를 아무리 늘려도 텍스트를 한 번만 읽으니, 이 단계만 놓고 보면 확실한 개선이었습니다

다만 솔직히 전체 문제는 많이 해결되지 않았습니다. 나중에 전체 처리 시간을 단계별로 쪼개보니 이 필터가 차지하는 몫이 생각보다 작았고, 진짜 시간은 데이터를 가져오는 다른 단계에 몰려 있었습니다. 그래서 이 알고리즘은 "쓰이던 자리의 시간은 확실히 줄였지만 전체로 보면 미미한" 개선에 가까웠습니다. 어디가 진짜 병목인지 먼저 재봤다면 순서를 다르게 잡았을 것 같습니다

쓰면서 걸렸던 점

빌드가 공짜는 아니었습니다 트라이랑 실패 링크를 만드는 데도 비용이 들어서, 단어 사전이 자주 바뀌는 환경이라면 이 재빌드 비용을 미리 생각해둬야 할 것 같았습니다. 저는 시작할 때 한 번 만들고, 사전이 바뀔 때만 다시 만드는 방식이 무난하다고 느꼈습니다

메모리를 꽤 씁니다 노드 수가 단어들의 전체 글자 수에 비례해서 늘어납니다. 한글처럼 글자 종류가 많은 경우에는 간선을 배열보다 Map으로 두는 게 메모리 면에서 나아서 위 코드도 그렇게 했습니다

찾는 것까지가 이 알고리즘의 일이었습니다 찾은 단어를 어떻게 바꿀지, he랑 hers가 같이 걸렸을 때 어느 걸 우선할지 같은 건 알고리즘이 정해주지 않았습니다. 이건 따로 정해야 하는 정책이었고, 실제로는 이 부분에서 버그가 더 자주 났습니다. 그래서 바꾸기 전과 후의 결과가 같은지 확인하는 테스트를 먼저 깔아두고 교체하는 게 안전하다고 생각했습니다

핵심 포인트

처음 느렸던 이유는 contains가 느려서가 아니라, 텍스트를 단어 수만큼 반복해서 읽는 구조 때문이었습니다
트라이는 단어들을 앞부분을 겹쳐서 담아, 한 번의 하강으로 여러 단어를 확인하게 해줍니다
실패 링크는 매칭이 끊겨도 텍스트를 뒤로 돌리지 않게 해줍니다
둘을 합친 Aho-Corasick은 텍스트를 한 번만 읽어서, 단어가 아무리 많아도 검색 속도가 유지됐습니다

적용부터 하고 뒤늦게 공부해보니 이렇게 정리됐습니다

단어가 몇십 개면 for + contains로 충분하지만, 수천 개를 넘어가면 텍스트를 한 번만 읽는 구조로 바꿀 때가 됐다고 생각했습니다

개요