從一組字符串中導出RegExp

想象一下，有一組任意的字符串。我們現在假設，除了一些成功的人物之外，他們都是平等的（如果這個假設不成立，那麼我會很好地迴應一個錯誤）。我現在想要派生一個正則表達式來標識不同的字符串部分。從一組字符串中導出RegExp

 
Input: 
"Hello Alice, I'm Bob.", "Hello John, I'm Bob.", "Hello Josh, I'm Bob." 

Output: 
"Hello (.+), I'm Bob." 

Input: 
"Monday", "Tree", "Dog" 

Output: 
Error

也許找到longest common substrings或Levenshtein distance可以幫助？我不確定它們中的一個是否真的適用於我的問題，或者如何使用它們來解決問題。

來源

2012-08-03 sigy

既然這是作業，我會嘗試給出更「體貼」的提示。我不確定你在基本計算理論中的背景是什麼，但將這些問題想象爲DFA（或者，在這種情況下，可能是相當於NFA的問題）通常很有幫助。嘗試創建一個產生正確結果的狀態圖並將其轉換爲正則表達式。 – RageD 2012-08-03 12:13:31

不知道爲什麼這被標記爲家庭作業。不是這樣！無論如何...我還不知道這是如何與自動機相關的，請您詳細解釋一下嗎？我也不明白爲什麼我的例子不符合我的問題。如果你能告訴我你的意思，我會盡力改善我的問題。 – sigy 2012-08-04 20:49:54

你有一個問題，並決定使用正則表達式來解決它 - 現在你有兩個問題。 :-)

所有開玩笑之外，你可以將其分爲兩個步驟：

識別字符串之間的差異。
看看所有的差異，找出一個匹配它們的正則表達式。

對於（1），它在你的語言使用差異計算庫（像在Python difflib）找到相同區域的兩個字符串之間以列表的問題。如果所有的字符串都有公共段，那麼比較string-1和string- [2..N]中的每一個來分析結果相同的塊（你必須聰明地比較每個塊的內容及其相對於其他相同的位置塊）。也提取並記錄相同塊之間的文本。

對於您的示例，每次比較時都會得到兩個相同的塊："Hello "和", I'm Bob."。相同的塊之間的文本將是這些字符串："Alice","John","Josh"。

對於（2），最微不足道的解決方案是把結果組合成構成一相當字面的regexp：

Hello + (Alice|John|Josh) + , I'm Bob.

或者，替換找到相同的相同電路塊之間的任何段在全部字符串與.*。考慮做一個非貪婪的比賽 - .*?。

我不知道自動機理論，不能幫助您使用DFA/NFA，但如果您需要更高的精度，這是一個堅實的方向。

來源

2012-08-31 22:36:23 vsh

從一組字符串中導出RegExp

回答

相關問題