last update Feb 4 2003
Biba is a package designed to deal with representations of large automata. It offers a library able to build, even on a modest computer, automata where the sum of the numbers of states and edges achieves one billion or more. Two applications that use this library are provided as examples. They build the reduced automaton for a given vocabulary, and the suffix automaton of a given word. New programs can be developed using this library. In order to overcome physical memory limitations, biba implements a paging scheme, in such a way that the automata really reside on disk, making possible their permanent storage. Through a simple interface suited for perl, small scripts can be easily written to use and extract informations from these automata.
The sources and documentation are available for download, usage and redistribution under the terms of the GNU GPL as ftp://ftp.ime.usp.br/pub/ueda/biba/biba-0.9c.tar.gz . The perl scripts presented and cited in the extended abstract are currently unavailable.
Construction of the reduced automaton of the Blocks Database
The time required by this task may vary largely depending on the choice of paging parameters. The computer used is a simple 486 100MHz with 32 megabytes of main memory. Best performance on this machine was achieved as follows:
$ eb | reduce -s 200000 -m 28 -c 28 -d 1000000
states: 1318407, edges: 1401826
ram pages: 6200 virtual pages: 6182
The input contains 109,660 entries (words) and total size 3,249,189. The command took 27 minutes to complete, and the final size of the files a.aut.st and a.aut.ed were 17 and 8 megabytes. Note that these sizes include deallocated areas.
The options -m and -c specify the maximum and comfortable limits of memory that reduce is allowed to alloc. The -s option is used to enlarge the sorting buffer, used when detecting equivalences, and the -d option informs that an automaton reduction is to be performed at each 1,000,000 insertions.
biba(1) man page.
biba(3) man page.
reduce(1) man page.
suffaut(1) man page.