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
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 5 April 2023
12:15
60 Minutes
E1 5
002
Saarbrücken
Abstract
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.
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.
Contact
Jennifer Müller
+49 681 9325 2900
--email hidden
Virtual Meeting Details
Zoom
997 1565 5535
passcode not visible
logged in users only
Jennifer Müller, 03/08/2023 09:14 -- Created document.