基于連續(xù)重復(fù)子串左聯(lián)配的正則表達式識認(rèn)算法

發(fā)布時間：2020-08-18 13:56

【摘要】：形式語言的歸納學(xué)習(xí)致力于研究如何從語言的有限信息出發(fā),通過歸納推斷得到語言的定義。在形式語言體系中,正則語言是一類使用較為廣泛的語言類。以正則表達式為目標(biāo)的正則語言學(xué)習(xí)算法在基因序列識別、XML模式推斷、圖數(shù)據(jù)庫查詢學(xué)習(xí)、信息抽取中有廣泛應(yīng)用。因此,對正則表達式學(xué)習(xí)算法的研究不僅具有重要的理論意義,還具有較大的實際應(yīng)用價值。語言極限識認(rèn)模型是語言學(xué)習(xí)的經(jīng)典模型,在該模型下進行學(xué)習(xí)算法研究,不僅能確保算法的良好特性,且學(xué)習(xí)語言類具有清晰明確的界定。本文基于語言極限識認(rèn)模型,研究正則表達式學(xué)習(xí)算法,主要研究成果如下所述。(1)提出了基于連續(xù)重復(fù)子串左聯(lián)配的正則表達式識認(rèn)框架:首先,識別句子中的最長連續(xù)重復(fù)子串;其次,基于連續(xù)重復(fù)子串分塊;然后,對分塊進行左聯(lián)配;最后,將聯(lián)配結(jié)果泛化為正則表達式。在該框架內(nèi)進行算法研究,可以識認(rèn)一元正則運算符作用在多個連續(xù)字符上的正則表達式,克服了現(xiàn)有大多數(shù)算法只能識認(rèn)運算符作用在單個字符上的局限性。(2)針對標(biāo)準(zhǔn)表達式和帶數(shù)字出現(xiàn)的表達式,分別提出了兩類不同的泛化策略,并實現(xiàn)了兩種不同的識認(rèn)算法。分析出可由算法識認(rèn)的表達式子類,總結(jié)出表達式子類對應(yīng)的特征樣本的特性。為了驗證理論分析結(jié)果,本文開發(fā)了一組工具用于表達式及其特征樣本的生成并進行了相關(guān)的實驗,實驗結(jié)果驗證了理論分析的正確性。對比了本文算法和已有算法,結(jié)果表明本文算法的識認(rèn)結(jié)果在緊湊性、可讀性方面均存在優(yōu)勢。(3)探討了識認(rèn)算法在圖數(shù)據(jù)庫查詢學(xué)習(xí)中的應(yīng)用,分析出圖數(shù)據(jù)庫可達性查詢中有一類由正則表達式定義的路徑約束與本文提出的帶數(shù)字出現(xiàn)的表達式子類相吻合,因此可將本文算法應(yīng)用于圖數(shù)據(jù)庫可達性查詢學(xué)習(xí)�？偨Y(jié)出可達性查詢學(xué)習(xí)的一般步驟,并用實例考察了本文算法在可達性查詢學(xué)習(xí)中的應(yīng)用。
【學(xué)位授予單位】：華僑大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2019
【分類號】：H08;TP391.1
【圖文】：