BSPM:A NEW MECHANISM FOR “OVERLAP-MATCHING EXPRESSIONS”IN DPI

Nowadays, using Deterministic Finite Automata (DFA) or Non-deterministic Finite Automata (NFA) to parse regular expressions is the most popular way for Deep Packet Inspection (DPI), and the research about DPI focuses on the improvement of DFA to reduce memory. However, most of the existing literature ignores a special kind of "overlap-matching expression", which causes states explosion and takes quite a large part in the DPI rules. To solve this problem, in this paper a new mechanism is proposed based on bitmap. We start with a simple regular expression to describe "overlap-matching expressions" and state the problem. Then, after calculating the terrible number of exploded states for this kind of expressions, the procedure of Bitmap-based Soft Parallel Mechanism (BSPM) is described. Based on BSPM, we discuss all the different types of "overlap-matching ex- pressions" and give optimization suggestions of them separately. Finally, experiment results prove that BSPM can give an excellent performance on solving the problem stated above, and the optimization suggestions are also effective for the memory reduction on all types of "overlap-matching expressions".

Text Compression Based on Letter’s Prefix in the Word

Huffman[Huffman(1952)]encoding is one of the most known compression algorithms.In its basic use,only one encoding is given for the same letter in text to compress.In this paper,a text compression algorithm that is based on Huffman encoding is proposed.Huffman encoding is used to give different encodings for the same letter depending on the prefix preceding it in the word.A deterministic finite automaton(DFA)that recognizes the words of the text is constructed.This DFA records the frequencies for letters that label the transitions.Every state will correspond to one of the prefixes of the words of the text.For every state,a different Huffman encoding is defined for the letters that label the transitions leaving that state.These Huffman encodings are then used to encode the letters of the words in the text.This algorithm was implemented and experimental study showed significant reduction in compression ratio over the basic Huffman encoding.However,more time is needed to construct these codes.

Some Aspects of Synchronization of DFA

A word w is called synchronizing （recurrent, reset, directable） word of deterministic finite automata （DFA） if w brings all states of the automaton to a unique state. According to the famous conjecture of Cerny from 1964, every n-state synchronizing automaton possesses a synchronizing word of length at most （n - 1）2. The problem is still open. It will be proved that the Cerny conjecture holds good for synchronizing DFA with transition monoid having no involutions and for every n-state （n 〉 2） synchronizing DFA with transition monoid having only trivial subgroups the minimal length of synchronizing word is not greater than （n - 1）2/2. The last important class of DFA involved and studied by Schutzenberger is called aperiodic; its automata accept precisely star-free languages. Some properties of an arbitrary synchronizing DFA were established.