Java案例如何实现自动补全？

本文目录导读：

1. Trie树（前缀树）实现
2. 加权自动补全（带频率排序）
3. 使用Lucene实现（企业级方案）
4. 基于N-gram的模糊自动补全
5. 使用示例
6. 选择建议

我来详细介绍Java中实现自动补全功能的几种常见方案：

Trie树（前缀树）实现

这是最经典的自动补全实现方式：

import java.util.*;
class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEnd = false;
    // 存储以该节点为结尾的词（可选）
    String word;
}
public class AutoComplete {
    private TrieNode root;
    public AutoComplete() {
        root = new TrieNode();
    }
    // 插入单词
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
        }
        node.isEnd = true;
        node.word = word;
    }
    // 搜索前缀
    public List<String> search(String prefix) {
        List<String> results = new ArrayList<>();
        TrieNode node = root;
        // 先找到前缀对应的节点
        for (char c : prefix.toCharArray()) {
            if (!node.children.containsKey(c)) {
                return results;
            }
            node = node.children.get(c);
        }
        // DFS收集所有可能的词
        dfs(node, results);
        return results;
    }
    private void dfs(TrieNode node, List<String> results) {
        if (node.isEnd) {
            results.add(node.word);
        }
        for (TrieNode child : node.children.values()) {
            dfs(child, results);
        }
    }
    public static void main(String[] args) {
        AutoComplete ac = new AutoComplete();
        ac.insert("apple");
        ac.insert("application");
        ac.insert("appetite");
        ac.insert("banana");
        ac.insert("ball");
        System.out.println("输入 'ap': " + ac.search("ap"));
        System.out.println("输入 'ba': " + ac.search("ba"));
    }
}

加权自动补全（带频率排序）

import java.util.*;
class WeightedAutoComplete {
    static class WordFrequency {
        String word;
        int frequency;
        WordFrequency(String word, int frequency) {
            this.word = word;
            this.frequency = frequency;
        }
    }
    private Map<String, Integer> wordFreq = new HashMap<>();
    private TrieNode root;
    public WeightedAutoComplete() {
        root = new TrieNode();
    }
    // 插入单词并设置频率
    public void insert(String word, int frequency) {
        wordFreq.put(word, frequency);
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
        }
        node.isEnd = true;
    }
    // 按频率排序返回结果
    public List<String> search(String prefix, int topK) {
        List<String> results = search(prefix);
        // 按频率排序
        results.sort((a, b) -> 
            Integer.compare(
                wordFreq.getOrDefault(b, 0), 
                wordFreq.getOrDefault(a, 0)
            )
        );
        // 返回前K个
        return results.subList(0, Math.min(topK, results.size()));
    }
    // 基本搜索方法（同上）
    private List<String> search(String prefix) {
        List<String> results = new ArrayList<>();
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            if (!node.children.containsKey(c)) {
                return results;
            }
            node = node.children.get(c);
        }
        dfs(node, prefix, results);
        return results;
    }
    private void dfs(TrieNode node, String prefix, List<String> results) {
        if (node.isEnd) {
            results.add(prefix);
        }
        for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) {
            dfs(entry.getValue(), prefix + entry.getKey(), results);
        }
    }
}

使用Lucene实现（企业级方案）

import org.apache.lucene.analysis.standard.StandardAnalyzer;
import org.apache.lucene.document.Document;
import org.apache.lucene.document.Field;
import org.apache.lucene.document.TextField;
import org.apache.lucene.index.*;
import org.apache.lucene.queryparser.classic.QueryParser;
import org.apache.lucene.search.*;
import org.apache.lucene.store.Directory;
import org.apache.lucene.store.RAMDirectory;
public class LuceneAutoComplete {
    private Directory directory;
    private StandardAnalyzer analyzer;
    public LuceneAutoComplete() {
        directory = new RAMDirectory();
        analyzer = new StandardAnalyzer();
    }
    public void buildIndex(List<String> words) throws Exception {
        IndexWriterConfig config = new IndexWriterConfig(analyzer);
        IndexWriter writer = new IndexWriter(directory, config);
        for (String word : words) {
            Document doc = new Document();
            doc.add(new TextField("word", word, Field.Store.YES));
            writer.addDocument(doc);
        }
        writer.close();
    }
    public List<String> autoComplete(String prefix) throws Exception {
        List<String> results = new ArrayList<>();
        IndexReader reader = DirectoryReader.open(directory);
        IndexSearcher searcher = new IndexSearcher(reader);
        // 使用前缀查询
        Query query = new PrefixQuery(new Term("word", prefix));
        TopDocs topDocs = searcher.search(query, 10);
        for (ScoreDoc scoreDoc : topDocs.scoreDocs) {
            Document doc = searcher.doc(scoreDoc.doc);
            results.add(doc.get("word"));
        }
        reader.close();
        return results;
    }
}

