dr hab. inż. Jan Daciuk | Gdańsk University of Technology

This chapter describes language models used in speech recognition, It starts by indicating the role and the place of language models in speech recognition. Mesures used to compare language models follow. An overview of n-gram, syntactic, semantic, and neural models is given. It is accompanied by a list of popular software.

We present a new library of functions that construct minimal, acyclic, deterministic, finite-state automata in the same format as the author's fsa package, and also accepted by the author's fadd library of functions that use finite-state automata as dictionaries in natural language processing.

We present a method to store additional information in a minimal automaton so that it is possible to compute a corresponding tree node number for a state. The number can then be used to retrieve additional information. The method works for minimal (and any other) deterministic acyclic finite state automata (DFAs). We also show how to compute the inverse mapping.

This book is conceived as an effort to gather all algorithms and methods developed by the author of the book that concern three aspects of optimization of automata: incrementality, hashing and compression. Some related algorithms and methods are given as well when they are needed to complete the picture.

Rozdział przedstawia algorytmy przyrostowego i półprzyrostowego tworzenia minimalnych deterministycznych automatów skończonych.