Clifford, Raphaël and Sach, Ben. (2011) Pattern matching in pseudo real-time. Journal of Discrete Algorithms, Vol.9 (No.1). pp. 67-81. ISSN 1570-8667

Full text not available from this repository.

Abstract

It has recently been shown how to construct online, non-amortised approximate pattern matching algorithms for a class of problems whose distance functions can be classified as being local. Informally, 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] can be expressed as @?"j@D(P[j],T[i+j]), where @D is any distance function between individual characters. We show in this work how to tackle online approximate matching when the distance function is non-local. We give new 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 and L"1 and L"2 rearrangement distances. The resulting online algorithms bound the worst case running time per input character to within a log factor of their comparable offline counterpart.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Computer Science
Journal or Publication Title:	Journal of Discrete Algorithms
Publisher:	Elsevier BV
ISSN:	1570-8667
Date:	March 2011
Volume:	Vol.9
Number:	No.1
Page Range:	pp. 67-81
Identification Number:	10.1016/j.jda.2010.09.005
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
URI:	http://wrap.warwick.ac.uk/id/eprint/42402

Request changes to a record

Actions (login required)

View Item