倒排索引的功能设计
倒排索引（Inverted Index）是一种高效的数据结构，常用于全文搜索和信息检索系统。它的核心思想是将文档中每个关键字（term）与包含该关键字的文档列表进行映射。
以下是实现倒排索引功能的设计步骤和代码示例：
功能需求
文档存储：
存储一组文档，文档可以是字符串（文本内容）。
索引构建：
从文档中提取关键词，构建倒排索引。
关键词查询：
根据用户输入的关键词，快速返回包含该关键词的文档ID。
多关键词查询：
支持 AND、OR 等多关键词查询模式。
设计步骤
1. 数据结构
使用以下数据结构：
Map<String, List<Integer>>（或HashMap）：每个关键词映射到一个文档ID列表。List<String>：存储原始文档内容，用于返回查询结果。
2. 倒排索引的构建
遍历所有文档，分词（Tokenization）提取关键词。
对于每个关键词，将文档ID添加到其倒排列表中。
3. 查询功能
单关键词查询：直接查找倒排索引。
多关键词查询：
AND 查询：取关键词对应的文档列表的交集。
OR 查询：取关键词对应的文档列表的并集。
Java实现代码
import java.util.*;
public class InvertedIndex {
// 倒排索引结构：关键词 -> 包含该关键词的文档ID列表
private Map<String, List<Integer>> index;
// 文档存储：文档ID -> 文档内容
private List<String> documents;
public InvertedIndex() {
this.index = new HashMap<>();
this.documents = new ArrayList<>();
}
// 添加文档到系统并更新倒排索引
public void addDocument(String document) {
int docId = documents.size(); // 文档ID为索引位置
documents.add(document); // 添加文档到文档存储
// 分词并更新倒排索引
String[] tokens = tokenize(document);
for (String token : tokens) {
index.computeIfAbsent(token, k -> new ArrayList<>()).add(docId);
}
}
// 分词函数，简单实现（按空格分词并转换为小写）
private String[] tokenize(String document) {
return document.toLowerCase().split("\\W+"); // 使用正则分割
}
// 查询单关键词
public List<String> search(String keyword) {
keyword = keyword.toLowerCase();
List<Integer> docIds = index.getOrDefault(keyword, new ArrayList<>());
List<String> results = new ArrayList<>();
for (int docId : docIds) {
results.add(documents.get(docId));
}
return results;
}
// 查询多个关键词（AND 模式）
public List<String> searchAnd(String... keywords) {
List<Set<Integer>> resultSets = new ArrayList<>();
for (String keyword : keywords) {
keyword = keyword.toLowerCase();
resultSets.add(new HashSet<>(index.getOrDefault(keyword, new ArrayList<>())));
}
// 求交集
Set<Integer> intersection = resultSets.get(0);
for (Set<Integer> resultSet : resultSets) {
intersection.retainAll(resultSet);
}
// 返回结果
List<String> results = new ArrayList<>();
for (int docId : intersection) {
results.add(documents.get(docId));
}
return results;
}
// 查询多个关键词（OR 模式）
public List<String> searchOr(String... keywords) {
Set<Integer> union = new HashSet<>();
for (String keyword : keywords) {
keyword = keyword.toLowerCase();
union.addAll(index.getOrDefault(keyword, new ArrayList<>()));
}
// 返回结果
List<String> results = new ArrayList<>();
for (int docId : union) {
results.add(documents.get(docId));
}
return results;
}
// 打印倒排索引（用于调试）
public void printIndex() {
for (Map.Entry<String, List<Integer>> entry : index.entrySet()) {
System.out.println(entry.getKey() + " -> " + entry.getValue());
}
}
// 测试方法
public static void main(String[] args) {
InvertedIndex invertedIndex = new InvertedIndex();
// 添加文档
invertedIndex.addDocument("Hello world");
invertedIndex.addDocument("Hello Java");
invertedIndex.addDocument("Java is fun");
invertedIndex.addDocument("Inverted index example");
// 打印倒排索引
invertedIndex.printIndex();
// 查询单关键词
System.out.println("Search 'Java': " + invertedIndex.search("Java"));
// 查询多个关键词（AND）
System.out.println("Search 'Hello' AND 'Java': " + invertedIndex.searchAnd("Hello", "Java"));
// 查询多个关键词（OR）
System.out.println("Search 'Java' OR 'example': " + invertedIndex.searchOr("Java", "example"));
}
}
代码说明
文档存储：
documents列表存储所有文档，文档ID是其索引位置。
倒排索引：
使用
HashMap<String, List<Integer>>存储每个关键词与对应文档ID列表的映射。computeIfAbsent确保关键词不存在时初始化列表。
查询功能：
单关键词：直接返回关键词对应的文档ID列表。
AND查询：取所有关键词的文档ID列表交集。
OR查询：取所有关键词的文档ID列表并集。
分词与归一化：
使用正则表达式按非字母数字字符分割，并将关键词转为小写。
输出示例
运行代码后可能输出如下：
hello -> [0, 1]
world -> [0]
java -> [1, 2]
is -> [2]
fun -> [2]
inverted -> [3]
index -> [3]
example -> [3]
Search 'Java': [Hello Java, Java is fun]
Search 'Hello' AND 'Java': [Hello Java]
Search 'Java' OR 'example': [Hello Java, Java is fun, Inverted index example]
总结
这个实现展示了一个简单但功能齐全的倒排索引系统，适用于小型的全文检索需求。如果需要处理大规模数据，可以进一步优化分词、索引存储（如基于磁盘存储或分布式系统），并加入排名算法（如 TF-IDF）以提高查询精度。