知识卡片

普通读书笔记卡 · 3623.k

编辑距离依赖允许操作成本

理解等级:中级

编辑距离在给定操作集与费用下,是把源串变成目标串的最低费用操作序列成本。

本题允许复制、替换、删除、插入、交换相邻字符与末尾清除,各有不同费用;若操作集或费用改变,距离与最优操作序列也会变。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 14 章问题与章末注释(`OEBPS/chapter014.xhtml`,文本字符 [100000, 110000);图 14.12、Art_P482)。 - 结论依据:问题14-5(a) 把编辑距离定义为给定操作费用下的最低变换成本;题设列复制、替换、删除、插入、相邻交换、末尾清除等操作。 - 原始内容:the edit distance from x to y is the cost of the least expensive operation sequence that transforms x to y .