The Library
Pattern matching in pseudo real-time
Tools
Clifford, Raphaël and Sach, Ben (2011) Pattern matching in pseudo real-time. Journal of Discrete Algorithms, Vol.9 (No.1). pp. 67-81. doi:10.1016/j.jda.2010.09.005 ISSN 1570-8667.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.jda.2010.09.005
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, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | Journal of Discrete Algorithms | ||||
Publisher: | Elsevier BV | ||||
ISSN: | 1570-8667 | ||||
Official Date: | March 2011 | ||||
Dates: |
|
||||
Volume: | Vol.9 | ||||
Number: | No.1 | ||||
Page Range: | pp. 67-81 | ||||
DOI: | 10.1016/j.jda.2010.09.005 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |