Space Efficient Deterministic Approximation of String Measures
We study approximation algorithms for the following three string measures that are widely used in practice: edit distance (ED), longest common subsequence (LCS), and longest increasing sequence (LIS). All three problems can be solved exactly by standard algorithms that run in polynomial time with ro...
Αποθηκεύτηκε σε:
| Κύριοι συγγραφείς: | , , , |
|---|---|
| Μορφή: | Άρθρο |
| Έκδοση: |
2020
|
| Θέματα: | |
| Διαθέσιμο Online: | https://arxiv.org/abs/2002.08498 http://arxiv.org/abs/2002.08498 |
| Ετικέτες: |
Δεν υπάρχουν, Καταχωρήστε ετικέτα πρώτοι!
|
Παρόμοια τεκμήρια: Space Efficient Deterministic Approximation of String Measures
- How Compression and Approximation Affect Efficiency in String Distance Measures
- Space-Efficient Indexes for Uncertain Strings
- Space-Efficient Online Computation of String Net Occurrences
- Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation
- Sensitivity of string compressors and repetitiveness measures
- Sensitivity of Repetitiveness Measures to String Reversal