A practical comparison of edit distance approximation algorithms.
Hiroyuki HanadaAtsuyoshi NakamuraMineichi KudoPublished in: GrC (2011)
Keyphrases
- approximation algorithms
- edit distance
- longest common subsequence
- edit operations
- np hard
- special case
- minimum cost
- vertex cover
- worst case
- graph matching
- string edit distance
- approximate string matching
- string matching
- similarity measure
- levenshtein distance
- graph edit distance
- distance function
- approximation ratio
- constant factor
- tree structured data
- string similarity
- dynamic programming
- tree edit distance
- triangle inequality
- dynamic time warping
- distance measure
- tabu search
- scheduling problem
- query processing