Welcome to Biba


[Home] [Dissertação] [Linux] [Conjugue] [br.ispell] [axw3] [uplink]

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.

Package Download

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.

Article Remarks

An Article on Biba is available. This article can be downloaded in PDF format from Springer Verlag's site (LNCS 1660). The following remarks apply to an earlier version of the article:

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.

Man Pages

biba(1) man page.
biba(3) man page.
reduce(1) man page.
suffaut(1) man page.