트라이 - 자동 완성과 접두사 검색

이 장에서 배우는 것

자동 완성 창에 ca를 입력하면 car, card, care, cat이 나타난다고 하자. 모든 단어를 처음부터 확인해도 결과는 만들 수 있다. 그러나 저장한 단어가 늘어날수록 같은 앞부분을 반복해서 비교한다. 이번에는 단어를 통째로 늘어놓지 않고, 앞부분이 같은 단어끼리 길을 공유하도록 저장한다.

이 구조를 트라이(trie)라고 한다. 문자열의 앞에서부터 몇 글자를 잘라 얻은 부분을 접두사(prefix)라고 한다. ca는 car의 접두사이며, 단어 전체와 빈 문자열도 접두사에 포함한다. 트라이는 접두사가 가리키는 위치까지 먼저 이동한 뒤 그 아래에서 단어를 찾는다.

앞 장에서는 우선순위에 따라 먼저 꺼낼 대상을 정했다. 여기서는 글자가 이어지는 순서를 이용해 찾을 범위를 좁힌다. 자료구조를 사용하는 설명에서 한 걸음 더 들어가, 배열로 자식 위치를 관리하고 실제로 몇 번 이동하는지 확인한다.

• 글자 하나에 대응하는 노드와 단어 끝 표시를 직접 설계한다.
• 단어 삽입, 정확한 단어 검색, 접두사 목록 생성을 구현한다.
• 글자를 따라가는 횟수와 자식 배열을 확인하는 횟수를 구분해 센다.
• 고정 크기 배열이 소비하는 공간을 계산하고 내장 목록 순회와 비교한다.

문제 상황

작은 개발 도구에 명령어 자동 완성을 붙이는 상황을 생각해 보자. 사용자가 명령어의 앞부분을 입력하면 등록된 단어를 사전순으로 보여 주어야 한다. 입력한 문자열 자체가 등록된 단어인지도 확인해야 한다. 예를 들어 car는 단어이지만 ca는 아직 단어가 아니다. 그렇더라도 ca로 시작하는 후보는 존재한다.

가장 단순한 구현은 모든 단어를 차례로 보며 앞부분이 일치하는지 확인한다. 이 방법은 후보가 없는 경우에도 전체 목록을 살펴본다. 반면 트라이는 첫 글자에 해당하는 길이 없으면 바로 멈출 수 있다. 접두사가 길어져도 전체 목록으로 돌아갈 필요가 없다.

이번 프로그램은 동작을 명확히 드러내기 위해 영문 소문자 a부터 z까지, 길이 20 이하의 단어만 받는다. 빈 단어도 저장할 수 있다. 공백 제거, 대문자 변환, 추천 순위 계산은 하지 않는다. 입력 규칙과 저장 구조를 함께 단순하게 정하면 어떤 비용을 세고 있는지 분명해진다.

목표는 입력을 기다리는 화면이 아니라, 자동 완성기의 핵심을 한 파일로 실행하는 것이다. 프로그램은 정해 둔 단어를 넣고 검색과 자동 완성을 수행한 뒤 종료한다. 난수를 쓰지 않으므로 실행할 때마다 결과와 연산 횟수가 같다.

글자 하나를 자식 배열 한 칸에 대응시킨다

다른 노드로 이어지는 정보를 담는 객체를 노드(node)라고 한다. 시작점인 루트(root)는 특정 글자를 뜻하지 않는다. 루트에서 c로 이동하고, 다시 a와 r로 이동하면 car를 읽은 셈이다. 노드 사이의 연결을 전공 수업에서는 간선(edge)이라고 부른다. 이 구현의 간선은 자식 객체를 가리키는 배열 원소다.

각 노드에는 길이 26의 children 배열을 둔다. a는 0번, b는 1번, z는 25번 칸에 대응한다. ord는 문자에 대응하는 정수를 얻는 내장 함수다. 소문자인지 확인한 뒤 ord(ch) - ord("a")를 계산하면 사용할 칸 번호가 나온다. 배열 원소가 None이면 그 글자로 이어지는 길이 없다는 뜻이다.

