从零到一构建智能终端(四)：Frecency 算法在命令补全中的应用

引言

当用户在终端输入命令时，补全系统需要从成百上千的候选项中选出最相关的几个。传统的排序方法要么基于字母顺序（无用），要么基于使用频率（忽略时间因素）。本文介绍一种更智能的排序算法——Frecency，它同时考虑使用频率和时间因素，能够更准确地预测用户意图。

问题：为什么频率排序不够好？

假设用户的命令历史如下：

命令	使用次数	最后使用时间
`git status`	200	3个月前
`npm run dev`	50	10分钟前
`docker ps`	80	1周前

如果只按频率排序，git status 会排在第一位。但用户当前可能在做前端开发，npm run dev 才是最需要的命令。

纯频率排序的问题：

项目切换：用户换了项目，历史高频命令可能完全无关
习惯变化：用户学了新工具，老命令频率虽高但已不再使用
冷启动：新命令刚用一两次，永远排在老命令后面

Frecency：频率 + 时近性

Frecency 这个词由 Firefox 团队在 2007 年发明，是 Frequency（频率）和 Recency（时近性）的合成词。其核心思想是：

一个条目的重要性 = 它被使用的次数 × 最近使用的时间权重

基本公式

最简单的 Frecency 计算：

frecency_score = frequency × recency_weight

其中 recency_weight 是一个基于时间的衰减函数，越近的使用权重越高。

时间衰减函数设计

关键在于如何设计衰减函数。常见的几种方案：

1. 阶梯衰减（Firefox 方案）

将时间划分为几个区间，每个区间一个固定权重：

时间范围	权重
4小时内	100
1天内	70
1周内	50
1月内	30
3月内	10
更早	0

优点：计算简单，可调参数直观缺点：边界处会有跳变（4小时01分突然从100跌到70）

2. 指数衰减

recency_weight = e^(-λt)

其中 t 是距离上次使用的时间，λ 是衰减系数。

λ = 0.1：缓慢衰减，一周后权重约 50%
λ = 0.5：快速衰减，一天后权重约 60%

优点：平滑无跳变缺点：需要实时计算，参数调优不直观

3. 幂律衰减

recency_weight = 1 / (1 + t)^α

优点：长尾特性，古老条目不会完全消失缺点：衰减较慢，可能导致老数据影响过大

终端补全场景的选择

对于终端命令补全，我推荐混合方案：

使用阶梯衰减作为基础（简单可控）
在同一阶梯内使用精确时间排序（避免随机性）
对频率使用对数压缩（避免高频命令永远霸榜）

score = log(1 + frequency) × tier_weight + recency_bonus

其中：

log(1 + frequency)：对数压缩，使用1次=0分，10次≈2.3分，100次≈4.6分
tier_weight：阶梯权重（100/70/50/30/10）
recency_bonus：同一阶梯内，按精确时间戳微调

工程实现考量

数据存储

每条命令需要记录：

{
  command: string,      // 命令文本
  frequency: int,       // 累计使用次数
  last_used: timestamp  // 最后使用时间
}

存储选择：

SQLite：持久化，支持复杂查询，适合桌面应用
内存 HashMap + 定期持久化：高性能，适合实时补全
LRU Cache：限制大小，自动淘汰，适合资源受限环境

计算时机

两种策略：

1. 查询时计算（On-demand）

每次补全请求:
  1. 获取所有匹配前缀的命令
  2. 计算每个命令的 frecency 分数
  3. 排序返回 top-k

优点：分数总是最新的缺点：候选项多时计算开销大

2. 预计算 + 增量更新

命令执行时:
  1. 更新该命令的 frequency 和 last_used
  2. 重新计算该命令的 frecency 分数
  3. 更新排序索引

补全请求时:
  1. 直接从排序索引中查询

优点：查询极快（O(log n)）缺点：实现复杂，需要维护索引

推荐：对于终端补全场景（候选项通常 < 10000），查询时计算完全够用。现代 CPU 对这个量级的排序毫无压力。

频率更新策略

不是每次按键都要更新频率，而是命令执行成功后才更新：

用户输入 git sta → 显示补全
用户选择 git status → 不更新（只是浏览）
用户按回车执行 → 更新 git status 的频率和时间戳

这样避免了"看了但没用"的命令污染频率数据。

冷启动处理

新安装的终端没有历史数据，如何提供有意义的补全？

方案一：内置热门命令

预置一份"通用高频命令"列表：

git status, git commit, git push, git pull
npm install, npm run dev, npm run build
cd, ls, cat, grep, find
docker ps, docker run, docker-compose up

给这些命令一个初始 frecency 分数，但权重低于用户实际使用过的命令。

方案二：导入 Shell 历史

首次启动时，扫描 ~/.bash_history 或 ~/.zsh_history，导入已有的命令历史。

方案三：渐进式学习

不做任何预置，让系统随用户使用自然学习。前几天体验较差，但之后会完全个性化。

进阶优化

上下文感知

纯 Frecency 忽略了一个重要因素：当前上下文。

同一个命令在不同目录下的重要性不同：

在 ~/projects/frontend 目录，npm run dev 应该排在前面
在 ~/projects/backend 目录，cargo run 应该排在前面

解决方案：按目录建立独立的 Frecency 索引

{
  global_frecency: { ... },          // 全局统计
  per_directory_frecency: {
    "/home/user/projects/frontend": { ... },
    "/home/user/projects/backend": { ... }
  }
}

查询时，同时查全局和当前目录的索引，目录特定的结果权重更高。

命令序列预测

Frecency 解决的是"单个命令"的排序问题。更进一步，可以考虑命令序列：

用户刚执行了 git add .，下一条命令大概率是 git commit

这需要记录命令对的转移概率：

P(git commit | git add) = 0.85
P(git status | git add) = 0.10
P(git diff | git add) = 0.05

将 Frecency 分数与转移概率结合：

final_score = frecency_score × (1 + α × transition_probability)

其中 α 控制序列预测的影响力。

衰减参数自适应

不同用户的使用模式不同：

活跃用户：每天执行上百条命令，衰减应该快
低频用户：一周才用几次终端，衰减应该慢

可以根据用户的活跃度动态调整衰减参数：

λ = base_λ × (daily_command_count / average_daily_count)

与其他算法的对比

算法	优点	缺点	适用场景
纯频率	简单	忽略时间	静态数据
纯 LRU	时间敏感	忽略频率	缓存淘汰
Frecency	平衡	需要存储时间戳	用户行为预测
机器学习	强大	复杂、数据饥渴	大规模系统

对于终端补全这个场景，Frecency 是复杂度与效果的最佳平衡点。它不需要复杂的模型训练，不需要大量历史数据，却能显著提升用户体验。

总结

Frecency 算法通过结合使用频率和时近性，解决了纯频率排序的时效性问题。在终端命令补全场景中：

阶梯衰减 + 对数压缩频率是实用的组合
命令执行时更新而非按键时更新
目录级别的上下文能显著提升准确率
命令序列预测是进阶优化方向

这个算法已经在 Firefox 的地址栏、Sublime Text 的命令面板、以及众多现代终端应用中得到验证。它简单、有效、可解释——这正是好算法的特征。

引言