Campus Event Calendar

Event Entry

What and Who

Faster Approximate String Matching: Now with up to 500 Errors

Philip Wellnitz
Max-Planck-Institut für Informatik - D1
Joint Lecture Series
AG 1, AG 2, AG 3, INET, AG 4, AG 5, D6, SWS, RG1, MMCI  
Public Audience

Date, Time and Location

Wednesday, 5 April 2023
60 Minutes
E1 5


String matching algorithms are everywhere. You use them every day,
perhaps even without noticing. Whenever your mail client filters out
spam, whenever your spell checker flags a spelling mistake, whenever
your search engine of choice presents you with results it deems useful,
to list just some examples. For many applications, we need more than
finding exact occurrences of a pattern string in a text. Hence, in this
talk, I consider the classical problem of finding parts of a text that
are close to a given pattern string.

In particular, I consider the problem of finding all parts of a given
text that can be transformed to a given pattern string by inserting,
deleting, or substituting at most k characters—the Approximate String
Matching problem. The first algorithms for this problem were developed
in the 1970s, some of them are relevant even today. After a long line of
research, around the year 2000, the progress in obtaining faster
algorithms for Approximate String Matching came to a halt—even though
the interest did not fade.

In a recent series of papers, I and coauthors improved the more than
20-year-old state-of-the-art algorithms. In this talk, I highlight the
new tools and techniques that we developed for Approximate String
Matching. Further, I give an overview of additional applications of our
techniques to settings where text and pattern are given in a compressed
setting or where we allow text and pattern to change dynamically.


Jennifer Müller
+49 681 9325 2900
--email hidden

Virtual Meeting Details

997 1565 5535
passcode not visible
logged in users only

Jennifer Müller, 03/08/2023 09:14 -- Created document.