基于N-gram的模糊自动补全

import java.util.*;
import java.util.stream.*;
public class NGramAutoComplete {
    private Map<String, Set<String>> ngramIndex = new HashMap<>();
    private int ngramSize = 2;
    public NGramAutoComplete(int ngramSize) {
        this.ngramSize = ngramSize;
    }
    // 生成n-gram
    private List<String> generateNGrams(String word) {
        List<String> ngrams = new ArrayList<>();
        String paddedWord = "#" + word + "#";  // 添加边界标记
        for (int i = 0; i <= paddedWord.length() - ngramSize; i++) {
            ngrams.add(paddedWord.substring(i, i + ngramSize));
        }
        return ngrams;
    }
    // 添加单词到索引
    public void addWord(String word) {
        List<String> ngrams = generateNGrams(word);
        for (String ngram : ngrams) {
            ngramIndex.computeIfAbsent(ngram, k -> new HashSet<>())
                     .add(word);
        }
    }
    // 搜索
    public List<String> search(String query) {
        List<String> queryNGrams = generateNGrams(query);
        // 找到包含所有n-gram的单词
        Set<String> result = new HashSet<>();
        boolean first = true;
        for (String ngram : queryNGrams) {
            if (ngramIndex.containsKey(ngram)) {
                if (first) {
                    result.addAll(ngramIndex.get(ngram));
                    first = false;
                } else {
                    result.retainAll(ngramIndex.get(ngram));
                }
            } else {
                return Collections.emptyList();
            }
        }
        // 按匹配度排序
        return result.stream()
                    .sorted(Comparator.comparingInt(word -> 
                        -levenshteinDistance(word, query)))
                    .collect(Collectors.toList());
    }
    // 编辑距离计算
    private int levenshteinDistance(String s1, String s2) {
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        for (int i = 0; i <= s1.length(); i++) dp[i][0] = i;
        for (int j = 0; j <= s2.length(); j++) dp[0][j] = j;
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                int cost = s1.charAt(i-1) == s2.charAt(j-1) ? 0 : 1;
                dp[i][j] = Math.min(Math.min(
                    dp[i-1][j] + 1,
                    dp[i][j-1] + 1),
                    dp[i-1][j-1] + cost
                );
            }
        }
        return dp[s1.length()][s2.length()];
    }
}

使用示例

public class AutoCompleteDemo {
    public static void main(String[] args) {
        // 使用Trie树
        AutoComplete trieComplete = new AutoComplete();
        trieComplete.insert("java");
        trieComplete.insert("javascript");
        trieComplete.insert("python");
        trieComplete.insert("javaee");
        System.out.println("Trie自动补全 'ja': " + trieComplete.search("ja"));
        // 使用加权自动补全
        WeightedAutoComplete weightedComplete = new WeightedAutoComplete();
        weightedComplete.insert("java", 100);
        weightedComplete.insert("javascript", 50);
        weightedComplete.insert("javaee", 30);
        System.out.println("加权自动补全 'ja': " + weightedComplete.search("ja", 5));
    }
}

选择建议

• Trie树：适合小规模数据，内存占用小，速度快
• 加权自动补全：需要排序结果时使用
• Lucene：适合大规模数据，企业级应用
• N-gram：支持模糊匹配和拼写纠错

根据实际需求选择合适方案，考虑因素包括数据量、响应速度、内存限制等。