여기서 Python 리스트는 길이가 정해진 배열을 만드는 용도로만 사용한다. [None] * 26으로 만든 뒤 원소를 읽거나 바꾸며, append나 길이 변경은 하지 않는다. 연결을 찾는 데 dict를 쓰지도 않는다. 마지막 비교 코드에서만 Python의 내장 목록 기능을 사용한다.

길이 존재한다는 사실과 단어가 끝났다는 사실은 다르다. card만 넣었더라도 c, ca, car까지 가는 길은 모두 생긴다. 따라서 도착한 노드에 별도의 단어 끝 표시가 필요하다. 이 코드에서는 word가 None이면 단어 끝이 아니고, 문자열이면 그 문자열이 끝난 자리다.

단어 끝에 전체 문자열을 보관하는 이유는 자동 완성 결과를 쉽게 돌려주기 위해서다. 글자를 다시 합치지 않고 문자열 객체를 가리키는 참조를 결과 배열에 넣는다. 참조는 객체를 다시 찾을 수 있게 하는 연결 정보다. 전공 수업에서 포인터(pointer)로 설명하는 역할과 연결되지만, Python 코드에서 메모리 주소를 직접 계산하지는 않는다.

노드의 두 필드가 맡는 역할

필드	저장 내용	판단할 수 있는 것
children	자식 참조 26개	다음 글자로 이동할 수 있는가
word	None 또는 완성된 문자열	현재 위치가 등록된 단어의 끝인가
루트의 word	None 또는 빈 문자열	빈 단어가 등록되어 있는가

삽입은 루트에서 시작해 글자를 하나씩 처리한다. 사용할 칸이 비어 있을 때만 새 노드를 연결한다. 이미 있는 길은 재사용한다. 마지막 노드가 아직 단어 끝이 아닐 때만 단어 수를 늘리므로 같은 단어를 여러 번 넣어도 후보가 중복되지 않는다.

검색도 같은 길을 따라가지만 노드를 만들지 않는다. 중간에 길이 없으면 실패하고, 끝까지 이동했더라도 word를 확인해야 한다. 이 차이를 빼면 ca를 검색했을 때 car의 앞부분이라는 이유로 성공해 버린다.

접두사 아래를 방문하고 비용을 센다

접두사 목록 생성은 두 단계다. 먼저 입력한 접두사를 따라 이동한다. 도착한 노드를 기준으로 아래에 연결된 모든 노드를 방문한다. 어떤 노드와 그 아래에 이어진 부분 전체를 전공 수업에서는 서브트리(subtree)라고 부른다. 접두사 목록은 이 서브트리에 있는 단어 끝을 모은 결과다.

아래쪽 방문은 현재 위치의 단어를 먼저 기록한 다음, 자식 배열의 0번부터 25번까지 차례로 진행한다. 한 갈래를 끝까지 살펴본 뒤 다른 갈래로 넘어가는 방식이며, 전공 수업에서는 깊이 우선 순회(depth-first traversal)라고 한다. 여기서는 트라이의 후보를 열거하는 데 필요한 형태만 구현한다.

함수 안에서 같은 함수를 다시 호출하는 재귀(recursion)를 사용한다. 각 호출이 자기 노드의 자식들을 처리한다. 자식이 없는 노드는 추가 호출 없이 돌아온다. 최대 단어 길이를 20으로 제한했으므로 이 프로그램의 호출 깊이도 그에 맞게 제한된다.

단어 끝을 먼저 기록하면 car가 card보다 앞선다. 자식을 a부터 z 순서로 방문하면 갈라지는 글자의 순서도 맞는다. 그래서 별도 정렬 없이 사전순 결과가 나온다. 여기서 사전순은 영문 소문자의 문자 순서를 기준으로 하며, 언어별 사전 편집 규칙까지 뜻하지 않는다.

