創建一個字符串列表的正則表達式

Question

我已經從科學文獻中提取了一系列表格，這些表格由各自爲不同類型的列組成。這裏是一個例子

我希望能夠爲每列自動生成正則表達式。顯然，有平凡的解決方案，如.*所以我想補充一點，他們只用了約束：

• [A-Z] [a-z] [0-9]
• 明確標點符號（如','，'''）
• 「簡單」 的量詞（例如{3,4}

上表中的「最佳」答案是：

[A-Z]{3} 
[A-Za-z\s\.]+ 
\d{4}\sm 
\d{2}\u00b0\d{2}'\d{2}"N,\d{2}\u00b0\d{2}'\d{2}"E 
(speciosissima|intermediate|troglodytes) 
(hf|sr) 
\d{4} 

當然，如果我們移動到地理區域之外，第四個正則表達式會中斷，但軟件不知道。目標是收集許多正則表達式，例如說「座標」並概括它們，可能是部分手動的。只有在有少量不同的字符串時纔會創建枚舉。

我很感激能夠做到這一點的（特別是F/OSS）軟件的例子，特別是在Java中。 （這與Google的Refine相似）。我知道this question 4 years ago，但這並沒有真正回答這個問題，而text2re這個網站似乎是互動的。

注：我注意到投票結束爲「過於本地化」。這是一個非常普遍的問題（表中給出的僅僅是一個例子），正如Google/Freebase開發Refine所示，以解決這個問題。它可能涉及各種各樣的表格（例如金融，新聞等）。這裏有一個浮點值：

自動確定某些權威機構實時報告年齡（例如不是幾個月，幾天）並使用2位數的精度將是有用的。

Answer 1

您的特殊問題是「通過演示編程」的特例。也就是說，給定一堆輸入/輸出示例，您需要生成一個程序。對你而言，輸入是字符串，輸出是每個字符串是否屬於給定列。最後，您希望使用您提出的有限正則表達式的語言生成一個程序。

這個演示編程的特例似乎與MSR最近的一個項目Flash Fill密切相關。在那裏，代替匹配數據生成正則表達式，它們自動生成程序變換基於輸入/輸出示例的字符串數據。

我只通過one他們的論文，但我會試着闡述我在這裏理解的東西。

本文中基本上有兩個重要的見解。首先是設計一個小型編程語言來表示字符串轉換。即使使用全功能正則表達式，也可以快速搜索到太多可能性。他們設計了自己的抽象語言來操作字符串;然而，您的約束（例如，只使用簡單的量詞）可能會起到與其自定義語言相同的作用。這在很大程度上是可能的，因爲您的特定問題的範圍比他們的範圍稍小。

第二個見解是關於如何在這種抽象語言中實際找到與給定輸入/輸出對匹配的程序。我的理解是，這裏的主要想法是使用一種名爲version space algebra的技術。關於版本空間代數的粗略想法是，您維護可能程序空間的表示，並通過引入附加約束來重複修剪它。這個過程的確切細節遠遠超出了我的主要興趣，所以你最好閱讀introduction to version space algebra，其中還包括一些示例代碼。

他們也有一些聰明的方法來排列不同的候選程序，甚至猜測哪些輸入可能對已經生成的程序有問題。我看到一個演示，他們在沒有給出足夠的輸入/輸出對的情況下生成了一個程序，程序實際上可以突出顯示可能不正確的新輸入。這種排名非常有趣，但需要一些更復雜的機器學習技術，並且可能不會立即適用於您的用例。雖然可能仍然很有趣。 （另外，這可能與我鏈接的論文有所不同。）

所以，長話短說，您可以通過將輸入/輸出示例提供給基於版本空間代數的系統來生成您的表達式。我希望有所幫助。

Answer 2

我自己的方法（我已部分原型化）是啓發式的，並且基於給定列經常具有相同或相似字符長度且具有類似標點符號的條目的前提。我會歡迎評論（並由此產生的代碼將爲開源）。

1. 弄平[A-Z]到'A'
2. 弄平[a-z]到'a'
3. 弄平[0-9]到'0'
4. 弄平任何其它特殊的碼點集（例如希臘字符）爲單個字符（例如字母）

然後列成爲：

1. "AAA"
2. "Aaaaaaaaaa", "Aaaaaaaaaaaaa", "Aaa aaa Aaaaaa"等
3. "0000 a"
4. "00\u00b000'00"N,00\u00b000'00"E
5. ...
6. ...
7. 「0000」

我可以將取代這些通過正則表達式suc H作爲

1. "([A-Z])([A-Z])([A-Z])"
2. ...
3. "(\d)(\d)(\d)(\d)\s([0-9])"

，並捕獲單個字符成組。這將顯示（說）在3。最終字符總是"m"，所以\d\d\d\d\s[m]和7.值爲[2][0][0][458]。

對於不適合此模型的列，我們使用"(.*)"進行搜索，並查看我們是否可以創建有用的集合（第5列和第6列），如「至少2個多個字符串且不超過50個％獨特的字符串「。

通過使用動態規劃（參見克魯斯卡）我希望能夠對準類似的正則表達式，這將是有用的對我來說，至少！

Answer 3

我目前正在研究相同的（或類似的）（here）。通常，這稱爲Grammar induction，或者在正則表達式的情況下，它是induction of regular languages。關於這個領域有StaMinA competition。常用算法是RPNI和Blue-Fringe。

Here是另一個相關的問題。而另一個是here。另外還有here。