검색 알고리즘 완벽 가이드

문서 1: "The quick brown fox"
문서 2: "The lazy dog"

역색인:
"the"    → [문서1, 문서2]
"quick"  → [문서1]
"brown"  → [문서1]
"fox"    → [문서1]
"lazy"   → [문서2]
"dog"    → [문서2]

import java.util.HashMap;
import java.util.Map;
 
/**
 * Trie 노드 클래스
 * 각 노드는 하나의 문자를 나타내며, 자식 노드들과 단어 종료 여부를 저장합니다.
 */
class TrieNode {
    // 자식 노드들을 저장하는 HashMap
    // Key: 문자, Value: 해당 문자로 이어지는 TrieNode
    Map<Character, TrieNode> children;
    
    // 이 노드가 단어의 끝인지 표시하는 플래그
    // true면 루트부터 이 노드까지의 경로가 완전한 단어를 나타냄
    boolean isEnd;
    
    /**
     * TrieNode 생성자
     * 초기화: 빈 HashMap과 isEnd = false
     */
    public TrieNode() {
        this.children = new HashMap<>();
        this.isEnd = false;
    }
}
 
/**
 * Trie 자료구조 클래스
 * 문자열 집합을 효율적으로 저장하고 검색하는 트리 구조
 * 
 * 시간복잡도:
 * - 삽입: O(m), m = 문자열 길이
 * - 검색: O(m)
 * - 접두사 검색: O(m)
 */
class Trie {
    // Trie의 루트 노드 (빈 문자열을 나타냄)
    private TrieNode root;
    
    /**
     * Trie 생성자
     * 빈 루트 노드로 초기화
     */
    public Trie() {
        this.root = new TrieNode();
    }
    
    /**
     * 단어를 Trie에 삽입합니다.
     * 시간복잡도: O(m), m은 단어의 길이
     * 
     * 동작 과정:
     * 1. 루트 노드에서 시작
     * 2. 단어의 각 문자를 순회하며:
     *    - 현재 노드의 자식 중 해당 문자가 없으면 새 노드 생성
     *    - 해당 문자의 자식 노드로 이동
     * 3. 마지막 노드의 isEnd를 true로 설정
     * 
     * @param word 삽입할 단어
     */
    public void insert(String word) {
        // 1단계: 루트 노드에서 시작
        TrieNode node = root;
        
        // 2단계: 단어의 각 문자를 순회
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            
            // 2-1단계: 현재 노드의 자식 중 해당 문자가 있는지 확인
            // 없으면 새로운 TrieNode를 생성하여 추가 (O(1) 연산)
            if (!node.children.containsKey(c)) {
                node.children.put(c, new TrieNode());
            }
            
            // 2-2단계: 해당 문자의 자식 노드로 이동
            node = node.children.get(c);
        }
        
