On the Compression of Lexicon Transducers

Marco Cognetta, Cyril Allauzen, Michael Riley


Abstract
In finite-state language processing pipelines, a lexicon is often a key component. It needs to be comprehensive to ensure accuracy, reducing out-of-vocabulary misses. However, in memory-constrained environments (e.g., mobile phones), the size of the component automata must be kept small. Indeed, a delicate balance between comprehensiveness, speed, and memory must be struck to conform to device requirements while providing a good user experience.In this paper, we describe a compression scheme for lexicons when represented as finite-state transducers. We efficiently encode the graph of the transducer while storing transition labels separately. The graph encoding scheme is based on the LOUDS (Level Order Unary Degree Sequence) tree representation, which has constant time tree traversal for queries while being information-theoretically optimal in space. We find that our encoding is near the theoretical lower bound for such graphs and substantially outperforms more traditional representations in space while remaining competitive in latency benchmarks.
Anthology ID:
W19-3105
Volume:
Proceedings of the 14th International Conference on Finite-State Methods and Natural Language Processing
Month:
September
Year:
2019
Address:
Dresden, Germany
Editors:
Heiko Vogler, Andreas Maletti
Venue:
FSMNLP
SIG:
SIGFSM
Publisher:
Association for Computational Linguistics
Note:
Pages:
18–26
Language:
URL:
https://aclanthology.org/W19-3105
DOI:
10.18653/v1/W19-3105
Bibkey:
Cite (ACL):
Marco Cognetta, Cyril Allauzen, and Michael Riley. 2019. On the Compression of Lexicon Transducers. In Proceedings of the 14th International Conference on Finite-State Methods and Natural Language Processing, pages 18–26, Dresden, Germany. Association for Computational Linguistics.
Cite (Informal):
On the Compression of Lexicon Transducers (Cognetta et al., FSMNLP 2019)
Copy Citation:
PDF:
https://aclanthology.org/W19-3105.pdf