知识卡片
记忆化动态规划削减重复搜索
分词若递归枚举所有切分会重复求解相同后缀;缓存每个子串的最佳结果后,只需逐个子串计算并比较有限长度的首词候选,复杂度可从指数级降到多项式级。概率乘积改用对数加法还能避免数值下溢。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第14章 自然语言语料库数据 · 查看原书依据
没有装饰器memo,对一个包含了n个字符的文本段的调用会导致对该段的2n次递归调用;有了memo,它就只执行n次调用——memo使得调用变成一个高效的动态编程算法。
参考来源
- 位置:《数据之美》第14章《自然语言语料库数据》(源文件:../程序之美系列套装(6册)团队之美、项目管理之美、架构之美、数据之美、测试之美、安全之美/_epub-src/OEBPS/Text/part0393.xhtml)
- 结论依据:原文直接比较无缓存与记忆化递归的调用次数,并给出带词长上限的复杂度;后文指出长序列概率连乘会下溢,因此改用对数求和。
- 原始内容:没有装饰器memo,对一个包含了n个字符的文本段的调用会导致对该段的2n次递归调用;有了memo,它就只执行n次调用——memo使得调用变成一个高效的动态编程算法。