Tokenization: Hardness and Bicriteria Approximation Algorithms
Organizations: Iowa State University. · University of Nebraska–Lincoln.
Abstract
We study Binary Tokenization: given a corpus of binary strings over and a vocabulary budget , select at most substrings (called vocabulary) to minimize the total number of tokens needed to represent the corpus. The primitive symbols and are always available, and each document must be segmented separately. Letting denote the total corpus length and for the maximum document length, we prove that, for every fixed , Binary Tokenization problem does not have polynomial-time -approximation algorithms unless . To complement the hardness result, we give a polynomial-time -bicriteria algorithm, with : The algorithm outputs a vocabulary of size at most with number of tokens at most , where is the optimal number of tokens under the original budget . We also study a storage-budget variant, in which the sum of the selected substrings' lengths is bounded by . For , we obtain an -bicriteria approximation algorithm.