시간 복잡도는 입력이 커질 때 작업량이 어떻게 늘어나는지를 나타낸다. O(L)은 길이 L에 비례하는 상한을 뜻한다. 단, 무엇을 한 번의 작업으로 세는지 먼저 정해야 한다. 이 장에서는 글자 하나로 자식 칸을 조회하는 일을 이동 시도 한 번으로 센다. 길이 없어서 실패한 조회도 포함한다. 후보를 모을 때는 빈 칸을 포함해 확인한 자식 칸 수도 따로 센다.

검증 비용은 이동 횟수와 구분한다. 올바르지 않은 입력 때문에 일부 글자만 저장되는 일을 막으려면 삽입 전에 문자열 전체를 확인해야 한다. 검증과 이동이 각각 길이에 비례하므로 삽입 전체도 O(L)이다. 정확한 검색 역시 검증을 포함하면 O(L)이며, 길이 없는 자리에 일찍 도착해도 앞서 수행한 검증 비용은 남는다.

배열 기반 트라이의 연산 비용

연산	기호	세는 작업	시간
삽입	단어 길이 L	이동 L회, 새 노드당 26칸 초기화	O(26L), 고정 알파벳에서는 O(L)
정확한 검색	단어 길이 L	검증 L글자, 이동 최대 L회	O(L)
접두사 목록	접두사 길이 P, 방문 노드 Vp, 후보 K	이동 최대 P회, 자식 칸 26Vp개 확인	O(P + 26Vp + K)
결과 출력	후보 전체 글자 수 C	문자열을 화면에 기록	O(C)

완성 코드의 결과 배열은 전체 단어 수만큼 미리 확보한다. 따라서 접두사 목록 메서드 자체에는 배열 초기화 O(N)도 더해진다. N은 등록된 단어 수다. 위 표의 목록 비용은 저장 공간이 준비된 뒤의 탐색 비용이며, 이 구현의 메서드 전체는 O(N + P + 26Vp + K)다. 이를 숨기면 후보 하나를 찾는 경우까지 접두사 길이에만 비례한다고 오해하게 된다.

빈 접두사는 루트에서 바로 수집을 시작하므로 모든 단어를 돌려준다. 반대로 첫 글자부터 길이 없으면 결과 배열을 만들지 않고 종료한다. 반환값의 배열이 None인 경우에는 후보 수가 반드시 0이다. 배열이 존재하는 경우에도 유효한 결과는 앞에서부터 후보 수만큼이다.

고정 배열의 메모리 비용을 계산한다

빠르게 다음 글자를 찾는 대가로 각 노드는 자식 참조 칸 26개를 확보한다. 자식이 하나뿐인 노드도 26칸을 차지하고, 단어 끝의 말단 노드도 마찬가지다. 자식이 없는 말단을 전공 수업에서는 리프(leaf)라고 한다. 사용하지 않는 칸이 많을 때 이러한 배치를 희소하다고 표현한다.

완성 코드에서는 총 10개 노드가 생긴다. 자식 배열 칸은 26 × 10 = 260개다. 루트를 제외한 각 노드에는 부모로부터 들어오는 연결이 하나 있으므로 실제 자식 연결은 9개다. 빈 칸은 251개다. 숫자는 바이트 수가 아니라 참조를 넣는 칸 수다. 실제 바이트 사용량에는 객체와 배열을 관리하는 정보도 더해진다.

전체 노드 수를 V, 저장한 서로 다른 단어의 전체 글자 수를 S라고 두면, 자식 배열과 보관한 단어 문자열의 공간은 O(26V + S)로 설명할 수 있다. word는 문자열을 복사하는 대신 기존 문자열을 참조하지만, 트라이가 그 참조를 유지하는 동안 문자열도 메모리에 남는다. 접두사 경로를 공유한다고 해서 이 구현의 원본 문자열까지 없어지는 것은 아니다.

후보 배열에는 별도로 O(N) 공간이 필요하고 재귀 호출에는 최대 단어 길이에 비례하는 공간이 필요하다. 호출이 끝나면 그 호출을 관리하던 공간은 되돌아온다. 반면 반환한 후보 배열은 사용하는 쪽이 붙잡고 있는 동안 남아 있다.

