2026-07-22T07:03:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20124 2024-06-18T13:20:58Z ddc:004 open_access

When Is the Normalized Edit Distance over Non-Uniform Weights a Metric? Fisman, Dana Tzarfati, Ilay Normalized Edit Distance Non-uniform Weights Triangle Inequality Metric The well known Normalized Edit Distance (ned) [Marzal and Vidal 1993] is known to disobey the triangle inequality on contrived weight functions, while in practice it often exhibits a triangular behavior. Let d be a weight function on basic edit operations, and let ned_{d} be the resulting normalized edit distance. The question what criteria should d satisfy for ned_{d} to be a metric is long standing. It was recently shown that when d is the uniform weight function (all operations cost 1 except for no-op which costs 0) then ned_{d} is a metric. The question regarding non-uniform weights remained open. In this paper we answer this question by providing a necessary and sufficient condition on d under which ned_{d} is a metric. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dana Fisman and Ilay Tzarfati 2024 Is Part Of LIPIcs, Volume 296, 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2024.14 urn:nbn:de:0030-drops-201247 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2024.14 eng https://creativecommons.org/licenses/by/4.0/legalcode