Trie 자동완성: 접두사 아래 단어를 정해진 순서로 모으기

Trie 자동완성은 접두사의 마지막 노드까지 이동한 뒤 그 아래의 단어 종료 지점만 모으는 탐색입니다. 결과 순서와 최대 개수를 먼저 정하면 삽입 순서에 흔들리지 않는 목록을 만들 수 있습니다.

선수 지식: Map, 트리 순회, Trie의 단어 종료 표시와 접두사 검색

• 접두사 존재와 완성 단어 수집을 구분합니다.
• Unicode 코드 포인트 순서로 결과를 제한하여 반환합니다.
• 공통 경로를 남기며 단어만 안전하게 삭제합니다.

접두사까지 이동한 뒤 아래쪽만 순회합니다

단어마다 루트에서 문자 연결을 따라 내려가고 마지막 노드에 단어 종료 표시를 둡니다. 자동차 이름 목록에 car, cart, cat이 있다면 앞의 두 문자 경로는 공유하지만 car와 cart의 종료 위치는 다릅니다. 접두사 ca에 맞는 목록을 얻으려면 먼저 c와 a의 연결을 찾고 그 노드 아래에서 종료 표시가 있는 위치만 수집합니다. 경로가 존재한다는 사실만으로 모든 중간 문자열을 결과에 넣으면 안 됩니다.

수집 함수는 현재 경로를 문자 배열로 들고 갑니다. 자식으로 내려가기 전에 문자를 하나 붙이고 돌아오면 하나 빼므로 형제 분기를 탐색할 때 이전 글자가 섞이지 않습니다. 종료 표시를 만나면 그 순간의 경로를 문자열로 합쳐 결과에 저장합니다. 접두사 자체도 등록된 단어라면 아래 자식보다 먼저 수집하므로 짧은 단어가 그 단어로 시작하는 긴 단어보다 앞에 나옵니다.

자동완성은 접두사에 맞는 개수만 세는 연산보다 할 일이 많습니다. 개수를 이미 저장해 두었더라도 실제 문자열을 목록으로 반환하려면 해당 종료 지점까지 내려가야 합니다. 따라서 기존 Trie 검색과 개수 세기의 경로 탐색은 그대로 활용하되 결과 수집 비용은 따로 생각해야 합니다. 이 글의 예제는 빈 문자열도 단어로 허용하며 그 종료 표시는 루트에 둡니다.

문자 단위와 정렬 순서를 계약으로 정합니다

JavaScript 문자열의 인덱스는 UTF-16 코드 단위이고 이모지는 두 코드 단위일 수 있습니다. 예제는 반복 구문으로 문자열을 읽어 코드 포인트 단위로 간선을 만듭니다. 따라서 웃는 얼굴 이모지를 반으로 나눈 두 연결 대신 하나의 연결로 저장합니다. 다만 여러 코드 포인트가 합쳐 화면의 한 글자가 되는 경우까지 하나의 간선으로 묶는 자소 단위 처리는 하지 않습니다.

입력 단어와 접두사는 먼저 NFC 정규화합니다. 완성형 한글 가와 분해된 한글 자모 조합이 같은 정규형으로 들어오므로 중복 단어를 한 번만 셉니다. 결과도 정규화된 문자열입니다. 정규화는 대소문자 통일이 아니므로 영문 대문자와 소문자는 구분합니다. 검색 서비스를 만들 때 문화권에 맞춘 정렬이나 대소문자 무시는 별도 정책으로 정해야 합니다.

Map의 자식 순서는 삽입 순서이므로 그대로 순회하면 단어를 넣은 순서에 따라 자동완성이 달라집니다. 예제는 각 노드의 자식 문자를 코드 포인트 수의 오름차순으로 정렬해 탐색합니다. 이 기준은 한국어 사전 순서나 추천 점수 순서가 아니며 실행 환경의 언어 설정에도 의존하지 않습니다. 보충 평면 문자와 기본 다국어 평면 문자를 비교할 때도 UTF-16 문자열 비교가 아니라 명시한 숫자 기준을 사용합니다.