글자 종류를 넓히면 노드마다 확보할 배열도 커진다. 실제 서비스의 여러 문자 체계를 이 구조에 그대로 넣는 것은 별도 설계가 필요하다. 이 장에서는 알파벳을 26개로 고정해 비용을 드러낸다. 자식이 있는 글자만 따로 저장하는 대안은 빈 칸을 줄일 수 있지만, 다음 글자를 찾는 방법과 비용도 함께 바뀐다.

완성 코드

아래 내용을 main.py에 저장한다. 핵심 구현은 고정 길이 리스트만 배열로 사용한다. 튜플은 테스트 입력과 여러 반환값을 묶는 데 사용하며, 마지막 비교 구역에서만 길이가 늘어나는 내장 리스트와 startswith를 사용한다.

ALPHABET = 26
MAX_LENGTH = 20


class Node:
    def __init__(self):
        self.children = [None] * ALPHABET
        self.word = None


class Trie:
    def __init__(self):
        self.root = Node()
        self.size = 0
        self.nodes = 1

    def _validate(self, text):
        if len(text) > MAX_LENGTH:
            raise ValueError("길이는 20 이하여야 한다")
        for ch in text:
            if not ("a" <= ch <= "z"):
                raise ValueError("영문 소문자만 사용할 수 있다")

    def insert(self, word):
        self._validate(word)
        node = self.root
        moves = 0
        for ch in word:
            index = ord(ch) - ord("a")
            moves += 1
            if node.children[index] is None:
                node.children[index] = Node()
                self.nodes += 1
            node = node.children[index]
        added = node.word is None
        if added:
            node.word = word
            self.size += 1
        return added, moves

    def _walk(self, text):
        node = self.root
        moves = 0
        for ch in text:
            index = ord(ch) - ord("a")
            moves += 1
            node = node.children[index]
            if node is None:
                return None, moves
        return node, moves

    def contains(self, word):
        self._validate(word)
        node, moves = self._walk(word)
        found = node is not None and node.word is not None
        return found, moves

    def _collect(self, node, output, count):
        scans = 0
        if node.word is not None:
            output[count] = node.word
            count += 1
        for index in range(ALPHABET):
            scans += 1
            child = node.children[index]
            if child is not None:
                count, child_scans = self._collect(
                    child, output, count
                )
                scans += child_scans
        return count, scans

    def complete(self, prefix):
        self._validate(prefix)
        node, moves = self._walk(prefix)
        if node is None:
            return None, 0, moves, 0
        output = [None] * self.size
        count, scans = self._collect(node, output, 0)
        return output, count, moves, scans


def show_completion(trie, prefix):
    output, count, moves, scans = trie.complete(prefix)
    print(f"접두사 '{prefix}':", end="")
    if count == 0:
        print(" (없음)", end="")
    else:
        for index in range(count):
            print(" " + output[index], end="")
    print(f" | 이동={moves}, 슬롯={scans}")


def check_boundaries():
    trie = Trie()
    assert trie.insert("") == (True, 0)
    assert trie.insert("") == (False, 0)
    assert trie.contains("") == (True, 0)
    output, count, moves, scans = trie.complete("")
    assert count == 1 and output[0] == ""
    assert moves == 0 and scans == 26

    before = trie.nodes
    rejected = False
    try:
        trie.insert("ab!")
    except ValueError:
        rejected = True
    assert rejected and trie.nodes == before

    rejected = False
    try:
        trie.insert("a" * (MAX_LENGTH + 1))
    except ValueError:
        rejected = True
    assert rejected and trie.nodes == before

    trie.insert("car")
    trie.insert("card")
    assert trie.contains("ca") == (False, 2)
    assert trie.contains("car") == (True, 3)


