知识卡片

普通读书笔记卡 · 6256.d

距离大小不同于计算成本

理解等级:中级

字符串编辑距离的结果可能很小,但求结果仍需处理许多候选状态。书内讨论长度M和N的常见计算过程约O(MN),这是算法工作量,不是编辑距离值;放入n个名称的全体两两比较时,还要结合候选对数估算总体成本。不要用返回1就推断计算只做一步。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      M×N次操作。换句话说,计算编辑距离是一个计算复杂度很高的操作,因此针对一般的数据需要巧妙的使用该方法。 n元文法相似度 n元文法是一种简洁表达来自文本的连续n个符号的每一种排列的可能性,也提供了计算搭配词所需的基本数据结构。n元文法相似度有许多种变形,但是我们考虑最直接的方式:计算2个字符串中所有词的所有可能二元文法,并通过计算字符串间相同的二元文法数来对

    参考来源

    - 位置:《社交网站的数据挖掘与分析(原书第2版)》第3章《3.3.3 测量相似度》(spine79;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part0068.html;u050-ch03-022)。 - 结论依据:原文在“M×N次操作”附近的定义、例子或代码支撑本卡核心说明:字符串编辑距离的结果可能很小,但求结果仍需处理许多候选状态。边界按已读前提解释;示例未执行。 - 原始内容:M×N次操作。换句话说,计算编辑距离是一个计算复杂度很高的操作,因此针对一般的数据需要巧妙的使用该方法。 n元文法相似度 n元文法是一种简洁表达来自文本的连续n个符号的每一种排列的可能性,也提供了计算搭配词所需的基本数据结构。n元文法相似度有许多种变形,但是我们考虑最直接的方式:计算2个字符串中所有词的所有可能二元文法,并通过计算字符串间相同的二元文法数来对