contents index next

13. fsa_dict: Dictionaries and Perfect Hashes

This module provides predicates to create (acyclic) finite automata on the basis of a set of strings. This can be used to implement word lists and perfect hashes.

A perfect hash is a hash in which each key is associated with a unique hash code: the rank of the key in the alphabetic ordering of the set of keys. This is possible by providing an enumeration of all keys in advance. For instance, if you provided the strings:

then a string-to-weight transducer will be constructed which maps achter to 0, achterdeur to 1, voor to 2, and voordeur to 3.

13.1. List of Predicates

This section lists the predicates defined by this module.

13.1.1. fsa_dict_to_perfect_hash(+ListOfStrings,-Fa)

A string-to-weight transducer Fa will be constructed implementing the perfect hash for the ListOfStrings; i.e. the transducer maps each string to its rank (in alphabetic order), and does not accept any string not listed in ListOfStrings. The transducer is (w_)minimal.

13.1.2. fsa_dict_to_perfect_hash_file(+FileIn,+FileOut)

FileIn is assumed to contain a set of strings: each line is a string. A string-to-weight transducer will be written to FileOut implementing the perfect hash for the set of strings read from FileIn: i.e. the transducer maps each string to its rank (in alphabetic order), and does not accept any string not listed in FileIn. The transducer is (w_)minimal.

13.1.3. fsa_dict_to_fsa(+ListOfStrings,-Fa)

A minimal recognizer Fa will be constructed recognizing exactly the strings in ListOfStrings

13.1.4. fsa_dict_to_fsa_file(+FileIn,+FileOut)

FileIn is assumed to contain a set of strings: each line is a string. A minimal automaton recognizing exactly those strings is written to FileOut

contents index next