2001/03/01 by Gonzalo Navarro · 4 citations
Computer Science · Biochemistry, Genetics and Molecular Biology · Mathematics · #Algorithms and Data Compression #Network Packet Processing and Optimization #DNA and Biological Computing #Computer science #Focus (optics) #Relevance (law) #String searching algorithm #String (physics) #Matching (statistics) #Theoretical computer science #Current (fluid) #Edit distance #Data science #Machine learning #Artificial intelligence #Pattern matching #Information retrieval #Mathematics
paper · doi:10.1145/375360.375365
openalex publication_date 2001/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/03
We survey the current techniques to cope with the problem of string matching that allows errors. This is becoming a more and more relevant issue for many fast growing areas such as information retrieval and computational biology. We focus on online searching and mostly on edit distance, explaining the problem and its relevance, its statistical behavior, its history and current developments, and the central ideas of the algorithms and their complexities. We present a number of experiments to compare the performance of the different algorithms and show which are the best choices. We conclude with some directions for future work and open problems.