《正反例相結合的正則表達式極限識認算法》是依託華僑大學，由鄭黎曉擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：正反例相結合的正則表達式極限識認算法
- 項目類別：青年科學基金項目
- 項目負責人：鄭黎曉
- 依託單位：華僑大學
項目摘要,結題摘要,
項目摘要
對正則表達式學習算法的深入研究不僅具有重要理論意義，還具有較大實際套用價值。根據語言學習的經典理論模型，即Gold極限識認模型，正則語言在只有正例的情況下無法極限識認。已知的可識認子類對語言表達能力限制太強，在實際中不一定夠用。如果同時含有反例，則整個正則語言類可以極限識認。已有的正反例相結合的正則語言識認算法大多以自動機為識認目標，而從自動機轉換為表達式時存在長度爆炸等問題，給實際套用帶來困難。因此，本項目圍繞如何從含有正反例的樣本信息中直接以正則表達式為學習目標，研究正則語言極限識認相關的理論和算法問題，包括：認識算法的設計和特徵樣本的刻畫、算法及特徵樣本特性的理論分析、識認結果的評估等。識認目標除了標準表達式之外，還研究實際中經常用到的帶數字出現的表達式。項目研究成果一方面能夠為正則表達式學習算法的更好套用提供理論與算法支持，另一方面也可以豐富正則語言極限識認研究相關的理論體系。
結題摘要
形式語言的歸納學習致力於研究如何從語言的有限信息出發，通過歸納推斷得到語言的定義。在形式語言體系中，正則語言是一類使用較為廣泛並且具有良好特性的語言類。對以正則表達式為學習目標的正則語言學習算法的深入研究不僅具有重要理論意義，而且在基因序列識別、XML模式推斷、信息抽取、圖資料庫中路徑查詢語句學習等領域具有廣泛而重要的套用。本項目基於經典的語言極限識認模型，圍繞如何從給定的樣本信息中直接以正則表達式為學習目標，研究正則語言極限識認相關的理論和算法問題。主要研究成果簡述如下。（1）從XML模式推斷這一套用作為出發點，對現有的正則表達式學習算法現狀進行了深入調研，對已有算法進行了細緻的分類、歸納和對比。（2）提出一種基於連續重複子串挖掘和左聯配的正則表達式學習算法。理論分析證明出該算法符合語言學習的極限識認模型，能夠學習出一類不含“|”操作符的受限正則表達式，同時算法經過擴展可以學習出支持計數的擴展表達式。理論分析並總結出學習出的目標表達式所對應的特徵樣本的特點，並通過實驗驗證了理論分析結果的正確性。（3）基於軟體測試中成對測試的思想提出一種正則表達式覆蓋準則，稱作“成對覆蓋”，並設計和實現從正則表達式中自動生成滿足成對覆蓋準則的字元串生成算法。該算法可以用來為正則表達式識認（推斷） 算法自動生成測試數據。（4） 研究一類路徑查詢語句的視圖確定性問題，其中對路徑表達式的性質、確定性問題的可判定性及複雜性等理論問題做了深入探討，為正則表達式推斷算法在圖數據查詢學習中的套用研究提供必要的知識積累。此外，還嘗試將進化算法的思想套用於正則表達式學習中，研究如何對正則表達式進行編碼，已經如何定義適應度函式和獲得新的候選解使用的交叉、變異等運算元。該部分工作正在進行中。這些研究成果一方面能夠為正則表達式學習算法的更好套用提供理論與算法支持，另一方面也可以豐富正則語言極限識認研究相關的理論體系。