        // 3단계: 마지막 노드를 단어의 끝으로 표시
        // 이렇게 하면 "app"와 "apple"을 구별할 수 있음
        node.isEnd = true;
    }
    
    /**
     * 단어가 Trie에 존재하는지 검색합니다.
     * 시간복잡도: O(m), m은 단어의 길이
     * 
     * 동작 과정:
     * 1. 루트 노드에서 시작
     * 2. 단어의 각 문자를 순회하며:
     *    - 현재 노드의 자식 중 해당 문자가 없으면 false 반환
     *    - 해당 문자의 자식 노드로 이동
     * 3. 마지막 노드의 isEnd 값을 반환
     * 
     * @param word 검색할 단어
     * @return 단어가 존재하면 true, 아니면 false
     */
    public boolean search(String word) {
        // 1단계: 루트 노드에서 시작
        TrieNode node = root;
        
        // 2단계: 단어의 각 문자를 순회
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            
            // 2-1단계: 해당 문자가 자식 노드에 없으면 검색 실패
            if (!node.children.containsKey(c)) {
                return false;
            }
            
            // 2-2단계: 해당 문자의 자식 노드로 이동
            node = node.children.get(c);
        }
        
        // 3단계: 마지막 노드가 단어의 끝인지 확인
        // "app"를 검색할 때 "apple"이 있어도 "app"의 isEnd가 false면 false 반환
        return node.isEnd;
    }
    
    /**
     * 주어진 접두사로 시작하는 단어가 Trie에 존재하는지 확인합니다.
     * 시간복잡도: O(m), m은 접두사의 길이
     * 
     * 동작 과정:
     * 1. 루트 노드에서 시작
     * 2. 접두사의 각 문자를 순회하며:
     *    - 현재 노드의 자식 중 해당 문자가 없으면 false 반환
     *    - 해당 문자의 자식 노드로 이동
     * 3. 모든 문자를 찾으면 true 반환 (isEnd 확인 불필요)
     * 
     * @param prefix 검색할 접두사
     * @return 접두사로 시작하는 단어가 존재하면 true, 아니면 false
     */
    public boolean startsWith(String prefix) {
        // 1단계: 루트 노드에서 시작
        TrieNode node = root;
        
        // 2단계: 접두사의 각 문자를 순회
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            
            // 2-1단계: 해당 문자가 자식 노드에 없으면 검색 실패
            if (!node.children.containsKey(c)) {
                return false;
            }
            
            // 2-2단계: 해당 문자의 자식 노드로 이동
            node = node.children.get(c);
        }
        
        // 3단계: 모든 문자를 찾았으면 true 반환
        // search()와 달리 isEnd 확인하지 않음 (접두사만 확인)
        return true;
    }
    
    /**
     * 사용 예시
     */
    public static void main(String[] args) {
        Trie trie = new Trie();
        
        // 단어 삽입
        trie.insert("apple");
        trie.insert("app");
        trie.insert("application");
        
        // 검색 테스트
        System.out.println(trie.search("app"));          // true - "app"는 완전한 단어로 존재
        System.out.println(trie.search("appl"));         // false - "appl"은 완전한 단어가 아님
        System.out.println(trie.startsWith("appl"));     // true - "appl"로 시작하는 단어 존재 (apple, application)
    }
}

import java.util.*;
 
/**
 * 매칭 결과를 저장하는 클래스
 * 찾은 패턴과 시작 위치를 포함
 */
class Match {
    String pattern;  // 매칭된 패턴 문자열
    int position;    // 텍스트에서의 시작 위치
    
    public Match(String pattern, int position) {
        this.pattern = pattern;
        this.position = position;
    }
    
    @Override
    public String toString() {
        return String.format("패턴 '%s' found at position %d", pattern, position);
    }
}
 
/**
 * 아호코라식(Aho-Corasick) 알고리즘 구현 클래스
 * 여러 패턴을 동시에 검색하는 문자열 매칭 알고리즘
 * 
 * 시간복잡도:
 * - 전처리 (패턴 추가 + Failure Link 구성): O(m), m = 모든 패턴의 총 길이
 * - 검색: O(n + z), n = 텍스트 길이, z = 매칭 개수
 * 
 * 핵심 구조:
 * 1. goto: 상태 전이 함수 (Trie 구조)
 * 2. fail: 실패 링크 (매칭 실패 시 이동할 상태)
 * 3. output: 각 상태에서 매칭되는 패턴들
 */
class AhoCorasick {
    // Trie 구조: 상태 -> {문자: 다음_상태}
    // 예: goto.get(0).get('a') = 1 (상태 0에서 'a'를 읽으면 상태 1로 이동)
    private Map<Integer, Map<Character, Integer>> gotoFunction;
    
    // Failure Link: 상태 -> 실패_시_이동할_상태
    // 예: fail.get(5) = 2 (상태 5에서 매칭 실패 시 상태 2로 이동)
    private Map<Integer, Integer> failFunction;
    
