论文标题
正常化的编辑距离，均匀操作成本是度量标准
The Normalized Edit Distance with Uniform Operation Costs is a Metric
论文作者
论文摘要
我们证明，当所有编辑操作的成本相同时，[Marzal and Vidal 1993]中提出的标准化编辑距离是一个度量标准。在文献中，这截言了漫长的差距，其中几位作者指出，这种距离在一般情况下不满足三角形的不平等，并且在所有编辑成本均等的统一情况下，它是否满足。当人们认为Marzal's和Vidal的距离不是指标时，我们将该指标与两个标准化指标进行比较，并将其作为文献中的替代品进行了比较，并确定了关键特性，这些属性可以解释为什么原始距离（现在也已知也是一个度量标准）对某些应用更好。我们的检查是从正式验证的角度来看的，但是属性及其意义是以应用不可知论的方式陈述的。
We prove that the normalized edit distance proposed in [Marzal and Vidal 1993] is a metric when the cost of all the edit operations are the same. This closes a long standing gap in the literature where several authors noted that this distance does not satisfy the triangle inequality in the general case, and that it was not known whether it is satisfied in the uniform case where all the edit costs are equal. We compare this metric to two normalized metrics proposed as alternatives in the literature, when people thought that Marzal's and Vidal's distance is not a metric, and identify key properties that explain why the original distance, now known to also be a metric, is better for some applications. Our examination is from a point of view of formal verification, but the properties and their significance are stated in an application agnostic way.
