Paging Automata

• 1. Introduction
• 2. An overview from the user's viewpoint
• 3. Short API description
• 4. Internal representation of automata
• 5. Limits and limitations
• 6. Notes on performance
• 7. Future Directions
• 8. Acknowledgements
• 9. Availability
• 10. Bibliography

Large and complex automaton-based data structures may arise when dealing with massive data sets. These automata can be viewed as ways to extract information from those sets, as well as ways to put and maintain them in a form suitable for specific applications, like search engines or spelling checkers. In this second case, the automaton is not a temporary need, but one definitive format under which the data set (dictionary) will be maintained.

Developed in a first moment to apply statistical tests in biological sequences [10], biba is mainly a C programming library, but it also contains programs built over this library offered as applications. It is able to make user-level memory paging, in the same sense that this term is used in operating systems textbooks (see for instance Bach [1]). However, biba's paging implementation is not only a way to overcome physical memory limitations, but it is also and mainly an efficient way to permanently store automata on disk.

Paging will be a very interesting option in those cases where the automaton can compare to a large relational database, that resides on disk but is continuously being consulted and changed punctually along a large interval of time. An example we can think about is an automaton-based index for a large dynamic textual database, as glimpse [7] does.

We introduce the features of biba, through some examples. For now, the visible part of biba are just two programs that integrate the package, reduce and suffaut.

The reduced automaton that recognizes a set of words, explicited one per line in a file, can be built using the reduce tool, that implements the algorithm due to Revuz [8]:

    $ reduce words

The automaton just built resides in the pair of files a.aut.st (the states) and a.aut.ed (the edges). These are ordinary files, that you can copy, compress or transfer. Because of practical limitations that the user may need to deal with, we allow to split the files that contain an automaton in many parts, so one can combine the available areas of many filesystems, and take advantage of using disks in parallel. For instance, the following command will divide a.aut.ed in two parts, the first of them containing just 25 megabytes:

    $ biba -s 25 a.aut.ed a.aut-1.ed

Next we present suffaut, a program that builds the suffix automaton of a given word, using the algorithm due to Blumer et alli [2]. In this same example we show how one paging parameter (among others) can be controlled through options. In this case we're specifying that the maximum ratio between total virtual memory size and total physical (RAM) memory size is 5. Just like in the first example, the automaton will reside in the files a.aut.st and a.aut.ed. We chose a binary word (the file /bin/sh seen as a sequence of bytes):

    $ suffaut -p 5 -f /bin/sh
    word length: 300668
    states: 428275 (14 finals) edges: 636565
    ram pages: 1300 virtual pages: 2141

This command took 64 seconds to complete in a 486 100Mhz with 32 megabytes of main memory. By default suffaut allocates 5 megabytes of RAM before allowing the ratio between virtual and physical memory becomes larger than 1. As the page size is 4096, suffaut allocated 1300 RAM pages. The final sizes for files a.aut.st and a.aut.ed were 5.5 and 3.2 megabytes, so suffaut allocated 13 bytes per state and 5 bytes per edge. These numbers will be explained in the next section (note that the algorithm requires two additional 32-bit fields per state).

Now we'll combine these two programs in order to test the accuracy of both. Let's consider Good-de Bruijn words over the alphabet {0,1}. The scprit good generates such a word with parameter p, that is, a word w where each element of {0,1}^p occurs just once as a factor of w. The number of states of the suffix automaton of w can be theoretically computed as being 2^p+1-1 [10]. We can build this automaton using suffaut or reduce, and compare the results:

    $ good 7 | suffaut
    word length: 134
    states: 255 (8 finals) edges: 381

    $ good -s 7 | reduce
    states: 255 (8 finals) edges: 381

In order to generate the word, good uses the classical construction based on Eulerian Tours. When called with the -s switch, it generates the word and all its suffixes. This script is available with the biba distribution.

