倒排索引的功能設計
倒排索引（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）以提高查詢精度。
