如何檢測字符串列表中的重複？

Question

我有SQL調用，我想用它來檢測環路（因此不必要的重複的SQL調用）的序列，但它讓我思考這個更一般的問題。

給出一個列表，說 [a,b,c,b,c,a,b,c,b,c,a,b,b]

有沒有一些方法，我可以把它轉換成 a,[[b,c]*2,a]*2,b*2

，或者[a,[b,c]*2]*2,a,b*2

也就是說，檢測重複（可能是嵌套的）。

Answer 1

窺視Lempel-Ziv-Welsh compression algorithm。它建立在檢測字符串重複並將其用於壓縮的基礎上。我相信你可以使用一個Trie 它。

Answer 2

如果你可以先進行排序，然後很容易經歷更多的時間來尋找重複操作。當然，像SQL查詢這樣的自由格式排序聽起來有點可怕。

Answer 3

我在這一領域的專家，但你可能想看看一些壓縮算法，在我看來，這是相當正是他們做什麼。

Answer 4

如果字符串足夠大，一個有趣的方法是在其上運行壓縮工具（如gzip，bzip或7zip）。這些工具通過定位重複（各級），並通過指針取代他們的文字（或字典）的初審工作。你實現的壓縮是重複的度量。轉儲文件（你將不得不編寫代碼來做到這一點）會給你重複的內容。