{'fraction_non_alphanumeric': 0.027336733960773043, 'fraction_numerical': 0.008729075364609526, 'mean_word_length': 4.6331444759206795, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Fast and Accurate Method for Approximate String Search

This paper proposes a new method for approximate string search, specifically candidate generation in spelling error correction, which is a task as follows. Given a misspelled word, the system finds words in a dictionary, which are most "similar" to the misspelled word. The paper proposes a probabilistic approach to the task, which is both accurate and efficient. The approach includes the use of a log linear model, a method for training the model, and an algorithm for finding the top k candidates. The log linear model is defined as a conditional probability distribution of a corrected word and a rule set for the correction conditioned on the misspelled word. The learning method employs the criterion in candidate generation as loss function. The retrieval algorithm is efficient and is guaranteed to find the optimal k candidates. Experimental results on large scale data show that the proposed approach improves upon existing methods in terms of accuracy in different settings.


Introduction
This paper addresses the following problem, referred to as approximate string search. Given a query string, a dictionary of strings (vocabulary), and a set of operators, the system returns the top k strings in the dictionary that can be transformed from the query string by applying several operators in the operator set. Here each operator is a rule that can replace a substring in the query string with another substring. The top k results are defined in * Contribution during internship at Microsoft Research Asia.
terms of an evaluation measure employed in a specific application. The requirement is that the task must be conducted very efficiently.
Approximate string search is useful in many applications including spelling error correction, similar terminology retrieval, duplicate detection, etc.
Although certain progress has been made for addressing the problem, further investigation on the task is still necessary, particularly from the viewpoint of enhancing both accuracy and efficiency.
Without loss of generality, in this paper we address candidate generation in spelling error correction. Candidate generation is to find the most possible corrections of a misspelled word. In such a problem, strings are words, and the operators represent insertion, deletion, and substitution of characters with or without surrounding characters, for example, "a"→"e" and "lly"→"ly". Note that candidate generation is concerned with a single word; after candidate generation, the words surrounding it in the text can be further leveraged to make the final candidate selection, e.g., Li et al. (2006), Golding and Roth (1999).
In spelling error correction, Brill and Moore (2000) proposed employing a generative model for candidate generation and a hierarchy of trie structures for fast candidate retrieval. Our approach is a discriminative approach and is aimed at improving Brill and Moore's method. Okazaki et al. (2008) proposed using a logistic regression model for approximate dictionary matching. Their method is also a discriminative approach, but it is largely different from our approach in the following points. It formalizes the problem as binary classification and assumes that there is only one rule applicable each time in candidate generation. Efficiency is also not a major concern for them, because it is for offline text mining.
There are two fundamental problems in research on approximate string search: (1) how to build a model that can archive both high accuracy and efficiency, and (2) how to develop a data structure and algorithm that can facilitate efficient retrieval of the top k candidates.
In this paper, we propose a probabilistic approach to the task. Our approach is novel and unique in the following aspects. It employs (a) a log-linear (discriminative) model for candidate generation, (b) an effective algorithm for model learning, and (c) an efficient algorithm for candidate retrieval.
The log linear model is defined as a conditional probability distribution of a corrected word and a rule set for the correction given the misspelled word. The learning method employs, in the training process, a criterion that represents the goal of making both accurate and efficient prediction (candidate generation). As a result, the model is optimally trained toward its objective. The retrieval algorithm uses special data structures and efficiently performs the top k candidates finding. It is guaranteed to find the best k candidates without enumerating all the possible ones.
We empirically evaluated the proposed method in spelling error correction of web search queries. The experimental results have verified that the accuracy of the top candidates given by our method is significantly higher than those given by the baseline methods. Our method is more accurate than the baseline methods in different settings such as large rule sets and large vocabulary sizes. The efficiency of our method is also very high in different experimental settings.

Related Work
Approximate string search has been studied by many researchers. Previous work mainly focused on efficiency rather than model. Usually, it is assumed that the model (similarity distance) is fixed and the goal is to efficiently find all the strings in the collection whose similarity distances are within a threshold. Most existing methods employ n-gram based algo-rithms (Behm et al., 2009;Yang et al., 2008) or filtering algorithms (Mihov and Schulz, 2004;. Instead of finding all the candidates in a fixed range, methods for finding the top k candidates have also been developed. For example, the method by Vernica and Li (2009) utilized n-gram based inverted lists as index structure and a similarity function based on n-gram overlaps and word frequencies. Yang et al. (2010) presented a general framework for top k retrieval based on ngrams. In contrast, our work in this paper aims to learn a ranking function which can achieve both high accuracy and efficiency.
Spelling error correction normally consists of candidate generation and candidate final selection. The former task is an example of approximate string search. Note that candidate generation is only concerned with a single word. For single-word candidate generation, rule-based approach is commonly used. The use of edit distance is a typical example, which exploits operations of character deletion, insertion and substitution. Some methods generate candidates within a fixed range of edit distance or different ranges for strings with different lengths (Li et al., 2006;Whitelaw et al., 2009). Other methods make use of weighted edit distance to enhance the representation power of edit distance (Ristad and Yianilos, 1998;Oncina and Sebban, 2005;McCallum et al., 2005;Ahmad and Kondrak, 2005).
Conventional edit distance does not take in consideration context information. For example, people tend to misspell "c" to "s" or "k" depending on contexts, and a straightforward application of edit distance cannot deal with the problem. To address the challenge, some researchers proposed using a large number of substitution rules containing context information (at character level). For example, Brill and Moore (2000) developed a generative model including contextual substitution rules; and Toutanova and Moore (2002) further improved the model by adding pronunciation factors into the model. Schaback and Li (2007) proposed a multi-level feature-based framework for spelling error correction including a modification of Brill and Moore's model (2000). Okazaki et al. (2008) utilized substring substitution rules and incorporated the rules into a L 1 -regularized logistic regression model. Okazaki et al.'s model is largely different from the model proposed in this paper, although both of them are discriminative models. Their model is a binary classification model and it is assumed that only a single rule is applied in candidate generation.
Since users' behavior of misspelling and correction can be frequently observed in web search log data, it has been proposed to mine spelling-error and correction pairs by using search log data. The mined pairs can be directly used in spelling error correction. Methods of selecting spelling and correction pairs with maximum entropy model  or similarity functions (Islam and Inkpen, 2009;Jones et al., 2006) have been developed. The mined pairs can only be used in candidate generation of high frequency typos, however. In this paper, we work on candidate generation at the character level, which can be applied to spelling error correction for both high and low frequency words.

Model for Candidate Generation
As an example of approximate string search, we consider candidate generation in spelling correction. Suppose that there is a vocabulary V and a misspelled word, the objective of candidate generation is to select the best corrections from the vocabulary V. We care about both accuracy and efficiency of the process. The problem is very challenging when the size of vocabulary is large, because there are a large number of potential candidates to be verified.
In this paper, we propose a probabilistic approach to candidate generation, which can achieve both high accuracy and efficiency, and is particularly powerful when the scale is large.
In our approach, it is assumed that a large number of misspelled words and their best corrections are given as training data. A probabilistic model is then trained by using the training data, which can assign ranking scores to candidates. The best candidates for correction of a misspelled word are thus defined as those candidates having the highest probabilistic scores with respect to the training data and the operators.
Hereafter, we will describe the probabilistic model for candidate generation, as well as training and exploitation of the model.

Model
The operators (rules) represent insertion, deletion, and substitution of characters in a word with or without surrounding context (characters), which are similar to those defined in (Brill and Moore, 2000;Okazaki et al., 2008). An operator is formally represented a rule α → β that replaces a substring α in a misspelled word with β, where α, β ∈ {s|s = t, s =ˆt, or s = t$} and t ∈ Σ * is the set of all possible strings over the alphabet. Obviously, V ⊂ Σ * . We actually derive all the possible rules from the training data using a similar approach to (Brill and Moore, 2000) as shown in Fig. 1. First we conduct the letter alignment based on the minimum edit-distance, and then derive the rules from the alignment. Furthermore we expand the derived rules with surrounding words. Without loss of generality, we only consider using +2, +1, 0, −1, −2 characters as contexts in this paper. If we can apply a set of rules to transform the misspelled word w m to a correct word w c in the vocabulary, then we call the rule set a "transformation" for the word pair w m and w c . Note that for a given word pair, it is likely that there are multiple possible transformations for it. For example, both "n"→"m" and "ni"→"mi" can transform "nicrosoft" to "microsoft".
Without loss of generality, we set the maximum number of rules applicable to a word pair to be a fixed number. As a result, the number of possible transformations for a word pair is finite, and usually limited. This is equivalent to the assumption that the number of spelling errors in a word is small.
Given word pair (w m , w c ), let R(w m , w c ) denote one transformation (a set of rules) that can rewrite w m to w c . We consider that there is a probabilistic mapping between the misspelled word w m and correct word w c plus transformation R(w m , w c ). We define the conditional probability distribution of w c and R(w m , w c ) given w m as the following log linear model: where r or o denotes a rule in rule set R, λ r or λ o denotes a weight, and the normalization is carried over . The log linear model actually uses binary features indicating whether or not a rule is applied.
In general, the weights in Equ.
(1) can be any real numbers. To improve efficiency in retrieval, we further assume that all the weights are non-positive, i.e., ∀λ r ≤ 0. It introduces monotonicity in rule application and implies that applying additional rules cannot lead to generation of better candidates. For example, both "office" and "officer" are correct candidates of "ofice". We view "office" a better candidate (with higher probability) than "officer", as it needs one less rule. The assumption is reasonable because the chance of making more errors should be lower than that of making less errors. Our experimental results have shown that the change in accuracy by making the assumption is negligible, but the gain in efficiency is very large.

Training of Model
Training data is given as a set of pairs The objective of training would be to maximize the conditional probabil- over the training data. This is not a trivial problem, however, because the "true" transformation R * (w i m , w i c ) for each word pair w i m and w i c is not given in the training data. It is often the case that there are multiple transformations applicable, and it is not realistic to assume that such information can be provided by humans or automatically derived. (It is relatively easy to automatically find the pairs w i m and w i c as explained in Section 5.1).
In this paper, we assume that the transformation that actually generates the correction among all the possible transformations is the one that can give the maximum conditional probability; the exactly same criterion is also used for fast prediction. Therefore we have the following objective function where λ denotes the weight parameters and the max is taken over the set of transformations that can transform w i m to w i c . We employ gradient ascent in the optimization in Equ.
(2). At each step, we first find the best transformation for each word pair based on the current parameters λ (t) Next, we calculate the gradients, In this paper, we employ the bounded L-BFGS (Behm et al., 2009) algorithm for the optimization task, which works well even when the number of weights λ is large.

Candidate Generation
In candidate generation, given a misspelled word w m , we find the k candidates from the vocabulary, that can be transformed from w m and have the largest probabilities assigned by the learned model.
We only need to utilize the following ranking function to rank a candidate w c given a misspelled word w m , by taking into account Equs. (1) and (2) rank(w c |w m ) = max For each possible transformation, we simply take summation of the weights of the rules used in the transformation. We then choose the sum as a ranking score, which is equivalent to ranking candidates based on their largest conditional probabilities.

Efficient Retrieval Algorithm
In this section, we introduce how to efficiently perform top k candidate generation. Our retrieval algorithm is guaranteed to find the optimal k candidates with some "pruning" techniques. We first introduce the data structures and then the retrieval algorithm.

Data Structures
We exploit two data structures for candidate generation. One is a trie for storing and matching words in the vocabulary, referred to as vocabulary trie, and the other based on what we call an Aho-Corasick tree (AC tree) (Aho and Corasick, 1975), which is used for storing and applying correction rules, referred to as rule index. The vocabulary trie is the same as that used in existing work and it will be traversed when searching the top k candidates. Our rule index is unique because it indexes all the rules based on an AC tree. The AC tree is a trie with "failure links", on which the Aho-Corasick string matching algorithm can be executed. Aho-Corasick algorithm is a well known dictionary-matching algorithm which can quickly locate all the words in a dictionary within an input string. Time complexity of the algorithm is of linear order in length of input string plus number of matched entries.
We index all the α's in the rules on the AC tree. Each α corresponds to a leaf node, and the β's of the α are stored in an associated list in decreasing order of rule weights λ, as illustrated in Fig. 2. 1 1 One may further improve the index structure by using a trie rather than a ranking list to store βs associated with the same α. However the improvement would not be significant because the number of βs associated with each α is usually very small.

Algorithm
One could employ a naive algorithm that applies all the possible combinations of rules (α's) to the current word w m , verifies whether the resulting words (candidates) are in the vocabulary, uses the function in Equ. (5) to calculate the ranking scores of the candidates, and find the top k candidates. This algorithm is clearly inefficient. Our algorithm first employs the Aho-Corasick algorithm to locate all the applicable α's within the input word w m , from the rule index. The corresponding β's are retrieved as well. Then all the applicable rules are identified and indexed by the applied positions of word w m .
Our algorithm next traverses the vocabulary trie and searches the top k candidates with some pruning techniques. The algorithm starts from the root node of the vocabulary trie. At each step, it has multiple search branches. It tries to match at the next position of w m , or apply a rule at the current position of w m . The following two pruning criteria are employed to significantly accelerate the search process.

1) If the current sum of weights of applied rules
is smaller than the smallest weight in the top k list, the search branch is pruned. This criterion is derived from the non-negative constraint on rule weights λ. It is easy to verify that the sum of weights will not become larger if one continues to search the branch because all the weights are non-positive. 2) If two search branches merge at the same node in the vocabulary trie as well as the same position on w m , the search branches with smaller sum of weights will be pruned. It is based on the dynamic programming technique because we take max in the ranking function in Equ. 5.
It is not difficult to prove that our algorithm is guaranteed to find the best k candidates in terms of the ranking scores, because we only prune those candidates that cannot give better scores than the ones in the current top k list. Due to the limitation of space, we omit the proof of the theorem that if the weights of rules λ are non-positive and the ranking function is defined as in Equ. 5, then the top k candidates obtained with the pruning criteria are the same as the top k candidates obtained without pruning.

Experimental Results
We have experimentally evaluated our approach in spelling error correction of queries in web search. The problem is more challenging than usual due to the following reasons.
(1) The vocabulary of queries in web search is extremely large due to the scale, diversity, and dynamics of the Internet.
(2) Efficiency is critically important, because the response time of top k candidate retrieval for web search must be kept very low. Our approach for candidate generation is in fact motivated by the application.

Word Pair Mining
In web search, a search session is comprised of a sequence of queries from the same user within a time period. It is easy to observe from search session data that there are many spelling errors and their corrections occurring in the same sessions. We employed heuristics to automatically mine training pairs from search session data at a commercial search engine. First, we segmented the query sequence from each user into sessions. If two queries were issued more than 5 minutes apart, then we put a session boundary between them. We used short sessions here because we found that search users usually correct their misspelled queries very quickly after they find the misspellings. Then the following heuristics were employed to identify pairs of misspelled words and their corrections from two consecutive queries within a session: 1) Two queries have the same number of words. 2) There is only one word difference between two queries. 3) For the two distinct words, the word in the first query is considered as misspelled and the second one as its correction.
Finally, we aggregated the identified training pairs across sessions and users and discarded the pairs with low frequencies. Table 1 shows some examples of the mined word pairs.

