Context-Dependent String Matching

Alan A. Bertossi, Elena Lodi, Fabrizio Luccio and Linda Pagli
Additional contact information
Alan A. Bertossi: Università di Pisa, Dipartimento di Informatica
Elena Lodi: Università di Pisa, Dipartimento di Informatica
Fabrizio Luccio: Università di Pisa, Dipartimento di Informatica
Linda Pagli: Università di Salerno, Dipartimento di Informatica e Applicazioni

A chapter in Sequences, 1990, pp 25-40 from Springer

Abstract: Abstract The approximate string matching problem consists of finding all the occurrences of a pattern P of length m in a text T of length n, m≪n, where at most k differences are allowed between P and each of its occurrences in T. Various types of differences have been studied in the literature. We introduce here the concept of context-dependent errors, where the differences between P and T depend on errors in T that are functions of the context of P and/or T, and develop sequential and parallel algorithms for some relevant sets of weighted errors. In particular, we allow: context-dependent mismatches, extra and missing characters (Problem I); the same errors plus transpositions of two consecutive characters (Problem II); and a more general choice of errors (Problem III). A set of theoretical results allows to solve Problems I and II with O(kn) time sequential algorithms, and O(k + log m) parallel time on a PRAM model with max{n+k+l, m2{ processors. Problem III is instead solved in O(mn) sequential time, and O(m+log n) parallel time with n+1 processors on a feasible bounded degree network.

Keywords: String matching algorithms; Approximate string matching; Context-dependent errors; Text-editing (search for similar items in EconPapers)
Date: 1990
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4612-3352-7_2

Ordering information: This item can be ordered from
http://www.springer.com/9781461233527

DOI: 10.1007/978-1-4612-3352-7_2

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().