倒排索引实现

by github LincZero/any-menu/src/Core/search

不过下面初版不支持多对多 (多个input可输出一个output，一个input也可输出多个output)，我改动后的版本才有

// --- 倒排索引实现 by claude sonnet 4.5 ---

class FuzzySearchEngine {
  // 倒排索引: 字符 -> 包含该字符的文档集合
  private index: Map<string, Set<string>> = new Map();
  // 文档存储
  private documents: Map<string, string> = new Map();

  /**
   * 添加文档
   * @param id 文档ID
   * @param content 文档内容
   */
  add(id: string, content: string) {
    this.documents.set(id, content);
    
    // 为每个字符建立索引
    for (const char of content) {
      if (!this.index.has(char)) {
        this.index.set(char, new Set());
      }
      this.index.get(char)!.add(id);
    }
  }

  /**
   * 模糊搜索: 支持子序列匹配
   * @param query 查询关键词（如 "物 和 然"）
   * @returns 匹配的文档ID列表
   */
  search(query: string): string[] {
    // 去除空格，提取关键字符
    const chars = query.replace(/\s+/g, '').split('');
    
    if (chars.length === 0) return [];

    // 1. 找出包含第一个字符的所有文档
    let candidates = this.index.get(chars[0]);
    if (!candidates || candidates.size === 0) return [];

    // 2. 对每个候选文档，验证是否包含子序列
    const results: string[] = [];
    for (const docId of candidates) {
      const content = this.documents.get(docId)!;
      if (this.isSubsequence(chars, content)) {
        results.push(docId);
      }
    }

    return results;
  }

  /**
   * 检查 chars 是否为 text 的子序列
   */
  private isSubsequence(chars: string[], text: string): boolean {
    let charIndex = 0;
    for (const char of text) {
      if (char === chars[charIndex]) {
        charIndex++;
        if (charIndex === chars.length) return true;
      }
    }
    return charIndex === chars.length;
  }

  static test() {
    // 使用示例
    const fuzzyEngine = new FuzzySearchEngine();
    fuzzyEngine.add('doc1', '动物和自然');
    fuzzyEngine.add('doc2', '植物与生态');

    console.log(fuzzyEngine.search('物 和 然')); // ['doc1']
    console.log(fuzzyEngine.search('物 生')); // ['doc2']
  }
}