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
- 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)
- PDF:
- https://preview.aclanthology.org/naacl24-info/W19-3105.pdf