Experiments on Accuracy
Two representative methods were used as baselines: the generative model proposed by (Brill and Moore, 2000) referred to as generative and the logistic regression model proposed by (Okazaki et al., 2008) Misspelled Correct Misspelled Correct  aacoustic  acoustic  chevorle  chevrolet  liyerature  literature tournemen tournament  shinngle  shingle  newpape  newspaper  finlad  finland  ccomponet component  reteive  retrieve  olimpick  olympic   Table 1: Examples of Word Pairs referred to as logistic. Note that Okazaki et al. (2008)'s model is not particularly for spelling error correction, but it can be employed in the task. When using their method for ranking, we used outputs of the logistic regression model as rank scores. We compared our method with the two baselines in terms of top k accuracy, which is ratio of the true corrections among the top k candidates generated by a method. All the methods shared the same settings: 973,902 words in the vocabulary, 10,597 rules for correction, and up to two rules used in one transformation. We made use of 100,000 word pairs mined from query sessions for training, and 10,000 word pairs for testing.
The experimental results are shown in Fig. 3. We can see that our method always performs the best when compared with the baselines and the improvements are statistically significant (p < 0.01). The logistic method works better than generative, when k is small, but its performance becomes saturated, when k is large. Usually a discriminative model works better than a generative model, and that seems to be what happens with small k's. However, logistic cannot work so well for large k's, because it only allows the use of one rule each time. We observe that there are many word pairs in the data that need to be transformed with multiple rules.
Next, we conducted experiments to investigate how the top k accuracy changes with different sizes of vocabularies, maximum numbers of applicable rules and sizes of rule set for the three methods. The experimental results are shown in Fig. 4, Fig. 5 and Fig. 6.
For the experiment in Fig. 4, we enlarged the vocabulary size from 973,902 (smallVocab) to 2,206,948 (largeVocab) and kept the other settings the same as in the previous experiment. Because more candidates can be generated with a larger vocabulary, the performances of all the methods de- cline. However, the drop of accuracy by our method is much smaller than that by generative, which means our method is more powerful when the vocabulary is large, e.g., for web search. For the experiment in Fig. 5, we changed the maximum number of rules that can be applied to a transformation from 2 to 3. Because logistic can only use one rule at a time, it is not included in this experiment. When there are more applicable rules, more candidates can be generated and thus ranking of them becomes more challenging. The accuracies of both methods drop, but our method is constantly better than generative. Moreover, the decrease in accuracy by our method is clearly less than that by generative. For the experiment in Fig. 6, we enlarged the number of rules from 10,497 (smallRuleNum) to 24,054 (largeRu-leNum). The performance of our method and those of the two baselines did not change so much, and our method still visibly outperform the baselines when more rules are exploited.

