13. AutoComplete

검색어 자동완성 시스템

1. 자동 완성이란?

사용자가 검색창에 문자를 입력할 때, 입력한 내용을 바탕으로 예상되는 검색어를 실시간으로 추천하는 기능입니다. 웹 브라우저, 검색 엔진 등 다양한 애플리케이션에서 사용됩니다.

2. 자동 완성 요구사항:

2.1. 빠른 응답속도

사용자가 키보드를 눌러 검색어를 입력하는 즉시 관련 검색어 리스트가 출력되어야 합니다. 몇 밀리초 이내에 완료되어야 합니다.

2.2. 연관성

사용자의 의도에 맞는 제안이 나와야 하며, 관련성 없는 검색어가 추천되면 시스템의 신뢰도가 떨어집니다. 연관성은 사용자의 과거 검색 기록, 지역적 트랜드, 실시간 트렌드를 반영할 수 있습니다.'

2.3. 정렬

자동완성 검색어는 여러개의 추천 목록을 제공하기 때문에, 이 검색어들은 사용자의 관심도와 관련성에 따라 정렬되어야 합니다.

검색어의 인기 정도
사용자 맞춤 정보 (이전 검색 기록, 지역 트랜드 등)
실시간 검색 트랜드

2.4. 규모 확장성

대규모 사용자를 지원할 수 있도록 시스템은 규모 확장성이 필요합니다. 일시적으로 트래픽이 증가하는 시간대에 대처할 수 있어야 합니다.

2.5. 고가용성

시스템이 언제나 동작 가능한 상태를 유지하는 것을 의미합니다. 서버 이중화, 무중단 배포 등을 고려해야 합니다.

3. 간단 설계

자동완성 서비스는 크게 두 가지, 데이터 수집 서비스, 질의 서비스로 구성되어있습니다.

3.1. 데이터 수집 서비스

질의문과 사용빈도를 저장하는 빈도 테이블을 사용합니다. 질의가 들어올때마다, 각 단어들의 카운트를 증가시켜줍니다.

3.2. 질의 서비스

사용자가 'tw'를 검색창에 입력하게 됐을때 빈도 테이블에서 빈도수가 높은 K가지 단어를 정렬하여 보여주게 됩니다.

SELECT * FROPM freqency_table
WHERE query Like 'prefix%'
ORDER BY frequency DESC
LIMIT K;

3.3. 문제점

쿼리 성능 문제: 데이터베이스에서 (prefix search)를 수행하기 때문에, 테이블 내 검색어가 많을 경우 성능이 급격하게 떨어짐.
- LIKE 연산은 인덱스 최적화를 사용하기 어렵기때문에 테이블 풀 스캔 가능성
- 정렬은 검색된 결과를 모두 메모리에 올린 후에 빈도에 따라 정렬을 수행하기 떄문에 부하가 큼
실시간 데이터 반영이 어려움: 관련 검색어가 폭증하더라도, frequency table만 사용하면 변화를 반영 못함.
개인화된 검색어 추천 불가: 모든 사용자에게 동일한 결과

3. 개선 방안

3.1. 트라이 자료구조

특징:

Trie는 검색을 뜻하는 retrieval 에서 용어를 따왔습니다.
트리 형태의 자료구조
각 노드는 글자 하나를 저장하며 최대 26개의 자식 노드를 가짐
각 트리 노드는 하나의 단어 또는 접두어 문자열을 나타냄
검색시 시간 복잡도 O(m*26). (m은 검색어의 길이)
동일한 문자열은 한번만 저장됨으로 메모리 사용량을 최적화

3.2. 트라이 연산

3.2.1. 트라이 생성

새로운 검색어가 데이터베이스에 전송되면, 트라이 구조에 해당 검색어를 반영해야합니다. 트라이 생성은 새로운 검색어가 추가될 때 수행되는 연산입니다. 이 과정에서 새로운 검색어가 트라이의 캐시와 데이터베이스에 저장되어야 하며, 이후 질의 서비스에서 빠르게 검색될 수 있도록 합니다.

3.2.2. 트라이 갱신

트라이 갱신은 이미 존재하는 검색어의 빈도수나 연관성을 기반으로 트라이를 동적으로 변경하는 연산입니다. 예를 들어, 특정 검색어가 특정 시간 동안 급격히 사용량이 증가했다면, 해당 검색어를 최우선 노드로 옮기거나, 해당 검색어가 더 빨리 검색되도록 가중치를 부여할 수 있습니다.

이를 위해 동적 가중치 부여 시스템을 지원해야 하며, 트라이 갱신이 이루어질 때마다 질의 서비스의 성능에 영향을 미치지 않도록 비동기식으로 처리하는 것이 중요합니다.

3.2.3. 검색어 삭제

트라이 구조에서 해당 검색어를 구성하는 경로를 제거하고, 관련된 자원을 해제하는 작업입니다.

특정 검색어를 삭제할때는 공유 노드 관리가 중요합니다. 공유 노드가 완전히 고립되지 않도록 다른 검색어들과의 관계를 유지해야 합니다.

TriLeetcode Trie(Prefix Tree) - Python

class Trie {
    Node root;

    public Trie() {
        root = new Node();
    }
    
    public void insert(String word) {
        root.insert(word, 0);
    }
    
    public boolean search(String word) {
        return root.search(word, 0);
    }
    
    public boolean startsWith(String prefix) {
        return root.startsWith(prefix, 0);
    }

    class Node {
        Node[] nodes;
        boolean isEnd;

        Node() {
            nodes = new Node[26];
        }

        private void insert(String word, int idx) {
            if (idx >= word.length()) return;
            int i = word.charAt(idx) - 'a';
            if (nodes[i] == null) {
                nodes[i] = new Node();
            }

            if (idx == word.length()-1) nodes[i].isEnd = true;
            nodes[i].insert(word, idx+1);
        }

        private boolean search(String word, int idx) {
            if (idx >= word.length()) return false;
            Node node = nodes[word.charAt(idx) - 'a'];
            if (node == null) return false;
            if (idx == word.length() - 1 && node.isEnd) return true;

            return node.search(word, idx+1);

        }

        private boolean startsWith(String prefix, int idx) {
            if (idx >= prefix.length()) return false;
            Node node = nodes[prefix.charAt(idx) - 'a'];
            if (node == null) return false;
            if (idx == prefix.length() - 1) return true;

            return node.startsWith(prefix, idx+1);
        }
    }
}

Leetcode Trie(Prefix Tree) - Java

class Trie {
    Node root;

    public Trie() {
        root = new Node();
    }
    
    public void insert(String word) {
        root.insert(word, 0);
    }
    
    public boolean search(String word) {
        return root.search(word, 0);
    }
    
    public boolean startsWith(String prefix) {
        return root.startsWith(prefix, 0);
    }

    class Node {
        Node[] nodes;
        boolean isEnd;

        Node() {
            nodes = new Node[26];
        }

        private void insert(String word, int idx) {
            if (idx >= word.length()) return;
            int i = word.charAt(idx) - 'a';
            if (nodes[i] == null) {
                nodes[i] = new Node();
            }

            if (idx == word.length()-1) nodes[i].isEnd = true;
            nodes[i].insert(word, idx+1);
        }

        private boolean search(String word, int idx) {
            if (idx >= word.length()) return false;
            Node node = nodes[word.charAt(idx) - 'a'];
            if (node == null) return false;
            if (idx == word.length() - 1 && node.isEnd) return true;

            return node.search(word, idx+1);

        }

        private boolean startsWith(String prefix, int idx) {
            if (idx >= prefix.length()) return false;
            Node node = nodes[prefix.charAt(idx) - 'a'];
            if (node == null) return false;
            if (idx == prefix.length() - 1) return true;

            return node.startsWith(prefix, idx+1);
        }
    }
}

Trie 삭제 연산

public void delete(String word) {
    delete(root, word, 0);
}