def main():
    check_boundaries()
    print("경계 검사: 통과")

    trie = Trie()
    inputs = ("car", "card", "care", "cat", "dog", "do", "car")
    total_moves = 0
    for word in inputs:
        added, moves = trie.insert(word)
        total_moves += moves

    print(f"단어={trie.size}, 노드={trie.nodes}")
    print(f"삽입 이동 합계={total_moves}")
    print(
        f"자식 슬롯={ALPHABET * trie.nodes}, "
        f"실제 연결={trie.nodes - 1}"
    )

    for word in ("care", "ca", "cap"):
        found, moves = trie.contains(word)
        print(f"검색 '{word}': {found} | 이동={moves}")

    for prefix in ("ca", "do", "z"):
        show_completion(trie, prefix)

    output, count, moves, scans = trie.complete("")
    assert count == 6 and moves == 0 and scans == 260
    print(f"빈 접두사: 후보={count}, 이동={moves}, 슬롯={scans}")

    # 여기부터 내장 자료구조를 사용한 비교다.
    builtin_words = ["car", "card", "care", "cat", "do", "dog"]
    for prefix in ("ca", "do", "z"):
        matches = []
        checks = 0
        for word in builtin_words:
            checks += 1
            if word.startswith(prefix):
                matches.append(word)

        output, count, moves, scans = trie.complete(prefix)
        same = count == len(matches)
        if same:
            for index in range(count):
                if output[index] != matches[index]:
                    same = False
                    break
        assert same
        print(
            f"비교 '{prefix}': 일치={same}, "
            f"트라이 이동={moves}, 슬롯={scans}, "
            f"내장 단어 검사={checks}"
        )


if __name__ == "__main__":
    main()

줄별 해설

ALPHABET과 MAX_LENGTH는 바뀌지 않는 설정값이다. 대문자로 적은 이름은 상수처럼 사용한다는 관례를 나타낸다. Node의 첫 대입문은 빈 자식 배열을 만들고 두 번째 대입문은 단어 끝이 아니라는 상태를 설정한다. Trie는 루트까지 포함해 노드 수를 1에서 시작한다.

_validate의 길이 검사는 글자 반복보다 먼저 실행된다. 이어지는 반복문은 모든 글자가 허용 범위에 있는지 확인한다. 잘못된 입력이면 ValueError 예외를 발생시켜 호출한 쪽에 실패를 알린다. 밑줄로 시작하는 메서드 이름은 구현 내부에서 사용하려는 의도를 나타내는 관례이며, 호출 자체를 막는 장치는 아니다.

insert는 검증을 마친 뒤에만 구조를 바꾼다. moves는 실제 자식 칸 조회 직전에 증가한다. 새 노드를 만드는 분기는 비어 있는 칸에서만 실행된다. 다음 대입문에서 node를 자식으로 옮기므로 반복문이 한 바퀴 돌 때마다 글자 하나를 처리한다.

반복 뒤의 added는 단어가 새로 등록되었는지를 담는다. 이미 길이 존재해도 단어 끝이 아니었다면 새 단어다. car를 먼저 넣고 ca를 나중에 넣는 경우가 여기에 해당한다. 반대로 같은 car를 다시 넣으면 이동은 다시 수행하지만 size는 증가하지 않는다.

_walk는 삽입과 닮았지만 자식 생성문이 없다. 길이 없는 칸에 도착한 순간 None과 현재 이동 횟수를 반환한다. contains는 그 반환값을 받아 경로와 단어 끝을 모두 확인한다. and는 왼쪽이 거짓이면 오른쪽을 평가하지 않으므로 node가 None일 때 node.word를 읽지 않는다.

_collect의 count는 결과를 다음에 쓸 칸 번호이면서 현재 후보 수다. word가 있으면 그 칸에 문자열 참조를 넣고 하나 증가시킨다. 다음 반복문은 연결 유무와 관계없이 26번 돈다. 재귀 호출에서 돌아온 count로 다음 빈 칸 위치를 이어받고, child_scans를 더해 아래쪽에서 확인한 칸도 합산한다.

리프라고 해서 scans가 0은 아니다. 리프임을 알아내기 위해 빈 자식 칸 26개를 확인한다. 이 때문에 ca 아래의 다섯 노드를 방문하면 26 × 5 = 130칸을 확인한다. 이동 횟수만 보면 놓치기 쉬운 비용이 별도 숫자로 드러난다.

