Extend_Fa Documentation

This page contains the Extend_Fa Package documentation.

The extend_fa Module

Module for pattern match: algorithm for Extending Finite Automaton.

class netbench.pattern_match.algorithms.experimental.extend_fa.extend_fa.extend_fa

Bases: netbench.pattern_match.b_nfa.b_nfa

Class for Extending Finite Automaton.

SaveToFile(file_name)

Make file which represent the Extend automaton. This file will be input into algorithm written in C language.

Parameter:file_name – Name of output file

NOTE: This method is deprecated. Use save_to_file().

change_state_numbering()
Change state numbering back to linear (0, 1, 2, 3, 4, 5, ...). Because of removing some states and for better work in C algorithm.
compute(file_name)

Fuction for make Extend FA from RE in file_name.

Parameter:file_name (string) – Name of input file
discover_before_part(file_name)

Discover string which is before .{n} like pattern.

Parameter:file_name – Name of input file
discover_start_state_counting()
Discover first NFA state from which is begin counting.
get_state_num()

Return number of states in Extend automaton.

Returns:Number of states in Extend automaton
Return type:int
get_trans_num()

Return number of transitions in Extend automaton.

Returns:Number of transitions in Extend automaton
Return type:int
make_ext_fa(file_name)

Fuction for make Extended FA from RE in file_name.

Parameter:file_name – Name of input file
remove_excessively_states(file_name)

Remove states which are excessively (because of queer creation NFA).

Parameter:file_name – Name of input file
report_memory_naive()

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) For Extend is: basic + Mem(cnt) + (State * Sym * 2/8)

Returns:Returns number of bytes.
Return type:int
report_memory_optimal()

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). For Extend is: basic + Mem(cnt) + (Tran*2/8).

Returns:Returns number of bytes.
Return type:int
save_to_file(file_name)

Make file which represent the Extend automaton. This file will be input into algorithm written in C language.

Parameter:file_name – Name of output file
show(file_name)

Print states, alphabet, start, transitions, final, flags of automat. And save graphviz dot file, representing graphical structure of automat.

Parameter:file_name – Name of output file
sort_transitions()
Make dictionary of sorted transitions, key is number of state.
supercede_counting_states()
Supercede N counting states by one state with special ability.

The test_extend_fa Module

class netbench.pattern_match.algorithms.experimental.extend_fa.test_extend_fa.test_extend_fa(methodName='runTest')

Bases: unittest.TestCase

Test module for class extend_fa.

test_compute()
compute()
test_report_memory_naive()
report_memory_naive()
test_report_memory_optimal()
report_memory_optimal()
test_save_to_file()
save_to_file()

Table Of Contents

Previous topic

Nfa_Split Documentation

Next topic

Dcam Documentation

This Page