    // Output 함수: 상태 -> [매칭된_패턴_인덱스들]
    // 예: output.get(3) = [0, 2] (상태 3에서 패턴 0번과 2번이 매칭됨)
    private Map<Integer, List<Integer>> outputFunction;
    
    // 현재 사용 중인 상태 번호 (0부터 시작, 루트는 0)
    private int stateCount;
    
    /**
     * AhoCorasick 생성자
     * 초기 상태: 루트 노드(상태 0)만 존재
     */
    public AhoCorasick() {
        this.gotoFunction = new HashMap<>();
        this.failFunction = new HashMap<>();
        this.outputFunction = new HashMap<>();
        this.stateCount = 0;
        
        // 루트 상태(0) 초기화
        gotoFunction.put(0, new HashMap<>());
        outputFunction.put(0, new ArrayList<>());
    }
    
    /**
     * 패턴을 Trie에 추가합니다.
     * 시간복잡도: O(k), k는 패턴의 길이
     * 
     * 동작 과정:
     * 1. 루트 상태(0)에서 시작
     * 2. 패턴의 각 문자를 순회하며:
     *    - 현재 상태에서 해당 문자로 가는 전이가 없으면 새 상태 생성
     *    - 해당 문자의 다음 상태로 이동
     * 3. 마지막 상태에 패턴 인덱스를 output에 추가
     * 
     * @param pattern 추가할 패턴 문자열
     * @param index 패턴의 인덱스 (검색 결과에서 어떤 패턴인지 식별용)
     */
    public void addPattern(String pattern, int index) {
        // 1단계: 루트 상태에서 시작
        int state = 0;
        
        // 2단계: 패턴의 각 문자를 순회
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            
            // 2-1단계: 현재 상태에서 해당 문자로 가는 전이가 있는지 확인
            Map<Character, Integer> transitions = gotoFunction.get(state);
            
            if (!transitions.containsKey(c)) {
                // 2-2단계: 없으면 새로운 상태 생성
                stateCount++;
                int newState = stateCount;
                
                // 새 상태의 전이 함수와 output 초기화
                transitions.put(c, newState);
                gotoFunction.put(newState, new HashMap<>());
                outputFunction.put(newState, new ArrayList<>());
            }
            
            // 2-3단계: 다음 상태로 이동
            state = transitions.get(c);
        }
        
