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 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article