Experiments on Efficiency
We have also experimentally evaluated the efficiency of our approach. Because most existing work uses a predefined ranking function, it is not fair to make a comparison with them. Moreover, Okazaki et al.' method does not consider efficiency, and Brill and Moore's method is based a complicated retrieve algorithm which is very hard to implement. Instead of making comparison with the existing methods in terms of efficiency, we evaluated the efficiency of our method by looking at how efficient it becomes with its data structure and pruning technique.  Fig. 7. We can see that the number of matches is not largely affected by the number of rules in the rule index. It implies that the time for searching applicable rules is close to a constant and does not change much with different numbers of rules.
Next, since the running time of our method is proportional to the number of visited nodes on the vocabulary trie, we evaluated the efficiency of our method in terms of number of visited nodes. The result reported here is that when k is 10.
Specifically, we tested how the number of visited nodes changes according to three factors: maximum number of applicable rules in a transformation, vocabulary size and rule set size. The experimental results are shown in Fig. 8, Fig. 9 and Fig. 10 respectively. From Fig. 8, with increasing maximum number of applicable rules in a transformation, number of visited nodes increases first and then stabilizes, especially when the words are long. Note that pruning becomes even more effective because number of visited nodes without pruning grows much faster. It demonstrates that our method is very efficient when compared to the non-pruning method. Admittedly, the efficiency of our method also deteriorates somewhat. This would not cause a noticeable issue in real applications, however. In the previous section, we have seen that using up to two rules in a transformation can bring a very high accuracy. From Fig. 8 and Fig. 9, we can conclude that the numbers of visited nodes are stable and thus the efficiency of our method keeps high with larger vocabulary size and number of rules. It indicates that our pruning strategy is very effective. From all the figures, we can see that our method is always efficient especially when the words are relatively short.

