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

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

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

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



本文編號：3771737