中国免费毛片片名检索怎样计算编辑距离

适用范围与例子性质

本文仅讨论非露骨的目录检索方法。星河夜、星河雨、星夜、星河长夜、河星夜均为本站原创虚构字串，不指向真实影片。本题每个所示汉字按一个字符处理，三个允许操作都计1步；不加入交换操作、不作繁简或Unicode规范化，也不声称任何搜索平台采用这条规则。

把“只差一点”改成可复算的规则

NIST算法与数据结构词典把Levenshtein距离定义为插入、删除、替换的最少次数。本题仅使用这个定义，不实现其完整动态规划程序，也不把所有近似字符串算法都称作同一种距离。

• 先写清比较单位与允许操作。本例是普通汉字短串，便于手算；若换成组合字符、表情序列或整词，单位与预处理必须另外定义，不能把本题次数直接当作各种文本处理库都会返回的结果。

三种一步变化分别怎样写

从“星河夜”到“星河雨”，将末字夜替换成雨，1步完成；从“星河夜”到“星夜”，删除中间的河，1步完成；到“星河长夜”，在河与夜之间插入长，也是1步。三种变化不同，但按本题等成本规则次数相同。

• 每对输入输出都不相同，因此距离不可能为0；又各有一条1步路径，所以最少次数就是1。不要只列一条三步改法就把距离写成3，因为距离要取所有允许路径中最少的次数。

相邻换位在本规则里不是一个动作

从“星河夜”到“河星夜”，可以把首字星替换为河，再把第二字河替换为星，共2步。也可先删去星，再插到河之后，同样2步。这里两条可行路径说明距离不大于2。

• 为什么不能1步？两串同长，单次插入或删除会改变长度；单次替换只能改一个位置，而首两位置均不同。因此本题距离恰为2。如果另一个算法允许相邻交换作为1步，它采用了不同规则，不能拿那个结果说本题算错。

别把编辑距离退化成逐位置计错

“星河夜”删掉河后成为“星夜”。若只把第二个位置河与夜判错，再把末尾夜判多余，可能记成2处；但允许删除的规则存在1步路径。插删会改变后续对齐方式，逐位置比对不是本题的方法。

• 手算时写出中间串能暴露错误。原串、目标串、操作、步数分别列出，不把“感觉像错别字”当成计算。遇到更长文本可以使用明确实现并验证的小程序，但输出仍应带上所用规则，而非只有一个神秘相似度。

阈值改变候选范围，不改变距离本身

本例设检索候选阈值为距离不超过1，则前三个目标入选，“河星夜”不入选；阈值改为2时四个都进入。改变的是允许范围，各对字串原来的1或2并没有变化。阈值0只保留完全相同的输入串。

• 更宽范围可能加入更多不同名称，更窄范围也可能漏掉差异较大的异名。这些是筛选结果，不是证明某条记录错误。相同中文题名可能指不同作品，同一作品的另一译名又可能距离很大，后续身份判断仍需本站已有原名、主创与版本资料。

保留原名，输出一张候选计算单

本题可写：“输入星河夜；操作为单字插删换；阈值1；星河雨、星夜、星河长夜各1步，列候选；河星夜2步，不在本轮候选。”同时保存最短路径说明，不把计算后的目标写回覆盖原记录。

• 本页增加的是如何复算字符串距离及阈值，不重复异名归并练习，也不把NFKC转换当作相似匹配。若真实检索服务没有公开使用规则，只报告自己提交了什么及查到什么，不能依据搜索结果猜内部算法。

把方法变成行动

1. 保留输入与目标原串，明确字符单位和单步插删换规则。
2. 给每对短串找可行最短路径，并用长度或不同位置排除更少步数。
3. 按公开阈值形成候选集合，不把阈值变化当距离变化。
4. 把候选交给身份字段核查，保留原记录与计算规则，不自动归并。

延伸阅读与支持范围

以下链接提供相关领域资料。本站的问题拆解、解释和练习为编辑设计，不表示外部机构认可本站全部内容。

关于这个问题的问答

对应学习卡片

继续阅读