Este trabalho relata o projeto, implementação e teste de um sistema que integra reconhecimento digital de textos em imagens de documentos antigos com busca e indexação aproximada e alinhamento múltiplo dos documentos. O reconhecimento de texto em documentos históricos, com tipografia muito diferente da atual e estado de conservação precário, é altamente sujeito a erro de forma que a comparação e o alinhamento múltiplo necessário a uma reconstituição de um estudo da origem filogenética precisa usar técnicas de Busca Aproximada para contornar o problema. Assim, propomos um sistema de pontuação para documentos históricos que releva o alinhamento de termos similares sujeito aos erros de OCR ou grafias diversas. Para a identificação de palavras semelhantes dentro de uma taxa de erro preestabelecida, usamos um cálculo da distância de edição proposto por Ukkonen que ainda requer muito recurso computacional. Nós propomos e testamos o uso de um filtro que usa sacos de símbolos que garante os mesmos resultados com uma redução drástica da computação das distâncias de edição. Desta forma, para identificação de trechos semelhantes em documentos históricos diversos sujeito a erros, foi proposta uma estratégia de alinhamento múltiplo local que utiliza técnicas de extração de sementes e expansões de alinhamentos locais como a usada pela ferramenta BLAST, muito conhecida na área de Bioinformática. Diante das deficiências encontradas nos trabalhos de processamento de imagens de documentos históricos no que diz respeito à segmentação de caracteres, propusemos e implementamos um novo algoritmo de segmentação baseado em uma modelagem que permite a elaboração de um algoritmo de otimização através de programação dinâmica, ao contrário das heurísticas existentes baseadas em estratégias gulosas. Foi também proposta uma arquitetura que aproveita dos alinhamentos produzidos contra documentos gabarito de forma a retreinar e aumentar a acurácia do classificador OCR

This thesis describes the design, implementation and experiments on a software system that integrates digital irnage pracessing for historical docurnents with appraxirnate search and multiple alignrnent for these kind of documents. Old typography along with a bad preservation state is very cornmon in historical docurnents. These two features generate noise when irnages of this kind are pracessed by modern OCR systems. Therefore, in order to perform comparison and rnultiple alignment that would lead to a reconstruction of the phylogenetic tree for these documents, one should use Appraxirnate Search techniques to overcorne this problern. We also prapose an scoring systern for historical documents based on the alignment of similar words bounded by an errar rate or with diverse spelling. To identify similar words considering a fixed errar rate, we use an an efficient Ukkonen's edit distance algorithm which still demands a Iot of computational resources. Thus, we proposed and ran experiments on a filter that uses a distance based on bag of characters that not only guarantees the sarne results but also drastically reduces the number of calls to Ukkonen's edit distance. In order to identify similar passages among historical documents allowing errors, we praposed a multiple local alignment algorithm that lends techniques like seeding and local alignment expansion from tools like BLAST, very popular in Bioinformatics. We also identified limitations in many solutions proposed for the problem of touching character segmentation in the image pracessing literature. We proposed and irnplemented a novel segmentation algorithm based on an model that allows to intraduce an optimization algorithm that uses dynamic programming, unlike existing heuristics based on greedy strategies. We also proposed an architecture that harnesses on the alignments generated against a ground-truth text document in order to retrain and increase accuracy for an OCR system