License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2022.17
URN: urn:nbn:de:0030-drops-161446
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16144/
Go to the corresponding LIPIcs Volume Portal

Fisman, Dana ; Grogin, Joshua ; Margalit, Oded ; Weiss, Gera

The Normalized Edit Distance with Uniform Operation Costs Is a Metric

pdf-format:
LIPIcs-CPM-2022-17.pdf (0.8 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{fisman_et_al:LIPIcs.CPM.2022.17,
  author =	{Fisman, Dana and Grogin, Joshua and Margalit, Oded and Weiss, Gera},
  title =	{{The Normalized Edit Distance with Uniform Operation Costs Is a Metric}},
  booktitle =	{33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-234-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{223},
  editor =	{Bannai, Hideo and Holub, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16144},
  URN =		{urn:nbn:de:0030-drops-161446},
  doi =		{10.4230/LIPIcs.CPM.2022.17},
  annote =	{Keywords: edit distance, normalized distance, triangle inequality, metric}
}

Keywords: edit distance, normalized distance, triangle inequality, metric
Collection: 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)
Issue Date: 2022
Date of publication: 22.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI