參考的paper
TCAM-based DFA Deflation: A Novel Approach To
Fast and Scalable Regular Expression Matching
1.idea
雖然D2FA可以有效的解決DFA的memory comsunmption，但是在look up 的過程中，會需要經過多次的default transition，使得memory access的次數增加，也雖然透過default transition使得DFA在圖形表達時，看起來會有很少的transition數量，但是在基本的二維的transition table，也是依然要用symbol表示default transition存在，所以希望透過TCAM解決memory access的次數的問題以及用更少的memory來表達transition table
2.方法
在建立D2FA的過程中，會因為diameter bound產生不同個數的D2FA forest，較大的diameter bound 會需要多次的default transition來找出實際的next state。但是可以有效的透過default transition減少state之間大部份的相同的transition，所以實際上我們只需要保留identical transition，以及透過default transition之後才找到的next-state transition，也因為大部份的state是因為有共同的transtiion才會使得default transition存在，所以藉由這樣的"common"關係，就可以利用TCAM的ternary來做進一步的壓縮。
所以方法就是建立在
1.用D2FA來做group，
2.針對group給予在TCAM中表達出state的code
考慮一個例子，
.*A.{2}CD，
在經過"default to"過group之後，可以有以下6個group結果
(冒號後的states都是default 到冒號前的state)
0 :8 12
5 :1 5
6 :2
7 :3 7
11:6 9 11
13:0 4 10 13
考慮6以及11這兩組group
簡單表示出相關的state及 tx，
數字是state，大寫字母是指一般的transition，小寫d為default transition
9 -C-> 4 4
↓ ↑ ↑
d D C
∣ ∣ ∣
11 <-d- 6 <-d- 2
11-A-> 5
11-C-> 10
11-D-> 13
在上面提到的 identical transition (不經由default即可找到next state)
有以下幾個
9+C->4
2+C->4
6+D->4
11+A->5
11+C->10
11+D->13
透過default transition之後才找到next state的transition
2+A->5 6+A->5 9+A->5
2+D->4 6+C->10 9+D>13
雖然從11出發三個transition規類在identical transition
但是11跟2 6 9 三個state都有共同的transtion，
所以經過給TCAM CODE之後，只需要保留
9+C->4 6+D->4 *+A->5
2+C->4 2+D->4 *+C->10
*+D->13
雖然這只是一組group的例子
全部group都有考慮的話，可以有的common transition會更多，也可以用更少的memory