Experiments on Model Constraints
In Section 3.1, we introduce the non-positive constraints on the parameters, i.e., ∀λ r ≤ 0, to enable the pruning technique for efficient top k retrieval. We experimentally verified the impact of the constraints to both the accuracy and efficiency. For ease of reference, we name the model with the non-positive constraints as bounded, and the origi-  Fig. 11 and Fig. 12. All the experiments were conducted based on the typical setting of our experiments: 973,902 words in the vocabulary, 10,597 rules, and up to two rules in one transformation. In Fig. 11, we can see that the difference between bounded and unbounded in terms of accuracy is negligible, and we can draw a conclusion that adding the constraints does not hurt the accuracy. From Fig. 12, it is easy to note that bounded is much faster than unbounded because our pruning strategy can be applied to bounded.

Conclusion
In this paper, we have proposed a new method for approximate string search, including spelling error correction, which is both accurate and efficient. Our method is novel and unique in its model, learning  Figure 12: Efficiency Comparison between Bounded and Unbounded Models algorithm, and retrieval algorithm. Experimental results on a large data set show that our method improves upon existing methods in terms of accuracy, and particularly our method can perform better when the dictionary is large and when there are many rules. Experimental results have also verified the high efficiency of our method. As future work, we plan to add contextual features into the model and apply our method to other data sets in other tasks.