In the next two examples biba deals with natural language dictionaries and biological vocabularies. In both cases we're building reduced automata, in the first case for the entire br.ispell dictionary for brazilian portuguese [11] (just like done by Lucchesi and Kowaltowski in [5]), which contains 195539 entries (total size 2120562), and, in the second, for the blocks protein database [4] (109660 entries, 3249189 total size). The filter eb, which extracts the sequences from the database distribution file removing comments, is provided in the biba distribution.

    $ ispell -e vocab -d br | reduce
    states: 14119 edges: 36588
    ram pages: 1300 virtual pages: 1303

    $ eb | reduce -s 200000 -m 28 -c 28 -d 1000000
    states: 1318407, edges: 1401826
    ram pages: 6200 virtual pages: 6182

The first command took just 240 seconds to complete in the same 486 computer described. The second took 27 minutes. Note that this time may vary largely depending on the choice of the paging parameters. We're omitting the final size of the files a.aut.st and a.aut.ed because in these cases they're full of garbage. In fact, their sizes are not determined by the automaton size, but by the vocabulary size, because the algorithm first builds a trie (this behaviour may be partially avoided using a command-line option). Anyway, at the end of the construction, each state uses 9 bytes, and each edge uses 5 bytes.

The library can also be used for many other purposes, but develop and link programs with the biba library is a time-consuming exercise of C programming, so we offer a simplistic alternative that opens partially the library's internal functionality for scripts that can be quickly written using perl or similar languages.

    #!/usr/bin/perl

    use FileHandle;
    use IPC::Open2;
    $pid = open2(\*Reader,\*Writer,"biba -w $ARGV[1]");
    Writer->autoflush();

    while (<stdin>) {
        print (Writer "r\ns$_");
        if ( =~ /^1/) {
            print $_;
        }
    }
    close(F);

For the programmer we provide a short description of the C API (for a detailed description please refer the man pages).. Just like we said that automata are like files to the user, they are like files to the programmer too. So deal with automata using this API is like deal with files through the C language library. Automata handles are provided, and they can be used to create or specify an existing automaton, and to subsequently work on it.

create_aut	similar to create(2)
register_aut	similar to open(2)
close_aut	similar to close(2)

In order to deal with automata states and edges, very simple services are provided. Each one require the specification of a handle, amongst other specific parameters. The complete list follows:

new_state	alloc a new state
set_final	set (to a given value) the state final flag
is_final	read the state final flag
set_dest	set the destination of an edge
dest	read the destination of an edge
stdeg	read the output degree of a state
next_dest	visit all edges leaving a given state
clone	clone a state

For low level configuration and session recovery support, the following services are provided:

States and edges reside on separate data structures, that grow as needed (currently they cannot shrink). The main goal of these data structures is to save memory, because we want to be able to represent large automata, so we need to try to minimize paging at the expense of a larger cost of in-memory operations.

The data structure that represents states is nothing more than a large array. Each entry of this array is a "state", composed of fixed fields (its output degree, a flag to identify if the state is final, and a pointer to the structure that represents its edges) and application-dependent fields, like flags and counters.

The data structure that represents the edges is an array too. It limits the alphabet size to 256, and currently does not support nondeterministic automata. In order to represent the edges that leave a state with output degree d, where d is in the range 0..256, it allocates just d contiguous entries of the array of edges. The allocation routines guarantee that these d entries reside on the same page, a fundamental property, needed to avoid performance degradation. Each edge is composed by a label field and a destination field which points to a state. Application-specific fields are not allowed.

To allocate a state is no more than increase by 1 the current size of the array of states, and manage the necessary changes in the data structure, which may include the allocation of a new page. Inserting an edge leaving a state demands the allocation of d contiguous entries of the array of edges (best-fit is used), where d is the resulting output degree. This is managed by the maintenance of free lists of free areas within this array, one per each possible free area size.

