用位并行法進(jìn)行過濾的中文近似串匹配算法.pdf

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

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

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