1、字符串的匹配問題被視為計算機科學的基本問題之一。早期的研究多集中于精確匹配領域，提出了許多單模式匹配算法和多模式匹配算法。 然而人們逐漸發(fā)現在實際應用中有時更需要進行近似字符串匹配。它在信號處理、文本檢索、計算生物學、病毒檢測、模式識別、OCR糾錯等領域均有重要的應用價值。因此，研究(設計)高效的近似字符串匹配算法具有重要的理論價值和實際意義。 應該說，近似匹配是精確匹配的變種和發(fā)展，也就是按照一定的近似標準在文本串中找

2、出與模式串相匹配的子串。對應的，多模式近似匹配則是按照一定的近似標準在文本串中找出與模式串集合相匹配的子串。 盡管對近似字符串匹配問題的研究歷史已不短，相應的文獻資料也不少，不過其中絕大多數的研究對象(字符集)都是針對英文等中等大小字符集或者針對DNA等微小字符集，而針對漢字及亞洲語言等大字符集的研究卻很少。其次，對多模式近似字符串匹配問題的研究也還不成熟，不管是針對中小字符集還是大字符集，均沒有特別成功的解決方法。 基

3、于上述原因，論文主要完成了如下工作：本文的第一、二章，我們簡要介紹了論文的研究背景、研究目的、主要內容和組織結構。同時還對近似字符串匹配問題進行了綜述，介紹了相關的理論及主要研究方法，并分別對動態(tài)規(guī)劃、自動機、位并行、過濾等主要方法進行了介紹和分析。 第三章對BPM等部分重要算法進行了較詳細的分析。 第四、五章是本文的核心，提出了在漢字等大字符集環(huán)境下基于過濾的位并行方法，具體包括基于漢字的單模式近似字符串匹配算法IBP