Fast Approximations to Edit and Dyck Edit Distances
Explore simple, deterministic, and fast approximations to edit distance and Dyck edit distance, including dynamic programming approaches and reductions between the two distance metrics.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Simple, Deterministic, Fast (but Weak) Approximations to Edit Distance and Dyck Edit Distance Michal Kouck Michael Saks Charles University Rutgers University
Edit distance ? a b c z d e f w h i k l m ? a b c d e f g h i j k l m Edit distance ED(?,?): the number of 1) insertions, and that transform ? into ?. 2) deletions
Dyck edit distance ? [ ( ) } [ ] ( ( ) ( ] ) ] Dyck edit distance Dyck(?): the number of 1) insertions, and that make ? well parenthesized. 2) deletions
Edit distance Dyck edit distance Dynamic programming ?(?2) ?(?3) Bringmann, Grandoni, Saha, Vassilevska- Williams 19 ?(?2.824) Lee 02, Abboud, Backurs, Vassilevska- Williams 15 ?? ?2 Backurs, Indyk 15 1 + ? -approximation , Das, Kociumaka, Saha 22 ?(?2) ? 1 -approximation , Andoni, Nosatzki 20 Das, Kociumaka, Saha 22 ?(?1+?) ?(?1.971)
Edit distance to Dyck edit distance ? = [ ?R ? ] ? b e a r [r [a [e [b b] a] r] t] ? b a r t ED ?,? = Dyck(?)
Dyck edit distance to edit distance ? = [ ?R ? ] ? b e a r [r [a [e [b b] a] r] t] ? b a r t ED ?,? = Dyck(?)
Dyck edit distance to edit distance ? ? ? ? ? ? ? [r a] [e [b e] [t r] t] ? ? ? ? ? ED ?,? = Dyck(?)
Dyck edit distance to edit distance Thm [Saha 15]:Randomized linear-time reduction from Dyck edit distance to edit distance ?(log ?)-approximation. Thm [ours]: Deterministic linear-time reduction from Dyck edit distance to edit distance 3 log ?-approximation.
Dyck edit distance ? L L R L R L R R L L R L R L R Dyck edit distance of ? is at most the sum of the edit distance of all the pairs. The sum of the edit distance of all the pairs is at most 3log ?- times the Dyck edit distance of ?.
Dyck edit distance ? L L R L R L R L R Dyck edit distance of ? is at most the sum of the edit distance of all the pairs. The sum of the edit distance of all the pairs is at most 3log ?- times the Dyck edit distance of ?.
Sahas edit distance approximation ? a b c z d e f g h i k l m ? a b c d e f g h i j k l m On a mismatch remove one of the symbols at random. Thm [Saha 15]:?(?)-approximation to edit distance. ? edit distance
Approximating edit distance Thm [Saha 15]:Randomized linear-time ?(?)-approximation to edit distance. Thm [ours]: Deterministic linear-time ?-approximation to edit distance. Remove: 1 mismatch from ?, 3 mismatches from ?, 5 mismatches from ?, 7 mismatches from ?,
Open questions Simple algorithm for ?(1)-approximation of edit distance? ?(1)-approximate reduction from Dyck edit distance to edit distance?
Dyck edit distance ?1 L R L R L R ?2 L L R Dyck edit distance of ? is at most the sum of the edit distance of all the pairs. The sum of the edit distance of all the pairs is at most 3log ?- times the Dyck edit distance of ?.
