計算機是否可以通過用戶提供的示例「學習」正則表達式？

Question

計算機是否可以通過用戶提供的示例「學習」正則表達式？

澄清：

• 我做不要學習正則表達式。
• 我想創建一個程序，它可以從用戶交互式提供的例子中「學習」正則表達式，也許可以通過從文本中選擇部分或選擇開始或結束標記。

這可能嗎？ Google可以提供哪些算法，關鍵字等？

編輯：謝謝你的答案，但我沒有興趣在提供此功能的工具。我正在尋找理論信息，如論文，教程，源代碼，算法名稱，所以我可以爲自己創造一些東西。

Answer 1

本書An Introduction to Computational Learning Theory包含學習有限自動機的算法。由於每種常規語言都等價於有限自動機，因此可以通過程序學習一些正則表達式。 Kearns and Valiant顯示了一些不可能學習有限自動機的情況。一個相關的問題是learning hidden Markov Models，它是可以描述字符序列的概率自動機。請注意，編程語言中使用的大多數現代「正則表達式」實際上比常規語言更強，因此有時難以學習。

Answer 2

你可能想用這個網站玩了一下，這是相當涼爽，聽起來就像是做類似的東西，你在說什麼：http://txt2re.com

Answer 3

相信術語是「上崗」。你想引發一個正規的語法。

我不認爲用一組有限的例子（正數或負數）是可能的。但是，如果我記得正確的話，如果有一個可以諮詢的Oracle，就可以完成。 （基本上，你必須讓程序詢問用戶是/否的問題，直到它的內容。）

Answer 4

如果它有可能一個人去學習正則表達式，那麼它是從根本上可能的程序。但是，該程序需要正確編程才能學習。幸運的是，這是一個相當有限的邏輯空間，所以它不像教授一個程序能夠看到物體或類似物體那麼複雜。

Answer 5

是的，這當然是「可能的」;這裏的僞代碼：

string MakeRegexFromExamples(<listOfPosExamples>, <listOfNegExamples>) 
{ 
    if HasIntersection(<listOfPosExamples>, <listOfNegExamples>) 
    return <IntersectionError> 

    string regex = ""; 
    foreach(string example in <listOfPosExamples>) 
    { 
     if(regex != "") 
     { 
     regex += "|"; 
     } 
     regex += DoRegexEscaping(example); 
    } 
    regex = "^(" + regex + ")$"; 

    // Ignore <listOfNegExamples>; they're excluded by definition 

    return regex; 
} 

問題是，有無數的正則表達式將匹配的例子列表。這段代碼提供了集合中最簡單/最愚蠢的正則表達式，它基本上與正例中的任何東西都匹配（並且沒有其他任何內容，包括任何負面例子）。

我想真正的挑戰是找到與所有例子相匹配的最短正則表達式，但即使如此，用戶也不得不提供非常好的輸入來確保結果表達式是「正確的」。

Answer 6

@Yuval是正確的。你正在研究計算學習理論，或者「歸納推理」。「

這個問題比你想象的要複雜得多，因爲」學習「的定義是非平凡的。一個常見的定義是學習者可以隨時吐出答案，但最終它必須停止吐出答案，或總是吐出相同的答案，這假定有無數的輸入，並且在程序達到其決定時絕對不提供任何補償，而且，當它已經達到它的決定時，你不能分辨它是什麼，因爲它可能仍然輸出不同的東西以後。

根據這個定義，我敢肯定，正規語言是可以學習的。其他的定義，沒有那麼多...

Answer 7

沒有計算機編程的， m將永遠能夠在有效匹配列表上生成一個基於的純粹的有意義的正則表達式。讓我告訴你爲什麼。

假設你提供的實施例中111111和999999，應在計算機生成：

