Pattern matching with address errors: Rearrangement distances

Amihood Amir; Yonatan Aumann; Gary Benson; Avivit Levy; Ohad Lipsky; Ely Porat; Steven Skiena; Uzi Vishne

doi:10.1145/1109557.1109692

Pattern matching with address errors: Rearrangement distances

Amihood Amir
, Yonatan Aumann
, Gary Benson
, Avivit Levy
, Ohad Lipsky
, Ely Porat
, Steven Skiena
, Uzi Vishne

Computer Science

Bar-Ilan University
Georgia Institute of Technology
Boston University

Research output: Contribution to conference › Paper › peer-review

34 Scopus citations

Abstract

Historically, approximate pattern matching has mainly focused at coping with errors in the data, while the order of the text/pattern was assumed to be more or less correct. In this paper we consider a class of pattern matching problems where the content is assumed to be correct, while the locations may have shifted/changed. We formally define a broad class of problems of this type, capturing situations in which the pattern is obtained from the text by a sequence of rearrangements. We consider several natural rearrangement schemes, including the analogues of the ℓ ₁ and ℓ ₂ distances, as well as two distances based on interchanges. For these, we present efficient algorithms to solve the resulting string matching problems.

Original language	English
Pages	1221-1229
Number of pages	9
DOIs	https://doi.org/10.1145/1109557.1109692
State	Published - 2006
Event	Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States Duration: Jan 22 2006 → Jan 24 2006

Conference

Conference	Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/Territory	United States
City	Miami, FL
Period	01/22/06 → 01/24/06

Access to Document

10.1145/1109557.1109692

Cite this

@conference{eef6d603293c4172b1c0b222cabd079d,

title = "Pattern matching with address errors: Rearrangement distances",

abstract = "Historically, approximate pattern matching has mainly focused at coping with errors in the data, while the order of the text/pattern was assumed to be more or less correct. In this paper we consider a class of pattern matching problems where the content is assumed to be correct, while the locations may have shifted/changed. We formally define a broad class of problems of this type, capturing situations in which the pattern is obtained from the text by a sequence of rearrangements. We consider several natural rearrangement schemes, including the analogues of the ℓ 1 and ℓ 2 distances, as well as two distances based on interchanges. For these, we present efficient algorithms to solve the resulting string matching problems.",

author = "Amihood Amir and Yonatan Aumann and Gary Benson and Avivit Levy and Ohad Lipsky and Ely Porat and Steven Skiena and Uzi Vishne",

year = "2006",

doi = "10.1145/1109557.1109692",

language = "English",

pages = "1221--1229",

note = "Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 22-01-2006 Through 24-01-2006",

}

TY - CONF

T1 - Pattern matching with address errors

T2 - Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms

AU - Amir, Amihood

AU - Aumann, Yonatan

AU - Benson, Gary

AU - Levy, Avivit

AU - Lipsky, Ohad

AU - Porat, Ely

AU - Skiena, Steven

AU - Vishne, Uzi

PY - 2006

Y1 - 2006

N2 - Historically, approximate pattern matching has mainly focused at coping with errors in the data, while the order of the text/pattern was assumed to be more or less correct. In this paper we consider a class of pattern matching problems where the content is assumed to be correct, while the locations may have shifted/changed. We formally define a broad class of problems of this type, capturing situations in which the pattern is obtained from the text by a sequence of rearrangements. We consider several natural rearrangement schemes, including the analogues of the ℓ 1 and ℓ 2 distances, as well as two distances based on interchanges. For these, we present efficient algorithms to solve the resulting string matching problems.

AB - Historically, approximate pattern matching has mainly focused at coping with errors in the data, while the order of the text/pattern was assumed to be more or less correct. In this paper we consider a class of pattern matching problems where the content is assumed to be correct, while the locations may have shifted/changed. We formally define a broad class of problems of this type, capturing situations in which the pattern is obtained from the text by a sequence of rearrangements. We consider several natural rearrangement schemes, including the analogues of the ℓ 1 and ℓ 2 distances, as well as two distances based on interchanges. For these, we present efficient algorithms to solve the resulting string matching problems.

UR - https://www.scopus.com/pages/publications/33244468606

U2 - 10.1145/1109557.1109692

DO - 10.1145/1109557.1109692

M3 - Paper

AN - SCOPUS:33244468606

SP - 1221

EP - 1229

Y2 - 22 January 2006 through 24 January 2006

ER -

Pattern matching with address errors: Rearrangement distances

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this