@inproceedings{381c28e693c143f3be78fb038ffcee71,
title = "Burst Edit Distance",
abstract = "In this paper we define two types of burst edit errors that occur in Text Editing scenarios when the communication speed is unstable within a wireless keyboard usage: (1) A Burst of Errors (BE) involves a sequence of erroneous identical symbols and allows a single edit operation applied to a sequence of identical symbols; (2) A Burst of Operations (BO) involves a sequence of erroneous symbols that are not necessarily identical and allows a single edit operation applied to a sequence of symbols. In both burst types, every burst operation has a penalty, which is a cost function F(k), where k is the burst length. The burst edit distance of two strings S and T is: (1) The minimum cost of a sequence of BE operations that transforms S into T in the bursts of errors variant (EDBE); (2) The minimum cost of a sequence of BO operations that transforms S into T in the bursts of operations variant (EDBO). We describe solutions to both problems for general natural penalty functions families. A conditional lower bound for the EDBE problem is also given. The K-bounded versions of the problems are considered as well.",
keywords = "Burst Errors, Edit Distance, String Similarity",
author = "Itai Boneh and Shay Golan and Avivit Levy and Ely Porat and Shalom, \{B. Riva\}",
note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.; 31st International Symposium on String Processing and Information Retrieval, SPIRE 2024 ; Conference date: 23-09-2024 Through 25-09-2024",
year = "2025",
doi = "10.1007/978-3-031-72200-4\_4",
language = "אנגלית",
isbn = "9783031721991",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "41--56",
editor = "Zsuzsanna Lipt{\'a}k and Edleno Moura and Karina Figueroa and Ricardo Baeza-Yates",
booktitle = "String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Proceedings",
address = "גרמניה",
}