        // 3단계: 마지막 상태에 패턴 인덱스 추가
        // 이 상태에 도달하면 해당 패턴이 매칭되었다는 의미
        outputFunction.get(state).add(index);
    }
    
    /**
     * Failure Link를 BFS로 구성합니다.
     * 시간복잡도: O(m), m은 모든 패턴의 총 길이
     * 
     * 동작 과정:
     * 1. Level 1 (루트의 직접 자식들): 모두 루트(0)로 실패 링크 설정
     * 2. Level 2 이상: BFS로 각 노드의 실패 링크 계산
     *    - 부모의 실패 링크를 따라가며 매칭되는 상태 찾기
     *    - 찾으면 그곳으로 링크, 못 찾으면 루트로 링크
     * 3. Output 상속: 실패 링크가 가리키는 상태의 output도 현재 상태에 추가
     * 
     * Failure Link의 의미:
     * "현재까지 읽은 문자열의 가장 긴 proper suffix가 나타내는 상태"
     */
    public void buildFailureLinks() {
        Queue<Integer> queue = new LinkedList<>();
        
        // 1단계: Level 1 초기화 (루트의 직접 자식들)
        // 루트의 모든 자식은 실패 시 루트로 돌아감
        Map<Character, Integer> rootTransitions = gotoFunction.get(0);
        for (int state : rootTransitions.values()) {
            failFunction.put(state, 0);  // 루트로 실패 링크 설정
            queue.offer(state);          // BFS 큐에 추가
        }
        
        // 2단계: Level 2 이상 처리 (BFS)
        while (!queue.isEmpty()) {
            int currentState = queue.poll();
            
            // 현재 상태의 모든 전이를 확인
            Map<Character, Integer> transitions = gotoFunction.get(currentState);
            
            for (Map.Entry<Character, Integer> entry : transitions.entrySet()) {
                char c = entry.getKey();
                int nextState = entry.getValue();
                
                // 다음 레벨 탐색을 위해 큐에 추가
                queue.offer(nextState);
                
                // 2-1단계: 실패 링크 계산
                // 현재 상태의 실패 링크에서 시작하여
                // 해당 문자로 갈 수 있는 상태를 찾을 때까지 실패 링크를 따라감
                int failState = failFunction.get(currentState);
                
                while (failState != 0 && !gotoFunction.get(failState).containsKey(c)) {
                    failState = failFunction.get(failState);
                }
                
                // 2-2단계: 실패 링크 설정
                if (gotoFunction.get(failState).containsKey(c)) {
                    // 해당 문자로 갈 수 있는 상태를 찾음
                    failFunction.put(nextState, gotoFunction.get(failState).get(c));
                } else {
                    // 찾지 못하면 루트로
                    failFunction.put(nextState, 0);
                }
                
                // 2-3단계: Output 상속
                // 실패 링크가 가리키는 상태의 output도 현재 상태에 추가
                // 이렇게 하면 "she"를 찾을 때 "he"도 동시에 찾을 수 있음
                List<Integer> inherited = outputFunction.get(failFunction.get(nextState));
                outputFunction.get(nextState).addAll(inherited);
            }
        }
    }
    
    /**
     * 텍스트에서 모든 패턴을 검색합니다.
     * 시간복잡도: O(n + z), n은 텍스트 길이, z는 매칭 개수
     * 
     * 동작 과정:
     * 1. 루트 상태에서 시작
     * 2. 텍스트의 각 문자를 순회하며:
     *    - 현재 상태에서 해당 문자로 가는 전이가 있으면 이동
     *    - 없으면 실패 링크를 따라가며 전이 가능한 상태 찾기
     * 3. 각 상태에서 output에 있는 모든 패턴을 결과에 추가
     * 
     * Amortized O(1) 분석:
     * - 각 문자마다 상태 깊이가 최대 1 증가 (총 n번)
     * - 실패 링크는 깊이를 감소시킴 (총 최대 n번)
     * - 따라서 전체 O(2n) = O(n)
     * 
     * @param text 검색할 텍스트
     * @param patterns 패턴 리스트 (인덱스로 패턴 문자열 찾기 위함)
     * @return 매칭 결과 리스트 (패턴과 위치)
     */
    public List<Match> search(String text, List<String> patterns) {
        List<Match> results = new ArrayList<>();
        
        // 1단계: 루트 상태에서 시작
        int state = 0;
        
        // 2단계: 텍스트의 각 문자를 순회
        for (int i = 0; i < text.length(); i++) {
            char c = text.charAt(i);
            
            // 2-1단계: 다음 상태로 전이 시도
            // 현재 상태에서 해당 문자로 가는 전이가 없으면
            // 실패 링크를 따라가며 전이 가능한 상태를 찾음
            while (state != 0 && !gotoFunction.get(state).containsKey(c)) {
                state = failFunction.get(state);  // 실패 링크 따라가기
            }
            
            // 2-2단계: 전이 가능한 상태로 이동
            if (gotoFunction.get(state).containsKey(c)) {
                state = gotoFunction.get(state).get(c);
            }
            // else: state = 0 (루트에 머무름)
            
            // 3단계: 현재 상태에서 매칭되는 모든 패턴 출력
            List<Integer> matchedPatterns = outputFunction.get(state);
            for (int patternIndex : matchedPatterns) {
                String pattern = patterns.get(patternIndex);
                // 패턴의 시작 위치 계산: 현재 위치 - 패턴 길이 + 1
                int startPos = i - pattern.length() + 1;
                results.add(new Match(pattern, startPos));
            }
        }
        
        return results;
    }
    
    /**
     * 사용 예시
     */
    public static void main(String[] args) {
        AhoCorasick ac = new AhoCorasick();
        
        // 1단계: 패턴 추가
        List<String> patterns = Arrays.asList("he", "she", "his", "hers");
        for (int i = 0; i < patterns.size(); i++) {
            ac.addPattern(patterns.get(i), i);
        }
        
        // 2단계: Failure Link 구성
        ac.buildFailureLinks();
        
        // 3단계: 검색 수행
        String text = "she sells seashells by the seashore";
        List<Match> matches = ac.search(text, patterns);
        
        // 4단계: 결과 출력
        for (Match match : matches) {
            System.out.println(match);
        }
        
        // 출력:
        // 패턴 'she' found at position 0
        // 패턴 'he' found at position 1
        // 패턴 'she' found at position 10
        // 패턴 'he' found at position 11
        // 패턴 'she' found at position 27
        // 패턴 'he' found at position 28
    }
}

