第7章：搜索引擎设计

type TrieNode struct {
	children map[rune]*TrieNode
	isEnd    bool
	freq     int  // 词频（用于排序）
}

type Trie struct {
	root *TrieNode
}

func NewTrie() *Trie {
	return &Trie{
		root: &TrieNode{
			children: make(map[rune]*TrieNode),
		},
	}
}

// Insert 插入词
func (t *Trie) Insert(word string, freq int) {
	node := t.root
	for _, ch := range word {
		if node.children[ch] == nil {
			node.children[ch] = &TrieNode{
				children: make(map[rune]*TrieNode),
			}
		}
		node = node.children[ch]
	}
	node.isEnd = true
	node.freq = freq
}

// Search 搜索建议（自动补全）
func (t *Trie) Search(prefix string, limit int) []string {
	node := t.root
	
	// 找到前缀节点
	for _, ch := range prefix {
		if node.children[ch] == nil {
			return []string{}
		}
		node = node.children[ch]
	}

	// DFS收集所有后缀
	results := make([]string, 0)
	t.dfs(node, prefix, &results, limit)

	return results
}

func (t *Trie) dfs(node *TrieNode, current string, results *[]string, limit int) {
	if len(*results) >= limit {
		return
	}

	if node.isEnd {
		*results = append(*results, current)
	}

	for ch, child := range node.children {
		t.dfs(child, current+string(ch), results, limit)
	}
}

package search

import (
	"sort"
	"strings"
	"sync"
)

// SearchEngine 搜索引擎
type SearchEngine struct {
	index     map[string]*PostingList  // 倒排索引
	documents map[int]*Document        // 文档存储
	mu        sync.RWMutex
	tokenizer *ChineseTokenizer
	bm25      *BM25
}

// Document 文档
type Document struct {
	ID      int
	Title   string
	Content string
	Length  int
	Terms   map[string]int  // term → frequency
}

// PostingList 倒排列表
type PostingList struct {
	Term     string
	Postings []*Posting
}

// Posting 倒排项
type Posting struct {
	DocID     int
	Frequency int
	Positions []int
}

func NewSearchEngine() *SearchEngine {
	return &SearchEngine{
		index:     make(map[string]*PostingList),
		documents: make(map[int]*Document),
		tokenizer: NewChineseTokenizer(),
		bm25:      NewBM25(100, 0),
	}
}

// IndexDocument 索引文档
func (se *SearchEngine) IndexDocument(doc *Document) {
	se.mu.Lock()
	defer se.mu.Unlock()

	// 分词
	terms := se.tokenizer.Tokenize(doc.Title + " " + doc.Content)

	// 统计词频和位置
	doc.Terms = make(map[string]int)
	termPositions := make(map[string][]int)

	for pos, term := range terms {
		doc.Terms[term]++
		termPositions[term] = append(termPositions[term], pos)
	}

	doc.Length = len(terms)

	// 存储文档
	se.documents[doc.ID] = doc

	// 构建倒排索引
	for term, freq := range doc.Terms {
		if se.index[term] == nil {
			se.index[term] = &PostingList{
				Term:     term,
				Postings: make([]*Posting, 0),
			}
		}

		se.index[term].Postings = append(se.index[term].Postings, &Posting{
			DocID:     doc.ID,
			Frequency: freq,
			Positions: termPositions[term],
		})
	}

	// 更新BM25参数
	se.updateBM25Stats()
}

// Search 搜索
func (se *SearchEngine) Search(query string, limit int) []*SearchResult {
	se.mu.RLock()
	defer se.mu.RUnlock()

	// 分词
	terms := se.tokenizer.Tokenize(query)

	// 找到包含所有词的文档（AND查询）
	candidates := se.findCandidates(terms)

	// 计算BM25分数
	results := make([]*SearchResult, 0)
	for docID := range candidates {
		doc := se.documents[docID]
		score := se.calculateScore(terms, doc)

		results = append(results, &SearchResult{
			DocID: docID,
			Title: doc.Title,
			Score: score,
		})
	}

	// 按分数排序
	sort.Slice(results, func(i, j int) bool {
		return results[i].Score > results[j].Score
	})

	// 返回Top N
	if len(results) > limit {
		results = results[:limit]
	}

	return results
}

// findCandidates 找候选文档
func (se *SearchEngine) findCandidates(terms []string) map[int]bool {
	candidates := make(map[int]bool)

	for i, term := range terms {
		postingList := se.index[term]
		if postingList == nil {
			// 有词未找到，返回空
			return make(map[int]bool)
		}

		if i == 0 {
			// 第一个词，加入所有文档
			for _, posting := range postingList.Postings {
				candidates[posting.DocID] = true
			}
		} else {
			// 后续词，取交集
			newCandidates := make(map[int]bool)
			for _, posting := range postingList.Postings {
				if candidates[posting.DocID] {
					newCandidates[posting.DocID] = true
				}
			}
			candidates = newCandidates
		}
	}

	return candidates
}

// calculateScore 计算BM25分数
func (se *SearchEngine) calculateScore(terms []string, doc *Document) float64 {
	score := 0.0

	for _, term := range terms {
		termFreq := doc.Terms[term]
		docsWithTerm := len(se.index[term].Postings)

		score += se.bm25.CalculateScore(termFreq, doc.Length, docsWithTerm)
	}

	return score
}

// updateBM25Stats 更新BM25统计信息
func (se *SearchEngine) updateBM25Stats() {
	totalLen := 0
	for _, doc := range se.documents {
		totalLen += doc.Length
	}

	avgDocLen := float64(totalLen) / float64(len(se.documents))
	se.bm25 = NewBM25(avgDocLen, len(se.documents))
}

// SearchResult 搜索结果
type SearchResult struct {
	DocID int
	Title string
	Score float64
}

// 使用Filter（可缓存）代替Query
GET /products/_search
{
  "query": {
    "bool": {
      "must": [
        { "match": { "title": "iPhone" } }
      ],
      "filter": [  // Filter会被缓存
        { "range": { "price": { "gte": 5000, "lte": 10000 } } },
        { "term": { "category": "Electronics" } }
      ]
    }
  }
}

// 分页优化：使用search_after代替from/size
GET /products/_search
{
  "size": 10,
  "query": { "match_all": {} },
  "search_after": [12345],  // 上一页最后一个文档的sort值
  "sort": [
    { "_id": "asc" }
  ]
}

输入："iph"
Trie查找：
  i → p → h → one (iPhone)
         → ad (iPad)

返回：["iPhone", "iPad"]

func LevenshteinDistance(s1, s2 string) int {
	// 计算两个字符串的最小编辑距离
	// "iphone" vs "iphoen" = 1
}

// 纠错：找编辑距离<=2的词