A guided tour to approximate string matching

By Gonzalo Navarro. CSUR, 2001

2,935 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Hardware and Architecture, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/e001232a2876989f52a7b4ac12bd9ed550d41240

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Hardware and Architecture

In Molecular Biology

Citations in the corpus

Supervised Sequence Labelling with Recurrent Neural Networks (2012, background): “ED(p,q) can be calculated in O(|p||q|) time (Navarro, 2001).”
Mining email social networks (2006, methodology): “Name Similarity: We use a scoring algorithm based on the Levenshtein edit distance [5, 13, 17] between the full names, and the first and last names separately.”
#thyghgapp: Instagram Content Moderation and Lexical Variation in Pro-Eating Disorder Communities (2016, background): “insertions, deletions, or substitutions) required to change one word into the other [30].”
Segmental Spatiotemporal CNNs for Fine-Grained Action Segmentation (2016, methodology): “This score is computed using the Levenshtein distance which is a function of segment insertions, deletions, and substitutions [42].”
Automatically Learning Semantic Features for Defect Prediction (2016, methodology): “To detect and eliminate mislabeling data, and help DBN learn common knowledge between the semantic information of buggy and clean ﬁles, we adopt the edit distance similarity computation algorithm [43] to deﬁne the distances between instances.”
A taxonomy of privacy-preserving record linkage techniques (2013, methodology): “The Levenshtein edit-distance [47] is a commonly used comparison method for approximate string and sequence matching.”
Interactive deduplication using active learning (2002, background): “For example, [23, 11] show how an inverted index on the NGrams of a text field can used to lower bound the edit-distance function.”
Near neighbor searching with K nearest references (2015, background): “Both measures can be computed in time OðK(2)Þ and are explained in depth in many books and surveys [37].”
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false) (2014, methodology): “ves the sum. As a result, 1There is a rather large body of work devoted to edit distance algorithms and we will not attempt to list all relevant works here. Instead, we refer the reader to the survey [Nav01] for a detailed overview of known exact and probabilistic algorithms, and to the recent paper”
A survey of sequence alignment algorithms for next-generation sequencing (2010, background): “[44] for a more comprehensive review in a wider scope.”
Understanding Plagiarism Linguistic Patterns, Textual Features, and Detection Methods (2012, background): “are [139], [140] 1) Insertion (s, a): inserting letter a into string s; 2) Deletion (a, s): deleting letter a from string s; 3) Substitution or replacement (a, b): substituting letter a by b;”
Neural Fuzzy Repair: Integrating Fuzzy Matches into Neural Machine Translation (2019, methodology): “, 2018) or other approximate string matching methods (Koehn and Senellart, 2010b; Navarro, 2001).”
Duplicate Record Detection: A Survey (2007, methodology): “The basic dynamic programming algorithm [29] for computing the edit distance between two strings takes O ðj (cid:2) 1 j (cid:2) j (cid:2) 2 jÞ time for two strings of length j (cid:2) 1 j and j (cid:2) 2 j , respectively.”
Substructure similarity search in graph databases (2005, methodology): “[14] G. Navarro.”
Software Vulnerability Detection Using Deep Neural Networks: A Survey (2020, methodology): “In particular, the authors applied a distance similarity computation algorithm [72] to remove noise from their data.”
Word Embedding based Edit Distance (2018, methodology): “Edit distance is a widely used measure for text similarity calculation (Navarro, 2001, Jurafsky and Martin, 2009).”
(Male, Bachelor) and (Female, Ph.D) have different connotations: Parallelly Annotated Stylistic Language Dataset with Multiple Personas (2019, background): “• W ORD D IST R ETRIEVE : retrieves a training source-target pair that has the same target style as the test pair and is closest to the test source in terms of word edit distance (Navarro, 2001).”