Title: Ant colonial-based approach for the minimal full trie problem
Authors: Meng Zhang; Yi Zhang
Addresses: College of Computer Science and Technology, Jilin University, Changchun, China ' Department of Computer Science, Jilin Business and Technology College, Changchun, China
Abstract: A trie of a set of strings P is a digital search tree in which each leaf corresponds to a string in P. Reducing the storage requirement of tries is one of the major problems of trie. One method for reducing the space required is to change the order of symbol testing. Unfortunately, the problem of finding an ordering which guarantees a minimum-size trie is NP-complete. We present a trie minimisation algorithm using ant colony optimisation (ACO). We introduce the dynamic graph and the ant teams to ACO that works out the solution by a group of cooperating ants. Experiments show that our approach generates tries that are smaller than that generated by the greedy method.
Keywords: ant colony; trie; optimisation.
DOI: 10.1504/IJBIC.2017.084331
International Journal of Bio-Inspired Computation, 2017 Vol.9 No.4, pp.235 - 239
Received: 09 Feb 2017
Accepted: 09 Mar 2017
Published online: 05 Jun 2017 *