Online Approximate Matching with Non-local Distances

Raphaël Clifford, Benjamin Sach

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

2 Citations (Scopus)

Abstract

A black box method was recently given that solves the problem of online approximate matching for a class of problems whose distance functions can be classified as being local. A distance function is said to be local if for a pattern P of length m and any substring T [i, i + m − 1] of a text T , the distance between P and T [i, i + m − 1] is equal to Σ_j ∆(P [j], T [i + j − 1]), where ∆ is any distance function between individual characters. We extend this line of work by showing how to tackle online approximate matching when the distance function is non-local. We give solutions which are applicable to a wide variety of matching problems including function and parameterised matching, swap matching, swap-mismatch, k-difference, k-difference with transpositions, overlap matching, edit distance/LCS, flipped bit, faulty bit and L1 and L2 rearrangement distances. The resulting unamortised online algorithms bound the worst case running time per input character to within a log factor of their comparable offline counterpart.
Translated title of the contributionOnline Approximate Matching with Non-local Distances
Original languageEnglish
Title of host publicationProceedings of the 20th Annual Symposium on Combinatorial Pattern Matching (CPM)
PublisherSpringer Berlin Heidelberg
Pages142 - 153
Edition-
Publication statusPublished - 2009

Bibliographical note

Conference Proceedings/Title of Journal: Proceedings of the 20th Annual Symposium on Combinatorial Pattern Matching (CPM)
Other identifier: 2001009

Cite this