最大正向匹配分词与字典树实现
哪些公司问过
答案要点
- 先求词典最长词长 L,从当前位置取最长子串查词典,失败则右侧逐字缩短
- 缩到单字仍未匹配则按单字切分兜底;切出后指针前移词长
- 字典树:从当前位置逐字下行,记录最后一个词尾节点即最长匹配
- 字典树节点存子节点映射与词尾标记,每个位置最多 L 步
- 局限:局部最长易产生歧义,可结合逆向最大匹配、双向匹配或统计模型
易错点
- 不设最长词长,从剩余整句开始尝试,效率很低
- 没有单字兜底,遇到未登录词死循环
- 字典树只匹配到第一个词尾就停止,得不到最长匹配
面试官常见追问
- 逆向最大匹配和双向最大匹配是什么?
- 字典树还能做什么?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。