Dissertation > Excellent graduate degree dissertation topics show

Approximate String Matching for Chinese Characters by Combining Filtering and Bit-parallelism

Author: FanLiXin
Tutor: ZhuangYueTing
School: Zhejiang University
Course: Computer Applications
Keywords: Approximate string matching Dynamic Programming Automata Bit parallel computing Filter Edit distance Chinese string matching Multi-pattern matching
CLC: TP391.1
Type: Master's thesis
Year: 2006
Downloads: 296
Quote: 3
Read: Download Dissertation

Abstract

String matching problem is considered one of the basic problems in computer science. Earlier studies mainly focused on the field of exact matches and made many single pattern matching algorithms and multi-pattern matching algorithms. However, people gradually found in practical applications sometimes need to approximate string matching. It is in signal processing, text retrieval, computational biology, virus detection, pattern recognition, OCR error correction and other fields have important application value. Therefore, the study (design) and efficient approximate string matching algorithm has important theoretical and practical significance. It should be said, an approximate match is exact matching variants and development, which is in accordance with certain criteria in a text string approximation to find the pattern string matches the substring. Correspondingly, an approximate match is a multi-mode approximation of standards in accordance with certain text strings to identify and model train set that matches the substring. Despite the approximate string matching problem study of history has been a lot, the corresponding literature is also a lot, but the vast majority of subjects (character set) are for English and other medium-sized character set or the character set for DNA and other minor , and for large character sets such as Chinese and Asian language studies are few. Secondly, the multi-mode approximate string matching problem research is not yet mature, regardless of the character set for small or large character set, did not particularly successful solution. For the above reasons, the paper mainly to complete the following work: This article first, second chapter, we briefly introduced the research background, research purposes, the main content and organizational structure. But also on the approximate string matching problem were reviewed to introduce the relevant theories and the main research methods, and dynamic programming, respectively, automata, bit parallel, filtration and other major methods are described and analyzed. The third chapter of the BPM and some important algorithms for a more detailed analysis. Chapters 4 and 5 is the core of this article is presented in large character sets such as Kanji environment based filtering bit parallel method, specifically including a single-mode approximation based on Chinese characters string matching algorithm IBPM-BM and multi-mode approximate string matching algorithm MBPM-BM, known as the main character is based on these two algorithms in large character sets such as Chinese characters exceptionally good environment. Algorithms in theory and in practice, have better performance, the paper also gives a complexity analysis and experimental results. It should be noted that the two most important features of the algorithm is to make full use of the filtration stage bit parallel technologies to fully tap the potential of computer's physical word. In the sixth chapter, summarize in this article, the application prospect and gives possible future research directions.

Related Dissertations

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > Computer applications > Information processing (information processing) > Text Processing
© 2012 www.DissertationTopic.Net Mobile