模式匹配問(wèn)題在大數(shù)據(jù)時(shí)代下的信息檢索、文本挖掘、網(wǎng)絡(luò)安全以及生物信息學(xué)等很多領(lǐng)域都具有重要的應(yīng)用價(jià)值,尤其是帶有通配符的多模式近似匹配,相比正則表達(dá)式、單模式匹配和精確模式匹配,可以解決更加復(fù)雜的模式匹配問(wèn)題,如從海量異構(gòu)數(shù)據(jù)的碎片化知識(shí)中提取有價(jià)值的信息等。因此,根據(jù)帶有通配符的模式特性,借助后綴樹(shù)、后綴數(shù)組等高效的數(shù)據(jù)結(jié)構(gòu)及其相應(yīng)特性,對(duì)帶有通配符的多模式近似匹配問(wèn)題研究具有重要的研究意義和應(yīng)用價(jià)值。目前對(duì)于帶有通配符的模式匹配多是針對(duì)單模式匹配,而對(duì)于多模式匹配的研究更多的是針對(duì)精確匹配,對(duì)于帶有通配符的多模式近似匹配問(wèn)題的研究相對(duì)較少。而后綴樹(shù)、后綴數(shù)組在精確字符串匹配中非常高效,常用于查找字符串中的頻繁子串、最長(zhǎng)重復(fù)子串、最長(zhǎng)公共前綴及回文串等問(wèn)題,而在近似匹配中多是理論分析,缺少實(shí)驗(yàn)分析及論證。因此,采用后綴樹(shù)、后綴數(shù)組的方法進(jìn)行帶有通配符的多模式近似匹配研究具有重要的研究意義。本文在對(duì)國(guó)內(nèi)外有關(guān)帶有通配符的模式匹配、多模式近似匹配、后綴樹(shù)和后綴數(shù)組在近似匹配中的理論研究以及其相關(guān)數(shù)據(jù)結(jié)構(gòu)特性,進(jìn)行分析總結(jié)的基礎(chǔ)上,提出了基于后綴樹(shù)和后綴數(shù)組的新算法,用于解決帶有通配符的多...

【文章頁(yè)數(shù)】：112 頁(yè)

【學(xué)位級(jí)別】：博士

【文章目錄】：
致謝
摘要
abstract
第一章 緒論
    1.1 課題背景及研究意義
    1.2 國(guó)內(nèi)外研究現(xiàn)狀
        1.2.1 多模式匹配研究現(xiàn)狀
        1.2.2 帶有通配符的模式匹配問(wèn)題研究現(xiàn)狀
    1.3 研究?jī)?nèi)容和組織結(jié)構(gòu)
        1.3.1 主要研究?jī)?nèi)容
        1.3.2 內(nèi)容組織
    1.4 本章小結(jié)
第二章 相關(guān)研究工作
    2.1 模式匹配
        2.1.1 單模式匹配
        2.1.2 多模式匹配
        2.1.3 帶有通配符的模式匹配
    2.2 后綴樹(shù)
        2.2.1 字典樹(shù)
        2.2.2 后綴樹(shù)
        2.2.3 后綴樹(shù)特性
    2.3 后綴數(shù)組
        2.3.1 后綴數(shù)組
        2.3.2 后綴數(shù)組特性
    2.4 本章小結(jié)
第三章 基于后綴樹(shù)的帶有通配符的單模式匹配
    3.1 引言
    3.2 問(wèn)題定義
    3.3 算法設(shè)計(jì)與分析
        3.3.1 算法描述
        3.3.2 算法復(fù)雜度分析
    3.4 實(shí)驗(yàn)結(jié)果及分析
        3.4.1 算法的完備性
        3.4.2 算法的時(shí)間性能
        3.4.3 算法的其他性能
    3.5 本章小結(jié)
第四章 基于后綴樹(shù)的帶有通配符的多模式匹配
    4.1 引言
    4.2 問(wèn)題定義
    4.3 算法設(shè)計(jì)與分析
        4.3.1 算法描述
        4.3.2 算法復(fù)雜度分析
    4.4 實(shí)驗(yàn)結(jié)果及分析
        4.4.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)集
        4.4.2 實(shí)驗(yàn)結(jié)果
    4.5 本章小結(jié)
第五章 基于后綴數(shù)組的帶有通配符的多模式匹配
    5.1 引言
    5.2 問(wèn)題定義
    5.3 算法設(shè)計(jì)與分析
        5.3.1 算法描述
        5.3.2 算法復(fù)雜度分析
    5.4 實(shí)驗(yàn)結(jié)果及分析
        5.4.1 基于DNA序列的實(shí)驗(yàn)結(jié)果及分析
        5.4.2 基于蛋白質(zhì)序列的實(shí)驗(yàn)結(jié)果及分析
    5.5 本章小結(jié)
第六章 總結(jié)與展望
    6.1 主要研究工作
    6.2 下一步工作
參考文獻(xiàn)
攻讀博士學(xué)位期間的學(xué)術(shù)活動(dòng)及成果情況



本文編號(hào)：3771737