/**
 * 벡터 유틸리티 클래스
 * 벡터 간 거리와 유사도를 계산하는 정적 메서드 제공
 */
class VectorUtils {
    
    /**
     * 두 벡터 간의 유클리드 거리를 계산합니다.
     * 시간복잡도: O(n), n은 벡터의 차원
     * 
     * 수학 공식:
     * d = √((x₁-y₁)² + (x₂-y₂)² + ... + (xₙ-yₙ)²)
     * 
     * 동작 과정:
     * 1. 각 차원에서 두 벡터의 차이를 계산
     * 2. 차이의 제곱을 모두 합산
     * 3. 합산 결과의 제곱근을 계산하여 반환
     * 
     * @param a 첫 번째 벡터
     * @param b 두 번째 벡터
     * @return 유클리드 거리 값
     * @throws IllegalArgumentException 벡터 길이가 다를 경우
     */
    public static double euclideanDistance(double[] a, double[] b) {
        // 예외 처리: 벡터 길이가 같은지 확인
        if (a.length != b.length) {
            throw new IllegalArgumentException(
                "벡터의 차원이 다릅니다: " + a.length + " vs " + b.length
            );
        }
        
        // 1단계: 각 차원에서의 차이의 제곱을 합산
        double sumOfSquares = 0.0;
        
        for (int i = 0; i < a.length; i++) {
            // 각 차원에서 차이 계산
            double diff = a[i] - b[i];
            
            // 차이의 제곱을 누적 합산
            // 예: a[0]=0, b[0]=3이면 diff=3, diff²=9
            sumOfSquares += diff * diff;
        }
        
        // 2단계: 제곱합의 제곱근 계산
        // √(sumOfSquares)
        return Math.sqrt(sumOfSquares);
    }
    
    /**
     * 사용 예시: 유클리드 거리 계산
     */
    public static void exampleEuclideanDistance() {
        // 2차원 벡터 예시
        double[] a = {0, 0};
        double[] b = {3, 4};
        
        double distance = euclideanDistance(a, b);
        System.out.println("유클리드 거리: " + distance);  // 5.0
        
        // 수식 검증:
        // √((3-0)² + (4-0)²) = √(9 + 16) = √25 = 5
    }
}

A·B = 3×6 + 4×8 = 18 + 32 = 50
|A| = √(9 + 16) = 5
|B| = √(36 + 64) = 10
cos(θ) = 50 / (5 × 10) = 1

/**
 * 벡터 유틸리티 클래스 (계속)
 */
class VectorUtils {
    