complete는 경로가 없으면 결과 배열을 만들지 않는다. 경로가 있으면 전체 단어 수만큼 확보한 배열에 후보를 채운다. 이 크기는 어느 접두사에서도 넘지 않는 상한이다. 모든 호출에 넉넉한 배열을 새로 만드는 선택은 구현을 단순하게 하지만, 앞서 설명한 O(N) 초기화 비용을 만든다.

show_completion은 후보 수만큼만 배열을 읽는다. print의 end 인수는 출력 뒤에 붙일 문자열을 정한다. 중간 출력에는 줄바꿈을 붙이지 않고, 마지막 출력에서 한 줄을 끝낸다. 빈 문자열이 후보인 경우에도 저장 여부는 정확히 유지되지만 화면에서 보이지 않으므로, 경계 검사에서는 직접 값으로 확인한다.

check_boundaries의 assert는 조건이 거짓이면 실행을 중단하는 검사문이다. 빈 단어, 중복 삽입, 잘못된 문자, 길이 제한, 단어와 접두사의 구분을 확인한다. try와 except는 예상한 예외를 받아 검사할 때 사용한다. 이 코드는 기본 실행 명령을 기준으로 하며, 검사를 생략하는 실행 옵션은 사용하지 않는다.

마지막 비교 구역은 정렬된 내장 단어 목록을 순회한다. 입력 순서는 dog가 do보다 먼저지만 트라이 결과는 사전순이므로, 비교 목록도 같은 순서로 준비한다. 결과의 개수뿐 아니라 각 칸의 단어까지 비교한다. 출력의 ‘일치’는 순서를 포함한 일치다.

실행 결과

macOS나 Linux의 터미널에서 다음 명령을 실행한다. 외부 패키지, 파일 입력, 네트워크 연결은 필요하지 않다.

python3 main.py

예상 출력은 다음과 같다.

경계 검사: 통과
단어=6, 노드=10
삽입 이동 합계=22
자식 슬롯=260, 실제 연결=9
검색 'care': True | 이동=4
검색 'ca': False | 이동=2
검색 'cap': False | 이동=3
접두사 'ca': car card care cat | 이동=2, 슬롯=130
접두사 'do': do dog | 이동=2, 슬롯=52
접두사 'z': (없음) | 이동=1, 슬롯=0
빈 접두사: 후보=6, 이동=0, 슬롯=260
비교 'ca': 일치=True, 트라이 이동=2, 슬롯=130, 내장 단어 검사=6
비교 'do': 일치=True, 트라이 이동=2, 슬롯=52, 내장 단어 검사=6
비교 'z': 일치=True, 트라이 이동=1, 슬롯=0, 내장 단어 검사=6

삽입 이동 합계 22에는 마지막에 다시 넣은 car의 3회도 포함된다. 새 단어가 아니어도 이미 등록된 끝까지 이동해야 중복임을 확인할 수 있다. 검색 ca는 두 번 이동한 뒤 단어 끝이 아니라서 실패한다. cap는 세 번째 자식 조회에서 길이 없어서 실패한다.

비교 출력의 숫자는 단위가 다르다. 트라이는 자식 칸을 세고, 내장 목록은 startswith를 호출한 단어 수를 센다. 따라서 130과 6을 곧바로 비교해 실행 시간이 몇 배라고 말할 수 없다. startswith 내부의 문자 비교 횟수도 이 계측에는 들어 있지 않다.

이 실험에서 확인할 수 있는 것은 작업 범위다. 목록 순회는 세 접두사 모두 여섯 단어를 확인한다. 트라이는 z의 첫 조회에서 멈추지만, ca의 후보를 모을 때는 빈 자식 칸까지 확인한다. 작은 사전에서는 배열의 빈 칸 비용이 크게 보일 수 있다. 구조의 장점과 실제 실행 속도는 같은 질문이 아니다.

단어 길이만큼 문자를 처리한다는 주장도 삽입과 검색 출력으로 확인한다. 후보 수집은 길이만으로 설명되지 않으며 방문한 노드 수가 필요하다. 전체 실행 시간에는 검증, 배열 초기화, 출력도 포함되므로 이 계측은 그중 어떤 부분을 측정했는지 함께 읽어야 한다.

