自動正則表達式生成器

我有N個字符串。另外，還有K個正則表達式，我不知道。每個字符串或者匹配其中一個正則表達式，或者它是垃圾。集合中共有L個垃圾字符串。 K和L都是未知的。自動正則表達式生成器

我想推導出正則表達式。顯然，這個問題有無數的解決方案。我需要找到一個「相當不錯的解決方案」，這

1）減少ķ

2）減少大號

3）最大化的正則表達式的「特效藥」。我不知道這個質量的合適期限是什麼。例如，字符串「ab123」可以被描述爲/ ab \ d + /或/\w+.+/，但是第一個正則表達式更「特定」。

所有3個要求都需要作爲一個複合標準，並具有一定的合理權重。如果L = 0和K = 1（只有一個正則表達式，並且沒有垃圾），那麼我們可以爲這些字符串找到LCS（最長的公共子序列），並提出一個相應的正則表達式從那裏。但是，當我們有「噪音」（L> 0）時，這種方法不起作用。

任何想法（或指向現有的工作）非常感謝。

什麼是給出的信息？只是N弦？正則表達式已經決定了，但是隱藏起來了嗎？通過用「|」連接它們，您可以輕鬆生成與特定字符串集匹配的正則表達式。 – 2009-05-21 22:52:18

:)這將是作弊。我想我需要另一個標準來防止這種解決方案......我想，限制正則表達式的長度。 – 2009-05-21 23:00:06

您的條件＃3可以更好地描述爲最小化不在給定的N個字符串集合中的匹配字符串的數量。考慮到你有3件事要儘量減少（儘管你可能很容易要求L = 0），你需要權衡哪些因素更重要。 – user57368 2009-05-21 23:31:08

這裏沒什麼聰明，也許我不完全明白這個問題？

爲什麼不總是將L減小到0？檢查每個字符串對每個正則表達式;如果一個字符串不匹配任何正則表達式，那就是垃圾。如果匹配，請記住匹配的正則表達式/字符串，並在每個L = 0，K = 1上執行LCS以推導每個正則表達式的定義。

2009-05-21 22:46:11 benson

我沒有任何正則表達式。推斷他們的問題。 – 2009-05-21 22:57:20

學術界關鍵詞是「語法推理」。不幸的是，沒有任何有效的通用算法來處理你提議的事情。你真正的問題是什麼？

編輯：它聽起來像你可能會對數據描述語言感興趣。 PADS（http://www.padsproj.org/）就是一個典型的例子。

2009-05-21 22:55:20 Dave

你所要做的是語言學習或語言推理一擰：而不是要概括在一組給定的例子（也可能是反例），要推斷用語言一個很小的特定的語法。

我不知道該做多少研究。但是，如果您也有興趣找到接受所有n字符串的最小（=一般）正則表達式，請搜索MDL（最小描述長度）和FSMs（有限狀態機）上的論文。在Google Scholar

兩個有趣的疑問：

2009-05-21 22:56:09 Stephan202

回答