google_like_dictionary

一个简洁的英汉词典应用，提供快速检索、释义查看与复制等能力，界面风格参考 Google 搜索。

功能亮点

• 离线词库：启动时从 assets/data/EnWords.csv 解析 10w+ 词条，并做内存缓存。
• 智能搜索：输入框实时筛选（含缩写、中文释义），自动节流避免卡顿。
• 结果展示：卡片式列表支持点击展开详情、复制释义、下拉刷新。
• 多端支持：基于 Flutter，可运行在 Android、iOS、Web、Windows。

开发命令

flutter pub get           # 安装依赖
flutter run -d chrome     # Web 端热重载调试
flutter analyze           # 静态检查
flutter test --coverage   # 执行测试并生成覆盖率

Windows 安装的 Flutter SDK 可能带有 CRLF 换行，若在 WSL 中运行上述命令失败，请先对 flutter/bin/*.sh 执行 dos2unix。

目录结构

assets/
  data/EnWords.csv    # 词典数据
  images/google.svg   # 顶部 Logo
lib/
  data/               # 数据层（CSV 解析、缓存）
  features/           # 业务控制器
  models/             # 实体定义
  main.dart           # UI 入口
test/                 # 单元与组件测试

应用运行流程概览

1. 启动与数据加载

   • main.dart 中创建 DictionaryRepository 与 DictionaryController，将控制器注入到 UI。
   • 首次进入页面时调用 DictionaryController.load()：
     • 通过 DictionaryRepository.loadEntries() 从 assets/data/EnWords.csv 读取完整 CSV 内容。
     • 使用 CsvToListConverter 将文本行解析为二维数组，再逐行构造 WordEntry：
       • word：英文单词。
       • translation：中文释义。
     • 得到的 List<WordEntry> 缓存在 _entries 与仓库 _cache 中，避免重复 IO。
     • 调用 _buildAvlIndex() 基于 _entries 构建 AVL 索引。
     • 最后 _applyFilter() 初始化 _visibleEntries，并通过 notifyListeners() 通知 UI 刷新。

2. 用户输入与节流

   • 搜索框变化时调用 DictionaryController.updateQuery(value)：
     • 更新 _query，并重置一个 120ms 的 Timer 充当节流。
     • 在用户快速输入期间不会立即触发筛选，只有停止输入超过 120ms 才真正调用 _applyFilter()。
   • 清空按钮会调用 clearQuery()，将 _query 置空并重新应用筛选逻辑。

3. 搜索策略切换

   • 通过底部弹窗（main.dart 中的 _showStrategyPicker()）在两种策略间切换：
     • SearchStrategy.linear：顺序查找。
     • SearchStrategy.avl：基于 AVL 树的前缀索引查找。
   • 选择后调用 setStrategy() 更新 _strategy 并再次执行 _applyFilter()。

4. 结果展示与交互

   • UI 监听 DictionaryController：
     • isLoading 控制骨架屏 / 进度指示。
     • visibleEntries 用于渲染列表结果，默认仅展示前 50 条；搜索时最多 150 条。
     • lastSearchDuration 用于显示最近一次搜索耗时，方便对比不同数据结构性能。
   • 列表项支持点击、复制等操作，但不影响搜索核心逻辑。

AVL 搜索索引的构建与查询

核心数据结构：AvlMap<K, V>

AVL 相关代码位于 lib/data_structures/avl.dart，核心由两部分组成：

• AvlNode<K, V>：

  • key：用于排序的键，这里是小写后的英文单词 String。
  • values：同一键对应的多个值列表 List<V>，在本项目中是多个 WordEntry（处理同形词）。
  • left / right：左右子树指针。
  • height：当前节点高度，用于计算平衡因子。

• AvlMap<K, V>：

  • 内部持有根节点 _root 和一个比较函数 compare(K a, K b)，这里使用 a.compareTo(b) 做字典序比较。
  • 提供：
    • insert(K key, V value)：插入键值对并保持树平衡。
    • get(K key)：按键精确查找对应的 List<V>。
    • forEachInRange(K low, K high, void Function(K, List<V>) f)：在闭区间 [low, high] 内按中序遍历所有键值对，这是前缀搜索的关键。

插入过程：构建自平衡二叉查找树

insert 会调用内部递归函数 _insert(node, key, value)：

1. 标准二叉查找树插入：

   • 若当前子树根 node 为空，则新建 AvlNode(key, [value]) 作为叶子返回。
   • 否则用 compare(key, node.key) 比较：
     • 若结果为 0，表示键相等，将 value 追加到 node.values，支持一个单词对应多个词条。
     • 若结果 < 0，递归插入到左子树 node.left.
     • 若结果 > 0，递归插入到右子树 node.right.

2. 回溯阶段更新高度：

   • 每次从子树返回时调用 _updateHeight(node)：
     • 取左右子树高度中较大值 + 1 作为当前节点高度.

3. 根据平衡因子进行旋转：

   • 通过 _balanceFactor(node) = height(left) - height(right) 判断是否失衡：
     • > 1：左侧过高，属于 LL 或 LR 型：
       • 若左子树平衡因子 < 0，先左旋左子树（LR），再右旋当前节点.
       • 否则直接右旋当前节点（LL）.
     • < -1：右侧过高，属于 RR 或 RL 型：
       • 若右子树平衡因子 > 0，先右旋右子树（RL），再左旋当前节点.
       • 否则直接左旋当前节点（RR）.
   • 旋转通过 _rotateLeft / _rotateRight 实现，调整指针并更新高度，保证整棵树始终满足 AVL 条件（任一节点左右子树高度差不超过 1）。

通过上述过程，当所有 WordEntry 插入完成后，就得到一棵按 小写英文单词排序的自平衡二叉查找树，其高度约为 O(log N)，后续查询和区间遍历都能维持较优复杂度。

构建单词 AVL 索引：_buildAvlIndex()

在 DictionaryController 中，_buildAvlIndex() 专门负责从 _entries 生成 AVL 索引 _avl：

1. 创建 AvlMap<String, WordEntry>，比较函数为 (a, b) => a.compareTo(b)。
2. 遍历 _entries 中的每个 WordEntry e：
   • 提取键 key = e.word.toLowerCase()，统一转小写，实现不区分大小写的英文搜索.
   • 调用 map.insert(key, e) 将词条插入 AVL 树.
3. 最终将构建好的 map 赋值给 _avl，供后续搜索使用.

因为所有数据只在加载或刷新时构建一次索引，平时用户输入只需要在这棵已有的树上做查询，避免了每次搜索都全表扫描.

使用 AVL 做前缀搜索：SearchStrategy.avl

当 _strategy == SearchStrategy.avl 时，_applyFilter() 的核心逻辑是：

1. 若 _avl 为空（尚未构建索引），直接返回空结果.

2. 将用户输入统一为小写：lowerQuery = _query.toLowerCase().

3. 构造一个闭区间上界：high = '$lowerQuery\uffff'：

   • 利用 Unicode 中 \uffff 是一个“很大”的码位.
   • 所有以 lowerQuery 为前缀的单词，其字典序都落在 [lowerQuery, lowerQuery + \uffff] 之间.

4. 调用 _avl.forEachInRange(lowerQuery, high, (k, vs) { ... })：

   • 该方法会在 AVL 树上递归中序遍历，只访问键在 [low, high] 范围内的节点.
   • 对于每个命中键 k 和其对应的 List<WordEntry> vs：
     • 额外通过 k.startsWith(lowerQuery) 再次确认是真正前缀匹配（防御性编程）.
     • 将所有 vs 追加到结果列表 results 中.

5. 对 results 排序：

   • 优先级：完全相等 > 仅前缀匹配 > 其它情况（这里主要是前两种）.
   • 其次按单词长度、再按字典序稳定排序，使结果更符合直觉.

6. 取前 150 条赋值给 _visibleEntries，并记录本次搜索耗时 lastSearchDuration.

由于 AVL 树高度为 O(log N)，forEachInRange 只会遍历与区间相关的子树，因此前缀搜索的时间复杂度约为 O(log N + M)（M 为命中结果数），相比顺序查找在大词库上更有优势.

顺序查找的实现与行为

当 _strategy == SearchStrategy.linear 时，_applyFilter() 会走顺序查找路径：

1. 将查询词转为小写：lowerQuery = _query.toLowerCase().

2. 使用 _entries.where((e) => e.matches(lowerQuery)) 对所有词条做一次线性扫描：

   • WordEntry.matches(query) 会同时在 word 与 translation 上做不区分大小写的 contains 检查：
     • word.toLowerCase().contains(query)：英文中包含查询子串.
     • translation.toLowerCase().contains(query)：中文释义中包含查询子串.
   • 因此顺序查找支持：
     • 英文部分任意子串匹配（不仅限前缀）.
     • 中文释义任意子串匹配（AVL 模式仅针对英文单词前缀）。

3. 对筛选后的 filtered 列表进行排序，使用内部的 rank(e) 函数定义“命中优先级”：

   • 计算 w = e.word.toLowerCase() 与 t = e.translation.toLowerCase().
   • 返回值越小优先级越高：
     • 0：w == lowerQuery，英文完全匹配.
     • 1：w.startsWith(lowerQuery)，英文前缀匹配.
     • 2：w.contains(lowerQuery)，英文子串匹配.
     • 3：t == lowerQuery，中文完全匹配.
     • 4：t.startsWith(lowerQuery)，中文前缀匹配.
     • 5：其他情况.
   • 排序规则：先比 rank，再比单词长度，最后按单词字典序，确保结果顺序稳定且符合直觉（更“精确”的匹配排在前面）。

4. 同样只保留前 150 条结果，并记录耗时.

顺序查找的特点：

• 优点：
  • 逻辑简单，直接扫描 List<WordEntry>，实现和调试成本低.
  • 支持英文和中文的任意子串匹配，灵活度高.
• 缺点：
  • 时间复杂度为 O(N)（再加上排序），在 10w+ 级别词库上，频繁搜索可能带来更高的 CPU 开销.

AVL 搜索 vs 顺序查找：如何选择

本项目通过 SearchStrategy 将两种实现并存，并允许在 UI 中切换，方便你在真实数据规模下对比：

• 偏性能 / 前缀匹配：
  • 适合使用 AVL：
    • 主要按英文单词前缀搜索.
    • 更关心在大词库上的响应速度.
• 偏灵活 / 支持中文和子串搜索：
  • 适合使用顺序查找：
    • 既要按英文，也要按中文释义搜索.
    • 希望支持任意子串而不是仅限前缀.

你可以在运行应用时切换策略，并观察 lastSearchDuration 的变化，直观感受两种数据结构在真实词典规模下的表现差异.

贡献说明

遵循 Conventional Commits（例如 feat(search): add accent matching）。提交前执行 flutter analyze 与 flutter test 并在 PR 中附上测试结果/截图。更多细节参见 AGENTS.md.