Source-linked AI summary
Levenshtein Distance Technique in Dictionary Lookup Methods: An Improved Approach
Rishin Haldar, Debajyoti Mukhopadhyay
TL;DR
OCR dictionary lookup can be complicated by prior-probability calculations and the search cost of large dictionaries. The paper modifies Levenshtein distance by lowering costs between visually similar letters. In the reported test, the modification reduced unrecognized words compared with standard Levenshtein distance, though its effectiveness beyond words of length three and five remains unverified.
Problem
Dictionary lookup can add overhead through prior-probability calculations, while large dictionaries increase search costs.
Source: §1 · p. 1Method
The method modifies Levenshtein distance by grouping similar-looking letters and reducing the weighted difference among group members.
Source: §1 · p. 1, §3.1 · p. 3Results
The modified method reduced unrecognized words from 93 to 52, compared with 66 using standard Levenshtein distance; after Bayesian lookup, it recognized 304 words versus 263 with LD.
Source: §5 · p. 4Takeaways & Limitations
The authors report that the modification reduces error and, when it does not narrow possible outcomes, its output is no worse than standard LD’s.
Source: §3.1 · p. 3, §6 · p. 5Effectiveness was tested only on words of length three and five, and remains unverified for other lengths.
Source: §6 · p. 5
Abstract
from arXiv · showhide
Dictionary lookup methods are popular in dealing with ambiguous letters which were not recognized by Optical Character Readers. However, a robust dictionary lookup method can be complex as apriori probability calculation or a large dictionary size increases the overhead and the cost of searching. In this context, Levenshtein distance is a simple metric which can be an effective string approximation tool. After observing the effectiveness of this method, an improvement has been made to this method by grouping some similar looking alphabets and reducing the weighted difference among members of the same group. The results showed marked improvement over the traditional Levenshtein distance technique.
1. Introduction
Dictionary lookup supplements OCR by finding dictionary entries closest to incorrectly recognized strings, especially when letters are ambiguous. The paper examines Levenshtein distance as a simpler alternative to lookup methods involving prior probabilities, then proposes a modification.
1. Introduction
- Dictionary lookup finds the closest dictionary matches for OCR strings with ambiguous or incorrectly recognized letters.It is used as a supplement during post-processing.Source: §1 · p. 1
- Prior-probability calculations add overhead and complexity, short dictionaries may miss contextual matches, and large dictionaries raise search costs.Source: §1 · p. 1
- The paper applies Levenshtein distance to string approximation and modifies it to improve output without much additional overhead.The approach is motivated by avoiding prior-probability calculations in dictionary lookup.Source: §1 · p. 1
2. Existing Method
Levenshtein distance measures the edit operations needed to transform an input string into a dictionary entry. The paper describes a matrix-based algorithm for calculating that distance.
2.1 Levenshtein Distance
- Levenshtein distance counts the deletions, insertions, and substitutions needed to transform source string s into target string t.Here, the source is the input and the target is a dictionary entry.Source: §2.1 · pp. 1–2
2.2.1 An Example
- Transforming GUMBO into GAMBOL requires two edits, so the example matrix’s lower-right distance is 2.Source: §2.1 · p. 2, §2.2.1 · p. 2
2.2 The algorithm
- The algorithm initializes a matrix by string lengths, then fills each cell with the minimum cost from deletion, insertion, or substitution/match transitions.It repeats processing until d[n,m] gives the result.Source: §2.2 · p. 2
3. Modifications
The modification assigns lower edit costs to visually similar letters, grouping them so that the resulting dictionary matches can better reflect handwriting ambiguity. Its benefit is not guaranteed to break ties, but it does not remove matches returned by standard Levenshtein distance.
3. Modifications
3.1 Justification of this modification
- For OCR output BDQY, standard Levenshtein distance gives four possible words, while modified weighting can make BODY the shortest match.The example connects the weighting to similar-looking handwritten letters.Source: §3.1 · p. 3
- If modified distances remain tied, the method may not narrow the candidate set; any correct answer among standard LD outputs remains in the modified output.Source: §3.1 · p. 3
4. Experimental Setup
The experiment used STPRTools OCR and dictionary lookup to compare standard and modified Levenshtein distance on manually entered English words. The setup restricted word lengths and reduced training samples to emphasize post-processing.
4.1 Data collection
- Training data came from STPRTools’ handwritten numerical data; its OCR system used 16x16-pixel inputs for each alphabet and a GUI for manually entering samples, while dictionary words came from /usr/dict/words, with more than 25,000 English words.Source: §4.1 · p. 3
4.2 Data Preprocessing
- Training samples were manually entered, restricted to English words of length 3 or 5, and reduced from 50 to 20 to give Levenshtein methods more opportunity to show post-processing effectiveness.Source: §4.2 · pp. 3–4
4.3 Software Used
- The implementation used Matlab’s STPRTools toolbox and incorporated both standard and modified Levenshtein distance methods.Source: §4.3 · p. 4
4.3.1 Steps followed
- The test used 250 words of length three and 250 of length five, applied SVM recognition, then ran both distance methods on SVM-unrecognized words and compared them with Bayesian dictionary lookup.The Bayesian method selected three nearest words.Source: §4.3.1 · p. 4
5. Experimental Results
After SVM processing, 93 of 500 test inputs remained unrecognized; LD reduced this to 66, while MLD reduced it to 52. After Bayesian processing, LD recognized 263 words and MLD recognized 304.
5. Experimental Results
- 52 of 93 initially unrecognized inputs remained unrecognized with MLD, compared with 66 after standard LD.The experiment began with 500 test inputs processed through SVM.Source: §5 · p. 4, Table 2 · p. 4
- 304 words were recognized by MLD versus 263 by LD after Bayesian processing.Table 3 reports unrecognized words after Bayesian processing.Source: Table 3 · p. 4, §5 · p. 4
6. Conclusion
The authors report that MLD reduces errors and is no worse than standard LD when it does not narrow the possible outcomes. Its effectiveness was tested only on words of lengths three and five.
6. Conclusion
- The authors report that MLD reduces errors and is no worse than standard LD when it does not narrow the possible outcomes.They believe the reduction would also hold for larger numbers of test samples.Source: §6 · p. 5
- The approach was tested only on words of lengths three and five, leaving its effectiveness on other lengths unverified.The authors also note that dictionary size must be balanced against computation overhead.Source: §6 · p. 5
- The authors suggest the approach could serve scanned-manuscript services and help users interpret unclear alphanumeric authentication characters.They describe these as possible applications.Source: §6 · p. 5