On Practical Accuracy of Edit Distance Approximation Algorithms.
Hiroyuki HanadaMineichi KudoAtsuyoshi NakamuraPublished in: CoRR (2017)
Keyphrases
- approximation algorithms
- edit distance
- longest common subsequence
- np hard
- vertex cover
- special case
- worst case
- minimum cost
- similarity measure
- edit operations
- string similarity
- graph edit distance
- string matching
- distance measure
- levenshtein distance
- graph matching
- approximation ratio
- string edit distance
- approximate string matching
- dynamic time warping
- tree structured data
- approximate matching
- partial order
- lower bound
- computational complexity
- training data