단어 종료를 먼저 보고 제한에 도달하면 멈춥니다

최대 개수는 기본 10이며 0 이상인 안전한 정수만 받습니다. 0이면 빈 목록을 바로 반환합니다. 음수, 소수, 무한대는 의미가 불분명한 요청으로 거부합니다. 존재하지 않는 접두사는 오류가 아니라 맞는 단어가 없다는 뜻이므로 빈 목록을 반환합니다. 빈 접두사는 루트에서 시작해 전체 사전의 앞부분을 수집하며, 빈 문자열이 등록되어 있다면 첫 결과로 포함됩니다.

제한에 도달하면 현재 자식 반복문뿐 아니라 모든 바깥 재귀 단계에서도 멈춰야 합니다. 안쪽 호출에서만 반환하면 부모가 다음 형제로 계속 내려가 불필요한 탐색을 할 수 있습니다. 예제는 단어를 추가한 직후와 자식에서 돌아온 직후 모두 개수를 확인합니다. 이 방식은 목록 개수를 제한하지만 방문한 각 노드의 자식 정렬 비용까지 사라지게 하지는 않습니다.

단어 삭제는 공유된 접두사 경로를 남깁니다

car를 지울 때 cart가 남아 있다면 r 노드까지 지워서는 안 됩니다. 우선 car의 마지막 노드에서 종료 표시만 끄고, 아래에 자식이 없는 경우에만 경로를 거꾸로 올라가며 연결을 정리합니다. 단어 종료 표시가 남아 있거나 자식이 하나라도 있는 노드를 만나면 중단합니다. 따라서 car를 지운 뒤에도 ca의 결과는 cart와 cat이 되고, cart까지 지우면 더는 쓰지 않는 r 경로만 정리할 수 있습니다.

없는 단어를 지울 때는 접두사 경로가 존재하더라도 종료 표시가 없다면 거짓을 반환합니다. 예를 들어 cart만 저장한 트리에서 car는 경로는 있지만 등록된 단어가 아닙니다. 빈 문자열 삭제는 루트의 종료 표시만 끄고 다른 자식은 유지합니다. 삭제와 삽입에서도 같은 NFC 정규화를 적용하므로 검색과 저장의 문자 기준이 어긋나지 않습니다.

결과에 담는 문자열을 만드는 비용도 무시할 수 없습니다. 긴 단어를 여러 개 반환하면 그 총길이만큼 복사가 필요합니다. 또한 방문한 노드마다 자식 키를 배열로 모아 정렬합니다. 단순히 접두사 길이만큼 걸린다고 설명하면 이 수집과 정렬을 빠뜨리게 됩니다. 매우 긴 한 단어는 재귀 깊이 제한에 닿을 수 있으므로 이 예제는 학습용 길이를 가정합니다. 큰 사전에서는 명시적 스택이나 정렬된 자식 구조를 검토할 수 있습니다.

직접 확인할 때는 단어 삽입 순서를 뒤집어도 같은 목록이 나오는지, 이모지 접두사가 깨지지 않는지, 분해 한글과 완성형이 중복으로 세어지지 않는지 보세요. 이어 짧은 단어만 삭제한 뒤 긴 단어가 남는지 확인하면 종료 표시와 경로의 역할을 구분할 수 있습니다. 접두사 개수만 맞추는 검사에 머무르지 않고 결과 문자열의 순서와 제한까지 비교하는 것이 핵심입니다.

전체 코드와 직접 실행

개념을 읽었다면 아래 예제를 직접 실행하며 상태 변화를 확인할 수 있습니다.

