Good parts first - a new algorithm for approximate search in lexica and string databases
Table 6: Search times for Bulgarian lexicon with short strings showing the influence of the length of lexicon entries. Standard Levenshtein distance, search times for three methods. f - Oflazer’s method, fb - the forward-backward method, new - the new method, ideal - the ‘‘ideal method’’.
['[ITALIC] b', 'Levenshtein distance, lexicon of Bulgarian word forms new / ideal', 'Levenshtein distance, lexicon of Bulgarian word forms fb / ideal', 'Levenshtein distance, lexicon of Bulgarian word forms f / ideal']
In our last experiment we look at the influence of the length of the strings in the lexicon. We selected a smaller dictionary of natural language expressions consisting of approximately 450,000 Bulgarian word forms with average word length 10.01. Since for every query string P we require |P|≥3b, for bounds b>4 there are less than 10,000 entries in the smaller dictionary from which we could generate queries. For this reason in the case of the smaller dictionary we do not present results for b>4. Even for the short strings of the Bulgarian lexicon, the new method is much faster than the forward-backward method and the third method. The speed-up gained is less drastic than for the lexicons of titles and MEDLINE sentences, and here the ‘‘ideal method’’ remains more than 85 times faster than the new method.