返回主题:深度表示与任务网络

知识卡片

普通读书笔记卡 · 3848.a

记忆化动态规划削减重复搜索

理解等级:中级

分词若递归枚举所有切分会重复求解相同后缀;缓存每个子串的最佳结果后,只需逐个子串计算并比较有限长度的首词候选,复杂度可从指数级降到多项式级。概率乘积改用对数加法还能避免数值下溢。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《数据之美》第14章《自然语言语料库数据》(源文件:../程序之美系列套装(6册)团队之美、项目管理之美、架构之美、数据之美、测试之美、安全之美/_epub-src/OEBPS/Text/part0393.xhtml) - 结论依据:原文直接比较无缓存与记忆化递归的调用次数,并给出带词长上限的复杂度;后文指出长序列概率连乘会下溢,因此改用对数求和。 - 原始内容:没有装饰器memo,对一个包含了n个字符的文本段的调用会导致对该段的2n次递归调用;有了memo,它就只执行n次调用——memo使得调用变成一个高效的动态编程算法。