There are a number of rules (an order of 10K, may be 100K-ish) that looks like a tuple:
(x1,x2,x3,x4), where xn may be a number (32 bit if it's matter) or a wildcard '*' (any).
What approach may be taken for compact representation for this rules and fast lookups in runtime? It's looks like FSM, but are there any efficient approach for FSM state lookup?
If it's matter, rules are static, so inserting/deleting is not important at all, but lookup speed is crucial.
To add some details, the result of rule applying is a grant/deny verdict, so if there is a a more general rule that produces grant and less general rule that produces deny - the deny rule should be taken.
The task looks very usual and must be solved, so what to search? My first attempts didn't give me much.
My first idea is to reorder the columns of the rules to have a biggest possible component with '*' at the end, like
(x1,x2,x3,*)
(x1,x2,*,*)
(x1,*,*,*)
exceptions
(*,x2,*,x3)
...
handle the "suffixed" part with tries of some sort, and then handle the reminder somehow.
