我正在嘗試為 DFA 實作一個非常簡單的狀態轉換表，但我遇到了一些效率問題。
如果我安排一個轉換表，其中每一行作為源狀態，每一列作為可能的輸入，交集作為下一個狀態，那么轉換很簡單：
next_state = table[from_state, input]
此方法將給出 O(1) 過渡時間。當有很多可能的輸入時，就會出現問題。如果我有一個包含所有 128 個 ASCII 字符的字母表，那么該表將變得失控，并且即使只是幾個狀態（狀態 * 輸入）也會在記憶體中咀嚼。
我考慮的另一個選擇是使每一列成為目標狀態，并將交叉點作為輸入符號。
input = table[from_state, to_state]
這種方法減少了記憶體消耗，但執行轉換需要測驗所有列，直到以 O(N) 方式找到具有正確輸入的列。
我真的陷入了時空權衡，還是有更好的方法來實作這一點？
PS我知道存在壓縮演算法，但是它們可以用來在構建程序中保持表壓縮嗎？
uj5u.com熱心網友回復：
我想我已經決定了一個似乎適合我需要的實作。它使用與第一種方法相同的方法，但保留一個單獨的元組來跟蹤使用的最小和最大代碼點。該表將僅將其列擴展到此范圍內的字符數。由于除了有限的字符范圍之外，大多數字符可能永遠不會被使用，這可能就足夠了。
然后索引從索引 0 開始變為（輸入 - 最低代碼點）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/459260.html
上一篇：這個解決方案的時間復雜度是多少？