On the basis of the PATRICIA suffix tree, the author presents a simple way to implement a data structure for searching and updating the finite size dictionary in compression algorithms. For updating, each time a new entry is inserted into the tree, the internal node keeps the latest position rather than its old one. As in the normal PATRICIA tree, all the external nodes are put into a buffer, which shifts circularly. After the leaf nodes are exhausted, the oldest leaf node is deleted and put into the tree to represent new entries, and its old position is kept with a pointer. In this way, the updating procedure for all the internal nodes can be bypassed. Therefore, whenever the finite size dictionary is full, the spaces below the points of old positions can be replaced by new input data.
展开▼
