2013/01/04 by Stefan Gerdjikov, Gerdjikov, Stefan, Stoyan Mihov +5
Computer Science · #Algorithms and Data Compression #Computation and Language (cs.CL) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Natural Language Processing Techniques
paper · pdf · doi:10.48550/arxiv.1301.0722
openalex publication_date 2013/01/04 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28
We present a new efficient method for approximate search in electronic\nlexica. Given an input string (the pattern) and a similarity threshold, the\nalgorithm retrieves all entries of the lexicon that are sufficiently similar to\nthe pattern. Search is organized in subsearches that always start with an exact\npartial match where a substring of the input pattern is aligned with a\nsubstring of a lexicon word. Afterwards this partial match is extended stepwise\nto larger substrings. For aligning further parts of the pattern with\ncorresponding parts of lexicon entries, more errors are tolerated at each\nsubsequent step. For supporting this alignment order, which may start at any\npart of the pattern, the lexicon is represented as a structure that enables\nimmediate access to any substring of a lexicon word and permits the extension\nof such substrings in both directions. Experimental evaluations of the\napproximate search procedure are given that show significant efficiency\nimprovements compared to existing techniques. Since the technique can be used\nfor large error bounds it offers interesting possibilities for approximate\nsearch in special collections of "long" strings, such as phrases, sentences, or\nbook ti\n