실무에서 자주 틀리는 것

길이 존재하면 등록된 단어라고 판단한다

다음 코드는 ca까지 길이 있으면 검색을 성공으로 처리한다.

# 틀린 코드
node, moves = self._walk(word)
return node is not None, moves

정확한 검색은 단어 끝을 확인해야 한다. 접두사의 존재만 확인하는 기능이라면 다른 이름의 메서드로 구분하는 편이 낫다.

# 고친 코드
node, moves = self._walk(word)
found = node is not None and node.word is not None
return found, moves

자식 노드를 한 번 만든 뒤 모든 칸에서 공유한다

리스트 반복은 객체를 여러 번 새로 생성하지 않는다. 아래 코드는 같은 자식 객체를 26칸에서 가리킨다. 한 갈래를 수정하면 다른 글자의 갈래도 같은 객체를 보게 된다.

# 틀린 코드
self.children = [Node()] * ALPHABET

빈 칸은 None으로 시작하고, 필요한 위치에만 서로 다른 노드를 만든다. None을 반복해 넣는 것은 빈 상태를 표시할 뿐이므로 이 문제가 생기지 않는다.

# 고친 코드
self.children = [None] * ALPHABET

# 삽입 중 필요한 칸에서 실행한다.
if node.children[index] is None:
    node.children[index] = Node()

검증과 삽입을 섞어 실패한 입력의 일부를 남긴다

다음처럼 한 글자씩 확인하면서 바로 노드를 만들면 ab! 입력은 a와 b의 길을 만든 뒤 실패한다. 등록된 단어 수는 그대로여도 불필요한 노드가 남는다.

# 틀린 코드
node = self.root
for ch in word:
    if not ("a" <= ch <= "z"):
        raise ValueError("영문 소문자만 사용할 수 있다")
    index = ord(ch) - ord("a")
    if node.children[index] is None:
        node.children[index] = Node()
    node = node.children[index]

전체 검증을 먼저 끝내면 입력 규칙 위반으로 인한 부분 변경을 막는다. 완성 코드의 경계 검사는 잘못된 삽입 뒤 노드 수가 유지되는지도 확인한다.

# 고친 코드
self._validate(word)
node = self.root
for ch in word:
    index = ord(ch) - ord("a")
    if node.children[index] is None:
        node.children[index] = Node()
        self.nodes += 1
    node = node.children[index]

단어 끝을 참과 거짓만으로 검사한다

빈 문자열은 조건식에서 거짓으로 취급된다. 따라서 word에 빈 문자열을 저장했을 때 아래 코드는 등록된 단어를 놓친다.

# 틀린 코드
if node.word:
    output[count] = node.word
    count += 1

단어 끝이 아니라는 표시는 None으로 정했으므로 그 값과 직접 구분해야 한다. 빈 접두사와 빈 단어는 서로 다른 개념이지만, 빈 단어를 허용한다면 루트가 단어 끝일 수도 있다.

# 고친 코드
if node.word is not None:
    output[count] = node.word
    count += 1

한눈에 보기

자동 완성기를 구현할 때 함께 기억할 판단 기준

항목	구현 규칙	확인한 결과
글자 이동	a부터 z를 0부터 25에 대응시킨다	care 검색은 이동 4회다
단어 끝	word가 None인지 확인한다	ca 검색은 실패한다
중복	기존 단어 끝에서는 size를 늘리지 않는다	7번 넣어도 단어는 6개다
후보 순서	현재 단어를 먼저, 자식은 문자순으로 방문한다	car, card, care, cat 순서다
탐색 비용	접두사 이동과 자식 칸 검사를 나눈다	ca는 이동 2회와 칸 검사 130회다
공간 비용	모든 노드에 26칸을 둔다	연결 9개에 자식 칸 260개를 확보한다
결과 배열	전체 단어 수만큼 고정 확보한다	초기화 O(N)이 메서드 비용에 더해진다