    /**
     * 두 벡터 간의 코사인 유사도를 계산합니다.
     * 시간복잡도: O(n), n은 벡터의 차원
     * 
     * 수학 공식:
     * cos(θ) = (A·B) / (|A| × |B|)
     * - A·B: 내적 (dot product)
     * - |A|, |B|: 벡터의 크기 (magnitude)
     * 
     * 반환값 범위:
     * - 1: 완전히 같은 방향
     * - 0: 직교 (90도)
     * - -1: 완전히 반대 방향
     * 
     * 동작 과정:
     * 1. 두 벡터의 내적 계산
     * 2. 각 벡터의 크기(길이) 계산
     * 3. 내적을 두 크기의 곱으로 나눔
     * 
     * @param a 첫 번째 벡터
     * @param b 두 번째 벡터
     * @return 코사인 유사도 (-1 ~ 1)
     * @throws IllegalArgumentException 벡터 길이가 다르거나 영벡터일 경우
     */
    public static double cosineSimilarity(double[] a, double[] b) {
        // 예외 처리: 벡터 길이가 같은지 확인
        if (a.length != b.length) {
            throw new IllegalArgumentException(
                "벡터의 차원이 다릅니다: " + a.length + " vs " + b.length
            );
        }
        
        // 1단계: 내적(dot product) 계산
        // A·B = a₁b₁ + a₂b₂ + ... + aₙbₙ
        double dotProduct = 0.0;
        
        for (int i = 0; i < a.length; i++) {
            dotProduct += a[i] * b[i];
        }
        
        // 2단계: 각 벡터의 크기(magnitude) 계산
        // |A| = √(a₁² + a₂² + ... + aₙ²)
        double magnitudeA = 0.0;
        double magnitudeB = 0.0;
        
        for (int i = 0; i < a.length; i++) {
            magnitudeA += a[i] * a[i];  // a[i]의 제곱을 누적
            magnitudeB += b[i] * b[i];  // b[i]의 제곱을 누적
        }
        
        // 제곱합의 제곱근을 계산하여 크기를 얻음
        magnitudeA = Math.sqrt(magnitudeA);
        magnitudeB = Math.sqrt(magnitudeB);
        
        // 예외 처리: 영벡터 확인 (0으로 나누기 방지)
        if (magnitudeA == 0.0 || magnitudeB == 0.0) {
            throw new IllegalArgumentException(
                "영벡터는 코사인 유사도를 계산할 수 없습니다"
            );
        }
        
        // 3단계: 코사인 유사도 계산
        // cos(θ) = (A·B) / (|A| × |B|)
        return dotProduct / (magnitudeA * magnitudeB);
    }
    
    /**
     * 사용 예시: 코사인 유사도 계산
     */
    public static void exampleCosineSimilarity() {
        // 같은 방향의 벡터들 (크기만 다름)
        double[] a = {3, 4};
        double[] b = {6, 8};
        
        double similarity = cosineSimilarity(a, b);
        System.out.println("코사인 유사도: " + similarity);  // 1.0 (완전히 같은 방향)
        
        // 수식 검증:
        // A·B = 3×6 + 4×8 = 18 + 32 = 50
        // |A| = √(3² + 4²) = √(9 + 16) = √25 = 5
        // |B| = √(6² + 8²) = √(36 + 64) = √100 = 10
        // cos(θ) = 50 / (5 × 10) = 50 / 50 = 1.0
        
        // 직교하는 벡터들
        double[] c = {1, 0};
        double[] d = {0, 1};
        
        double orthogonal = cosineSimilarity(c, d);
        System.out.println("직교 벡터 유사도: " + orthogonal);  // 0.0 (90도)
    }
    
    /**
     * 전체 사용 예시
     */
    public static void main(String[] args) {
        System.out.println("=== 유클리드 거리 예시 ===");
        exampleEuclideanDistance();
        
        System.out.println("\n=== 코사인 유사도 예시 ===");
        exampleCosineSimilarity();
    }
}

1. 1000개 중심점 중 10개 선택: 1,000번 거리 계산
2. 10개 클러스터 내부 검색: 10 × (1,000,000 / 1,000) = 10,000번
총: 11,000번 (Brute-force는 1,000,000번!)