Simple and Efficient Algorithm for Approximate Dictionary Matching

Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 851–859, Beijing, August 2010 Simple and Efficient Algorithm for Approximate Dictionary Matching Naoaki Okazaki University of Tokyo okazaki@is.s.u-tokyo.ac.jp Jun’ichi Tsujii University of Tokyo University of Manchester National Centre for Text Mining tsujii@is.s.u-tokyo.ac.jp Abstract This paper presents a simple and effi- cient algorithm for approximate dictio- nary matching designed for similarity measures such as cosine, Dice, Jaccard, and overlap coefficients. We propose this algorithm, called CPMerge, for the τ- overlap join of inverted lists. First we show that this task is solvable exactly by a τ-overlap join. Given inverted lists re- trieved for a query, the algorithm collects fewer candidate strings and prunes un- likely candidates to efficiently find strings that satisfy the constraint of the τ-overlap join. We conducted experiments of ap- proximate dictionary matching on three large-scale datasets that include person names, biomedical names, and general English words. The algorithm exhib- ited scalable performance on the datasets. For example, it retrieved strings in 1.1 ms from the string collection of Google Web1T unigrams (with cosine similarity and threshold 0.7). 1 Introduction Languages are sufficiently flexible to be able to express the same meaning through different dic- tion. At the same time, inconsistency of surface expressions has persisted as a serious problem in natural language processing. For example, in the biomedical domain, cardiovascular disorder can be described using various expressions: cardio- vascular diseases, cardiovascular system disor- der, and disorder of the cardiovascular system. It is a nontrivial task to find the entry from these sur- face expressions appearing in text. This paper addresses approximate dictionary matching, which consists of finding all strings in a string collection V such that they have similar- ity that is no smaller than a threshold α with a query string x. This task has a broad range of ap- plications, including spelling correction, flexible dictionary look-up, record linkage, and duplicate detection (Henzinger, 2006; Manku et al., 2007). Formally, the task obtains a subset Yx,α ⊆ V , Yx,α = {y ∈ V �� sim(x, y) ≥ α}, (1) where sim(x, y) presents the similarity between x and y. A na¨ıve solution to this task is to com- pute similarity values |V | times, i.e., between x and every string y ∈ V . However, this solution is impractical when the number of strings |V | is huge (e.g., more than one million). In this paper, we present a simple and effi- cient algorithm for approximate dictionary match- ing designed for similarity measures such as co- sine, Dice, Jaccard, and overlap coefficients. Our main contributions are twofold. 1. We show that the problem of approximate dictionary matching is solved exactly by a τ-overlap join (Sarawagi and Kirpal, 2004) of inverted lists. Then we present CPMerge, which is a simple and efficient algorithm for the τ-overlap join. In addition, the algorithm is easily implemented. 2. We demonstrate the efficiency of the al- gorithm on three large-scale datasets with person names, biomedical concept names, 851 and …

Content truncated to 500 words