트라이의 핵심은 같은 앞부분을 같은 경로로 표현하는 데 있다. 그 경로의 존재, 단어가 끝나는 위치, 아래에서 후보를 모으는 비용을 구분하면 구현과 분석이 함께 맞아떨어진다. 다음 장에서는 글자의 앞뒤 관계라는 제한을 벗어나, 여러 대상 사이의 연결을 표현하고 탐색하는 방법을 다룬다.

연습 문제

1. 완성 코드의 삽입을 마친 뒤 can을 추가한다. 추가 이동 횟수, 전체 노드 수, ca 자동 완성의 자식 칸 검사 횟수를 예상하고 코드로 확인한다.
2. 접두사까지 가는 길이 존재하는지 확인하는 has_prefix 메서드를 만든다. car만 등록한 상태에서 ca와 빈 문자열은 참이고, z는 거짓이어야 한다. 이동 횟수도 반환한다.
3. 새 트라이에 a와 ab를 넣고 빈 접두사로 자동 완성한다. 결과 순서, 방문 노드 수, 자식 칸 검사 횟수를 구하고 assert로 확인한다.
4. complete가 전체 단어 수 N만큼 결과 배열을 확보하는 비용을 줄이려 한다. 후보를 한 번 세고 정확한 크기의 배열을 만든 뒤 다시 수집하는 방법의 시간과 공간을 설명한다.

정답과 해설

1. can은 세 글자를 처리하므로 이동은 3회다. c와 a는 이미 존재하고 n만 새로 생기므로 전체 노드 수는 11이다. ca 아래는 여섯 노드가 되어 156칸을 확인한다. 결과는 can, car, card, care, cat 순서다. 완성 코드의 main에서 기존 삽입을 끝낸 뒤 다음을 실행하면 확인할 수 있다.

   assert trie.insert("can") == (True, 3)
   assert trie.nodes == 11
   output, count, moves, scans = trie.complete("ca")
   assert count == 5 and moves == 2 and scans == 156
   expected = ("can", "car", "card", "care", "cat")
   for index in range(count):
       assert output[index] == expected[index]
   

2. 단어 끝을 검사하지 않고 경로의 존재만 반환한다. 빈 문자열은 글자를 처리하지 않고 루트에 도착하므로 빈 트라이에서도 참이다. 이는 빈 문자열이 모든 문자열의 접두사라는 규칙과 맞는다. 다음 메서드는 Trie 안에 추가한다.

   def has_prefix(self, prefix):
       self._validate(prefix)
       node, moves = self._walk(prefix)
       return node is not None, moves
   

   다음 검사는 별도의 새 트라이에서 실행한다.

   sample = Trie()
   sample.insert("car")
   assert sample.has_prefix("ca") == (True, 2)
   assert sample.has_prefix("") == (True, 0)
   assert sample.has_prefix("z") == (False, 1)
   

3. 루트, a, b의 세 노드를 방문한다. a의 단어 끝을 기록한 뒤 b로 내려가므로 결과는 a, ab다. 세 노드 모두 자식 칸을 26개씩 확인해 총 78회다.

   sample = Trie()
   sample.insert("a")
   sample.insert("ab")
   output, count, moves, scans = sample.complete("")
   assert sample.nodes == 3
   assert count == 2 and moves == 0 and scans == 78
   assert output[0] == "a" and output[1] == "ab"
   

4. 첫 순회에서 단어 끝의 개수 K를 센 다음 [None] * K를 만든다. 두 번째 순회에서는 기존 _collect로 참조를 채운다. 방문 범위를 두 번 확인하므로 자식 칸 검사 횟수는 52Vp가 되지만, 상수 배를 제외한 시간은 O(P + 26Vp + K)다. 결과 배열 공간은 O(N)에서 O(K)로 줄어든다.

   이 방법에서도 후보를 저장하는 공간과 재귀 호출 공간은 필요하다. 또한 두 순회 사이에 트라이가 변경되지 않는다는 조건이 있어야 센 개수와 실제 수집 개수가 일치한다. 이 장의 프로그램은 한 흐름에서 차례로 실행하므로 그 조건을 유지할 수 있다.