我正在寻找多维字符串的 Levenshtein 距离（编辑距离）的扩展。我不确定是否有正式的多维定义，但这就是我所说的：
一维字符串：是常规字符串
二维字符串：类似于一维字符串的列表，例如
dfdsfdsfdsf
dsffgdfdgfdsdaf
dsfdsf
fdgfdgfdg
ND 字符串：是 (N-1)-D 个字符串的列表
如何计算此类多维字符串之间的 Levenshtein 距离？
问问题
1123 次
1 回答
5
编辑距离基于将一个字符串转换为另一个字符串的最小成本操作序列。如果这些操作代表罕见的错误，那么该距离是对一个字符串被损坏为另一个字符串的概率的粗略测量。
要找到二维变体，您必须决定允许哪些类型的操作，这取决于您为什么要解决这个问题。如果一个列表中的每个字符串都映射到另一个列表中的相应字符串，那么您可能只需要结果对中编辑距离的总和。如果根本没有对应关系，您可能会计算出所有 n * m 对字符串的编辑距离，然后找到将第一个列表中的一个字符串与第二个列表中的一个字符串相关联的最小成本匹配，并对匹配进行评分与匹配的字符串对的编辑距离之和。如果损坏过程插入和删除整个字符串，以及在字符串中插入和删除字符，
于 2013-09-14T04:48:52.363 回答