Skip Trie Matching: A Greedy Algorithm for Real- Time OCR Error Correction on Smartphones

Proactive nutrition management is considered by many nutritionists and dieticians as a key factor in reducing diabetes, cancer, and other illnesses caused by mismanaged diets. As more individuals manage their daily activities with smartphones, they start using their smartphones as diet management tools. Unfortunately, while there are many vision- based mobile applications to process barcodes, especially aligned ones, there is a relative dearth of vision-based applications for extracting useful nutrition information items such as nutrition facts, caloric contents, and ingredients. In this article, we present a greedy algorithm, called Skip Trie Matching (STM), for real time optical character recognition (OCR) output error correction on smartphones. The STM algorithm uses a dictionary of strings stored in a trie data structure to correct OCR errors by skipping misrecognized characters while driving down several paths in the trie. The number of skipped characters is referred to as the skip distance. The algorithm's worst-case performance is