Matching for run-length encoded strings

The need to approximately match run-length encoded strings emerged during development of an optical character recognition (OCR) system. This system, built in association with Data Capture Systems Inc., is designed to achieve a low substitution error-rate via fixed-front character recognition. The ith row or column of pixels in a given query character image will define a binary string containing a small number of white-black transitions. By comparing this run-length encoded string against the ith row or column of each of the character image-models, the similar can be identified. An algorithm which finds these longest common subsequences of strings X and Y in time polynomial in the size of the compressed strings is presented.