Both arrays reside on disk, but at each moment only some of their pages are loaded into memory, accordingly to the paging routines. Each state and each edge uses just 40 bits to be represented (the size of a state may be larger depending on the presence of application-specific fields). This number is due to current limit on the alphabet size, that cannot be larger than 256, plus the choice of a 31-bit addressing limit for states and edges. So if n is the sum of the number of states and edges of an automaton, then the total disk size needed to represent it will be 5n bytes.

• The states of one automaton can use a virtual space of at most 8 gigabytes. The same limit applies to its edges (this is imposed by a page addressing limit).
• Paging makes unfeasible to adopt a platform-independent representation of data, so when moving automata from one computer to another, conversion tools may be needed (such tools are not currently available).
• To avoid performance degradation, it is not currently allowed to attach application-specific fields to edges nor to use alphabets with sizes larger than 256.
• Nondeterministic automata are not currently supported.
• Automata splitting in many files is currently limited to 10 parts for the states and 10 parts for the edges. So an automaton may be split in at most 20 files.

6. Notes on performance

The paging scheme by itself represents a performance penalty, because of the additional memory and time comsumption needed to manage and detect page faults and access memory. In a user-level paging scheme like the one implemented in biba, this penalty is more significant because we cannot use, as the operating system kernel does, hardware features that make the paging more efficient (and unportable).

In order to estimate the time penalty, we depend on more programming effort. Using the suffix array tool in development (details in the next section) we'll be able to make it.

Regarding edges representation, some enhancements are needed, like support for nondeterministic automata. Changes are being planned in order to allow the addition of application-specific fields to edges, as well as the usage of larger alphabets and/or support automata where the labels of the edges are words over a given alphabet.

A search tool for WWW servers similar to glimpse [7] will be released soon. It currently uses an index based on GNU gdbm, but an automaton-based alternative is being added.

More general data structures besides automata can be represented using biba. We plan to release soon a program that builds the suffix array, and implements both the refinement algorithm due to Manber and Myers [6] and the external sorting algorithm due to Gonnet [3]. We wrote this program some time ago, and it is currently being adapted to use the biba paging scheme.

[1] Maurice J. Bach. The Design of the Unix Operating System. Prentice Hall, 1986.

[2] A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler, M. T. Chen and J. Seiferas, The smallest automaton recognizing the subwords of a text. Theoretical Computer Science, vol. 40, pp 31-55, 1985.

[3] Gaston H. Gonnet, Ricardo A. Baeza-Yates and T. Snider. Lexicographical indices for text: inverted files vs. PAT trees. TR OED-91-01, UW Centre for the New Oxford English Dictionary, University of Waterloo, 1991.

[4] S Henikoff and JG Henikoff. Automated assembly of protein blocks for database searching, Nucleic Acids Res. 19:6565-6572, 1991.

[5] Cláudio L. Lucchesi and Tomasz Kowaltowski, Applications of Finite Automata Representing Large Vocabularies, in Software Practice and Experience, Vol. 23, pp. 15-30, 1993.

[6] Udi Manber and Gene Myers. Suffix arrays: A new method for on-line string searches. SIAM Journal on Computing, 22(5):935-948, October 1993.

[7] Udi Manber and Sun Wu, GLIMPSE: A Tool to Search Through Entire File Systems, Usenix Winter 1994 Technical Conference, San Francisco pp. 23-32, 1994.

[8] Dominique Revuz, Minimization of Acyclic Deterministic Automata in Linear Time. Theoretical Computer Science, vol. 92 pp 181-189, 1992.

[9] Edward N. Trifonov, Making sense of the human genome. Structure & Methods, 1:69-77, 1990.

[10] Ricardo Ueda Karpischek. The Suffix Automaton (in portuguese). Master Thesis, University of São Paulo, 1993.

[11] Ricardo Ueda Karpischek, br.ispell, a brazilian portuguese dictionary for ispell, http://www.ime.usp.br/~ueda/br.ispell/, 1995.