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 \(\mathcal {K}\) -bounded versions of the problems are considered as well.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Burst Edit Distance

  • Itai Boneh,
  • Shay Golan,
  • Avivit Levy,
  • Ely Porat,
  • B. Riva Shalom

摘要

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 \(\mathcal {K}\) -bounded versions of the problems are considered as well.