function normalizeWord(word) {
  if (typeof word !== 'string') throw new TypeError('word must be a string');
  return word.normalize('NFC');
}
class TrieNode {
  constructor() {
    this.children = new Map();
    this.terminal = false;
  }
}
class Trie {
  constructor() {
    this.root = new TrieNode();
    this.size = 0;
  }
  insert(word) {
    word = normalizeWord(word);
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch);
    }
    if (node.terminal) return false;
    node.terminal = true;
    this.size++;
    return true;
  }
  remove(word) {
    word = normalizeWord(word);
    let node = this.root;
    const path = [];
    for (const ch of word) {
      if (!node.children.has(ch)) return false;
      path.push([node, ch]);
      node = node.children.get(ch);
    }
    if (!node.terminal) return false;
    node.terminal = false;
    this.size--;
    for (let i = path.length - 1; i >= 0; i--) {
      if (node.terminal || node.children.size > 0) break;
      const [parent, ch] = path[i];
      parent.children.delete(ch);
      node = parent;
    }
    return true;
  }
  autocomplete(prefix, limit = 10) {
    prefix = normalizeWord(prefix);
    if (!Number.isSafeInteger(limit) || limit < 0) {
      throw new TypeError('limit must be a nonnegative safe integer');
    }
    if (limit === 0) return [];
    let node = this.root;
    for (const ch of prefix) {
      node = node.children.get(ch);
      if (!node) return [];
    }
    const result = [];
    const path = [...prefix];
    function collect(current) {
      if (current.terminal) result.push(path.join(''));
      if (result.length >= limit) return;
      const keys = [...current.children.keys()].sort((a, b) => a.codePointAt(0) - b.codePointAt(0));
      for (const ch of keys) {
        path.push(ch);
        collect(current.children.get(ch));
        path.pop();
        if (result.length >= limit) return;
      }
    }
    collect(node);
    return result;
  }
}
const trie = new Trie();
['cat', 'cart', 'car', '😀나', '😀가'].forEach(word => trie.insert(word));
console.log(JSON.stringify(trie.autocomplete('ca', 2)));
console.log(JSON.stringify(trie.autocomplete('😀')));
console.log(JSON.stringify(trie.autocomplete('없는')));
trie.remove('car');
console.log(JSON.stringify(trie.autocomplete('ca')));

node algorithm-trie-autocomplete.mjs

["car","cart"]
["😀가","😀나"]
[]
["cart","cat"]

비용과 적용 범위

정규화 비용을 별도로 두고 Map 접근을 평균 O(1)로 가정하면 길이 L인 단어의 삽입·삭제는 O(L)입니다. 자동완성은 접두사 길이 P, 방문 노드 V의 자식 수 d(v), 반환 문자열 총길이 Z에 대해 O(P + Σ d(v) log(d(v)+1) + Z) 시간입니다. 경로·재귀는 최대 단어 길이 H에 비례하며, 재귀 도중 유지되는 자식 정렬 배열과 결과 문자열 공간도 추가됩니다. Trie 저장은 총 등록 문자 경로 수에 비례합니다.

직접 확인해 보기

car와 cart가 있을 때 car만 삭제한 뒤 autocomplete("car", 1)은 무엇을 반환하나요? 빈 접두사에 limit=0이면요?

함께 읽을 글

• JavaScript Trie: Unicode 접두사 검색과 안전한 삭제 구현 — 자동완성의 바탕인 Unicode 경로·종료 표시·삭제 규칙을 복습합니다.
• 코딩테스트 Trie: 접두사에 맞는 단어 수 세기 — 접두사 아래 단어의 개수와 실제 목록 수집의 차이를 비교합니다.
• JavaScript 문자열 해시 테이블 구현: 충돌 처리와 리사이즈, NFC 정규화 — 문자열 자료구조에서 같은 NFC 정책을 일관되게 적용하는 이유를 확인합니다.

참고 자료

• Algorithms, 4th Edition — TrieSET — keysWithPrefix와 collect의 접두사 경로 탐색 및 하위 키 수집 원리를 참고했습니다. 참고 코드는 256방향 ASCII Trie이며 Unicode 코드 포인트·NFC·결과 제한은 이 글의 구현에서 추가로 정한 계약입니다.