1. 甲正則表達式匹配恰好這兩個例子：(111111|999999)
2. 甲正則表達式匹配的6個相同數字(\d)\1{5}
3. 甲正則表達式匹配的6一個和九個[19]{6}
4. 匹配任意6位數的正則表達式\d{6}
5. 任何三個以上，具有單詞邊界，例如， \b\d{6}\b
6. 前三位中的任何一位，前面或後面都沒有數字，例如， (?<!\d)\d{6}(?!\d)

正如你可以看到，有許多方法在這些實例可以概括爲正則表達式。計算機構建可預測的正則表達式的唯一方法是要求您列出全部可能的匹配項。然後它可以生成一個匹配那些匹配的搜索模式。

如果您不想列出所有可能的匹配項，則需要更高級別的說明。這正是正則表達式旨在提供的。您只需告訴程序匹配「任意六位數字」，而不是提供6位數字的長列表。在正則表達式語法中，這變成\ d {6}。

任何提供與正則表達式一樣靈活的更高級別描述的方法也將與正則表達式一樣複雜。像RegexBuddy這樣的所有工具都可以使創建和測試高級描述更容易。直接使用簡潔的正則表達式語法，RegexBuddy使您可以使用簡單的英語構建塊。但它不能爲你創建高級描述，因爲它不能神奇地知道它應該什麼時候推廣你的例子，什麼時候不應該。

當然可以創建一個工具，使用示例文本以及用戶提供的指導原則來生成正則表達式。設計這種工具的難點在於它如何向用戶詢問所需的指導信息，而不會使工具比正則表達式本身更難學習，並且不會將工具限制爲普通的正則表達式工作或簡單的正則表達式。

Answer 8

有一種語言致力於這樣的問題，基於prolog。它被稱爲progol。

正如其他人所提到的，其基本思想是歸納學習，在AI界通常被稱爲ILP（inductive logic programming）。

第二個鏈接是關於ILP的wiki文章，其中包含許多有用的源材料，如果您有興趣瞭解更多關於該主題的內容。

Answer 9

我已經做了谷歌和CiteSeer一些研究，發現這些技術/論文：

• Language identification in the limit
• Probably approximately correct learning

而且戴納·安格盧的「學習從查詢和反例規則集」似乎很有前途，但我無法找到PS或PDF版本，只能引用和研討會論文。

即使在理論層面上，這似乎也是一個棘手的問題。

Answer 10

是的， 有可能， 我們可以從例子（文本 - >所需的提取）中生成正則表達式。 這是一個在線工具，它可以完成這項工作：http://regex.inginf.units.it/

正則表達式++在線工具通過使用GP搜索算法提供的示例生成正則表達式。 GP算法由多目標適應度驅動，導致更高的性能和更簡單的解決方案結構（Occam's Razor）。 這個工具是由裏雅斯特大學的機器勒維實驗室（Universitàdegli studi di Trieste）提供的一種應用。 請看視頻教程here。

這是一個研究項目，所以你可以閱讀關於使用的算法here。

看哪！ :-)

尋找從一個例子的正則表達式有意義/溶液是可能當且僅當所提供的實施例描述了問題良好。 考慮這些描述提取任務的例子，我們正在尋找特定的物品代碼;的實例是文本/提取對：

"The product code il 467-345A" -> "467-345A" 
"The item 789-345B is broken" -> "789-345B" 

的（人）的人，着眼於實施例，可以說--ie： 「的項目代碼之類的東西\ d ++ - 345 [AB]」

當物品代碼更寬容但我們沒有提供其他例子時，我們沒有證據可以很好地理解問題。 當將人類產生的解\ d ++ - 345 [AB]以下內容的文本，它失敗：

"On the back of the item there is a code: 966-347Z" 

你必須提供其它實例中，爲了更好地描述什麼是匹配的，哪些是不所需的匹配： --ie：

"My phone is +39-128-3905 , and the phone product id is 966-347Z" -> "966-347Z" 

的電話號碼是不是一個產品ID，這可能是一個重要的證明。