An Analysis of the Correctability of Garbled Strings

摘要

The paper discusses the problems encountered, when processing garbled or erroneously spelled strings or words. Such strings are often output of many pattern recognition systems, e.g., character and speech recognition. Although several algorithms and methods for correcting such strings have been published, hardly any of the publications give some reasons why do the algorithms very often fail. This paper discusses the inherent behavior of correct and garbled strings and its effect on two of the most important error correcting methods, namely the Levenshtein distance method, and the substring or n-gram method.