Constructing a BPE Tokenization DFA
Many natural language processing systems operate over tokenizations of text to address the open-vocabulary problem. In this paper, we give and analyze an algorithm for the efficient construction of deterministic finite automata (DFA) designed to operate directly on tokenizations produced by the popular byte pair encoding (BPE) technique. This makes it possible to apply many existing techniques and algorithms to the tokenized case, such as pattern matching, equivalence checking of tokenization dictionaries, and composing tokenized languages in various ways. The construction preserves some key properties of the automaton, and we use this to establish asymptotic bounds on the state complexity of the automata that result. Finally, we demonstrate how to construct an input-deterministic (subsequential) string-to-string transducer which precisely describes the relationship between strings and their correct tokenizations.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Mutual Enhancement Between Global Tokens and Patch Tokens: From Theory to Practice
Accurate and effective discrete image tokenization is crucial for long image sequence processing. However, current methods rigidly compress all content at a fixed rate, ignoring the variable information density of images…
RepCodec: A Speech Representation Codec for Speech Tokenization
With recent rapid growth of large language models (LLMs), discrete speech tokenization has played an important role for injecting speech into LLMs. However, this discretization gives rise to a loss of information, conseq…
Language ModelingLanguage ModellingQuantizationSpeech TokenizationIs Tokenization Needed for Masked Particle Modelling?
In this work, we significantly enhance masked particle modeling (MPM), a self-supervised learning scheme for constructing highly expressive representations of unordered sets relevant to developing foundation models for h…
DecoderMissing ElementsSelf-Supervised LearningLICHEE: Improving Language Model Pre-training with Multi-grained Tokenization
Language model pre-training based on large corpora has achieved tremendous success in terms of constructing enriched contextual representations and has led to significant performance gains on a diverse range of Natural L…
Language ModelingLanguage ModellingNatural Language UnderstandingOn the Role of Discrete Tokenization in Visual Representation Learning
In the realm of self-supervised learning (SSL), masked image modeling (MIM) has gained popularity alongside contrastive learning methods. MIM involves reconstructing masked regions of input images using their unmasked po…
Contrastive LearningRepresentation LearningSelf-Supervised Learning