LeanType 建议引擎详解：如何预测下一个词？评分流水线与 Ngram 上下文原理完整解析

LeanType 是一款开源、可深度定制的 Android 智能键盘（HeliBoard 分支），内置离线预测输入引擎：你每敲一个字母，它都能实时算出最可能的词并显示在建议条上，甚至在你还没打空格前就预判出下一个词。本文带你走读它的 C++ 评分流水线与 Ngram 上下文模型，搞懂"键盘为什么这么聪明"。

一张图看懂：从指尖到建议条的 3 步流水线 🎯

LeanType 的建议引擎继承自 AOSP LatinIME 并做了深度优化，核心代码全部运行在设备本地（libjni_latinime.so），无需联网。整体流程可以拆成三步：

1. 触摸建模：把每次按键的坐标、时间、指针 ID 封装成输入事件，并通过 ProximityInfo 计算"这个坐标附近还有哪些键可能被误按"——这是容忍手抖的关键。
2. Trie 词库搜索：C++ 层 Suggest::getSuggestions() 以词典 Trie（前缀树）为骨架，逐字符展开搜索节点（DicNode），同时容忍替换、漏敲、多敲、换位等错误类型。
3. 评分与排序：所有搜索完的"终点节点"（terminal）进入评分流水线，按"复合距离"从低到高排序，产出建议条上的候选词。

Kotlin 侧的总入口是 Suggest.kt 中的getSuggestedWords()，它把词库、上下文和键盘布局组装好，再通过 JNI 调用 BinaryDictionary.kt 中的getSuggestionsNative()进入 C++ 引擎。

评分流水线：空间距离 + 语言距离如何合成"置信度" 📐

每个 DicNode 在扩展过程中会持续累加两类距离，定义在 dic_node_state_scoring.h：

复合距离 = 空间距离(spatial) + 语言距离(language) × 语言权重(weightOfLangModelVsSpatialModel)

搜索阶段的规则集中在 suggest.cpp 的expandCurrentDicNodes()中，每个输入点会尝试多种"修正假设"：

• MATCH_CHAR / PROXIMITY_CHAR：命中或邻键命中（比如把w按成了相邻的键）；
• SUBSTITUTION / OMISSION / INSERTION / TRANSPOSITION：替换、漏敲、多敲、换位，代价参数全部集中在 scoring_params.h，如SUBSTITUTION_COST、OMISSION_COST、TRANSPOSITION_COST；
• DIGRAPH：ch、sh等双字母组合整体匹配；
• NEW_WORD / SPACE_OMISSION：检测到词边界，回到 Trie 根节点继续搜下一个词，实现多词连改（如hevis→he is）。

低分节点会被优先扩展、高分节点提前剪枝，由 dic_nodes_cache.h 的优先级队列管理，保证在手机上也能毫秒级出结果。

Ngram 上下文原理：上文的词决定下一个词的"权重" 🧠

只靠单字概率远远不够——同样打出bank，前文是river还是salary，推荐的后继词完全不同。LeanType 用Ngram 概率表解决这个问题：

• 上下文载体：Kotlin 侧的 NgramContext.kt 记录"前面若干词 + 是否句首"（句首用<S>标记），C++ 侧对应 ngram_context.h。
• 下一个词预测：当你敲完一个词、还没开始下一个词时，dictionary.cpp 中的getPredictions()会遍历词典里以当前上文为前缀的所有 Ngram 条目，通过NgramListenerForPrediction把高概率后继词推给建议条。这就是"空格后立刻冒出一排词"的来源。
• 纠错中的上下文加权：搜索进行到一半时，getNgramProbability()会用前文词 ID 查询组合概率（底层由 multi_bigram_map.h 管理 bigram 映射），让"符合语境"的词排到前面。
• 性能优化：Suggest.kt用容量 50 的LruCache<NgramContext, SuggestionResults>缓存预测结果，切应用/切输入框时自动清空，避免重复查表。

最终打分：精确匹配加成与错误惩罚如何平衡 ⚖️

搜索结束后的输出与最终分计算在 suggestions_output_utils.cpp 和 typing_scoring.h。核心公式：

最终分 = 基础分 - 复合距离 / 最大距离

在此基础上做加减分（常量见 scoring_params.h）：

• 精确匹配加成EXACT_MATCH_PROMOTION：你原样打出的词优先保留，避免"好心改坏"；
• 完美匹配加成PERFECT_MATCH_PROMOTION：对零概率词（如缩写Mt）仅在"完美匹配"时提升，防止输入mt被强推成my；
• 大小写/重音/双字母惩罚：CASE_ERROR_PENALTY_FOR_EXACT_MATCH、ACCENT_ERROR_PENALTY_FOR_EXACT_MATCH等，精确匹配但大小写或重音不符时扣分；
• 自动纠正阈值AUTOCORRECT_OUTPUT_THRESHOLD：多词建议置信度足够高时（长度 ≥16），强制自动替换输入。

Kotlin 侧shouldBeAutoCorrected()再结合用户设置的阈值做最后一道把关：建议分足够高且与输入词不同，才会在你空格时静默替换。

个性化词典：它记得你敲过的每个词 ✍️

除了内置词典（assets/dicts/main_en-US.dict等 19 种语言），LeanType 还有用户词典：

• 每次你确认某个词，updateEntriesForWordWithNgramContext()会把"该词 + 当前上文"的频率写回 UserBinaryDictionary；
• 长期不用的词会按遗忘曲线衰减（forgetting_curve_utils.h），让建议始终保持"新鲜"；
• 因此你自创的项目名、人名打几次后，就会稳定出现在建议条前排。

想深入源码？从这里看起 📂

总结

LeanType 的建议引擎本质上是一个**"键盘布局空间模型 × Ngram 语言模型"的联合评分系统**：

1. 用邻近键信息容忍手误，用 Trie + 优先级队列高效搜索候选词；
2. 用空间距离 + 语言距离合成复合距离，精确匹配加成保证"尊重你的输入"；
3. 用 Ngram 上下文预测下一个词，让建议条领先你的手指半拍；
4. 用个性化词典持续学习你的用词习惯，且全程本地运行、零隐私泄露。

理解了这套评分流水线，你也就理解了为什么 LeanType 在弱网甚至完全离线的场景下，依然能给出又快又准的预测输入体验。