private boolean delete(TrieNode current, String word, int index) {
    if (index == word.length()) {
        if (!current.isWord) {
            return false;
        }
        current.isWord = false;
        return current.children.isEmpty();
    }
    char c = word.charAt(index);
    TrieNode node = current.children.get(c);
    if (node == null) {
        return false;
    }
    boolean shouldDeleteCurrentNode = delete(node, word, index + 1);
    if (shouldDeleteCurrentNode) {
        current.children.remove(c);
        return current.children.isEmpty();
    }
    return false;
}

3.3. 개선된 트라이 자료구조

기존 트라이를 더욱 효율적으로 사용할 수 있도록 보완할 수 있습니다. 데이터가 많아질수록 메모리 사용량이 증가하고, 검색 속도가 느려지기 떄문입니다.

3.3.1. 접두어 최대 길이 제한

트라이의 각 경로에서 지나치게 긴 접두어를 저장하지 않도록 하여 메모리 사용량을 최적화하는 기법입니다. 일반적으로 검색어 자동완성에서는 사용자가 몇 글자 이내에서 관련 검색어를 추천하는 경우가 많습니다. 따라서 특정 길이 이상의 접두어를 저장하지 않도록 제한을 두어 메모리 효율을 높일 수 있습니다. 다만, 매우 긴 단어의 정확도를 약간 낮출 수 있는 단점이 있습니다.

예: university -> unive까지만 저장되고 이후의 경로는 생략할 수 있습니다.

3.3.2. 노드에 인기 검색어 캐시

각 트라이 노드에 대해, 해당 경로와 연관된 인기 검색어를 캐싱하여, 빠른 검색 결과를 제공하는 방식입니다. 인기 검색어가 미리 캐시되어 있어 검색 요청 시 빠르게 결과를 반환할 수 있고, 자주 검색되는 키워드는 매번 트라이를 탐색할 필요가 없어서 연산 자원을 절약할 수 있습니다.

예: jav 까지 입력했을때, 해당 노드에 java, javascript, java tutorial 등의 인기 검색어를 미리 캐시해 둘 수 있습니다.

3.4. 트라이 기반 자동완성의 장단점

3.4.1. 장점

빠른 검색 속도
메모리 효율성: 접두어를 공유하여 중복 데이터의 저장을 최소화합니다.
유연한 확장성

검색에 따른 시간복잡도

접두어가 존재하지 않음 : L
접두어가 있고 하위 노드에 단어가 없음: L
접두어가 있고 관련 단어가 100개 존재 (정렬 없음): L + N × L'
접두어가 있고 관련 단어가 100개 존재 (정렬 있음): L + N × L' + N log N
접두어가 있고 상위 K개의 단어만 반환 (정렬 없음): L + N × L' + K
접두어가 있고 상위 K개의 단어만 반환 (정렬 있음, 우선순위 큐 사용): L + N × L' + N log K
접두어가 길고 단어가 많음 (예: 1000개): L + N × L' + N log N
캐싱된 접두어 요청 (정렬 있음): 1
캐싱된 접두어 요청 (정렬 없음): 1
접두어가 있고 연관 단어가 매우 많음 (예: 1만 개, 상위 10개 요청): L + N × L' + N log K
접두어가 있고 긴 단어만 포함 (평균 단어 길이 20자): L + N × 20 + N log N
접두어가 있고 자식 노드가 링크드 리스트로 구현됨: L × D + N × L' + N log N

L: 단어 길이

N: 연관된 단어 길이

L': 평균 단어 길이

K: K개만 추출

3.4.2 단점

복잡한 구현
높은 메모리 사용: 데이터가 방대할 경우 메모리 사용량이 급격히 증가할 수 이습니다.
동적 가중치 조정의 어려움

3.5. 데이터 수집 서비스

3.5.1. 로그 취합 서버

자동 완성 시스템의 연관성 높은 검색어를 추천하기 위해서는 실시간 사용자 검색 로그를 지속적으로 수집하고 분석하는 것이 중요합니다. 로그 취합 서버는 사용자가 입력한 검색어, 검색 시간, 검색 위치 등의 데이터를 수집하여 이후의 데이터 분석 및 검색어 추천에 활용됩니다.