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
|
| Խորագրեր: | |
| Առցանց հասանելիություն: | 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