This page contains the Phf_Dfa Package documentation.
Bases: netbench.pattern_match.b_dfa.b_dfa
Class for the DFA based on perfect hashing. Extension with faulty transition table is also implemented. To enable this extension, use method enable_faulty_transitions.
Kastil, J., Korenek, J., Lengal, O.: Methodology for Fast Pattern Matching by Deterministic Finite Automaton with Perfect Hashing, In: 12th EUROMICRO Conference on Digital System Design DSD 2009, Patras, GR, IEEE CS, 2009, p. 823-289, ISBN 978-0-7695-3782-5 URL: http://www.fit.vutbr.cz/research/view_pub.php?id=9054
Kastil, J., Korenek, J.: High Speed Pattern Matching Algorithm Based on Deterministic Finite Automata with Faulty Transition Table, In: Proceedings of the 6th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, La Jolla, US, ACM, 2010, p. 2, ISBN 978-1-4503-0379-8 URL: http://www.fit.vutbr.cz/research/view_pub.php?id=9380
This class uses bitstring module: http://code.google.com/p/python-bitstring/
This method computes DFA with Perfect hashing.
Note that PHF table generation may fail, depending on PHF class parameters (limit, ratio), so _compute may not be set to True.
Compute the symbol accepting the beggining of input string.
Parameters: |
|
---|---|
Returns: | ID of found symbol or -1 if no symbol was found and the remainder of input string. |
Return type: | tuple(string, int) |
This function sets the fallback state. This requires fully defined automaton! If state is not specified, the one with most incoming transitions is used. Warning about fully defined automaton is printed on stdout, unless the parameter warning is set to False. _compute is set to False.
Parameters: |
|
---|
Enable faulty transition table. Uniform hash function is used to compress the transition representation. If small hash size is chosen, collisions and faults in pattern matching may occure. PHF table must be (re)generated after enabling faulty transitions (method generate_PHF_table() or compute()). This method sets _compute to False.
Parameters: |
|
---|
This method generates the PHF table containing the transition table.
2 bits required by bdz algorithm
(empty lines contain maximum symbol and state id, computed from symbol_bits and state_bits)
next state
compressed value of transition representation (faulty trans)
Returns: | True if table was generated succesfully. False otherwise. |
---|---|
Return type: | Boolean |
This function returns 2-tuple of integers. First integer is the number of bit used for the representation of the state. The second integer is a number of bits representing symbol in the transition table. State and symbol together represents the key to the transition table.
Returns: | Table parameters - number of bits used for the representation of state and symbol. |
---|---|
Return type: | tuple(int, int) |
Experimental code, intended only for internal use. This function creates text file containing binary representation of the transition table.
Parameter: | FileName (string) – The name of output file. |
---|
Remove all transitions to given state in nfa_data _automaton1. _automaton is unchanged, so dfa algorithms used in compute (like determinization or minimize) are working. This method should only be called from compute() and it sets _compute to False.
Parameter: | state (int) – ID of the fallback state. All transitions to this state will be removed. |
---|
Report consumed memory in bytes. Naive mapping algorithm is used (2D array). Basic algorithm for this variant of mapping is: M = |states| * |alphabet| * ceil(log(|states| + 1, 2) / 8)
Returns: | Returns number of bytes. |
---|---|
Return type: | int |
Report consumed memory in bytes. Optimal mapping algorithm is used (with oracle). Basic algorithm for this variant of mapping is: M = |transitions| * ceil(log(|states|, 2) / 8)
Returns: | Returns number of bytes. |
---|---|
Return type: | int |
Report consumed memory in bytes - the size of PHF table.
Returns: | Size of PHF table in bytes. |
---|---|
Return type: | int |
Search for the pattern in the given string.
Parameters: |
|
---|---|
Returns: | Bitmap of matched regular expressions. |
Return type: | list(int) |
Set the PHF class for PHF table generation. _compute is set to False.
Parameter: | phf_class (bdz()) – Class implementing the perfect hash function |
---|
This function sets the number of bits representing the state and symbol in the transition table. The parameter is a 2-tuple of integers. The first one sets the size of the state representation and the second position represents the size of symbol. NOTE: number of states/symbols must be less than 2 ** state_bits/symbol_bits !
Parameter: | bit_nums (tuple(int, int)) – Table parameters - number of bits used for the representation of state and symbol. |
---|
Validate given transition. If faulty transitions are enabled, validation is made based on the compressed value and the result may be faulty. In that case, counter self.bad_transitions is incremented and collision is stored in dictionary self.collisions.
Parameter: | tran (tuple(string, string)) – Representation of transition to be validated. |
---|---|
Returns: | True if the transition is valid in this automaton. Otherwise False is returned. |
Return type: | boolean |
Bases: unittest.TestCase
This class tests implementation of the algorithm PHF_DFA.