本文目录导读：
我来详细介绍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：支持模糊匹配和拼写纠错
根据实际需求选择合适方案，考虑因素包括数据量、响应速度、内存限制等。
