arXiv:2611.15074v1 cs.DS

토큰화: 난해성과 이중 기준 근사 알고리즘

Tokenization: Hardness and Bicriteria Approximation Algorithms

Atieh Bastan, Xiaoling He, A. Pavan, N. V. Vinodchandran

제출 2026-11-11

한국어 초록

우리는 이진 토큰화를 연구한다. 이는 $\{0,1\}$ 위의 이진 문자열 코퍼스와 어휘 예산 $K$가 주어졌을 때, 코퍼스를 표현하는 데 필요한 전체 토큰 수를 최소화하도록 최대 $K$개의 부분 문자열(어휘)을 선택하는 문제이다. 기본 기호 $0$과 $1$은 항상 사용할 수 있으며, 각 문서는 별도로 분할되어야 한다. $n$을 전체 코퍼스 길이, $M$을 최대 문서 길이라 할 때, 모든 고정된 $\varepsilon\in(0,1)$에 대해 $\mathsf{P}=\mathsf{NP}$가 아닌 한 이진 토큰화 문제에는 다항 시간 $n^{1-\varepsilon}$-근사 알고리즘이 존재하지 않음을 증명한다. 이 난해성 결과를 보완하기 위해 $\gamma = \sqrt{M}\log n$인 다항 시간 $(\gamma,\gamma)$-이중 기준 알고리즘을 제시한다. 이 알고리즘은 크기가 최대 $\gamma K$인 어휘를 출력하며 토큰 수는 최대 $\gamma {\rm OPT}_K$이다. 여기서 ${\rm OPT}_K$는 원래 예산 $K$ 하에서의 최적 토큰 수이다. 또한 선택된 부분 문자열 길이의 합이 $B$로 제한되는 저장 예산 변형도 연구한다. $2\le B<n$에 대해 $(O(\log n\log B),O(\log n\log B))$-이중 기준 근사 알고리즘을 얻는다.

원문 초록

We study Binary Tokenization: given a corpus of binary strings over $\{0,1\}$ and a vocabulary budget $K$, select at most $K$ substrings (called vocabulary) to minimize the total number of tokens needed to represent the corpus. The primitive symbols $0$ and $1$ are always available, and each document must be segmented separately. Letting $n$ denote the total corpus length and $M$ for the maximum document length, we prove that, for every fixed $\varepsilon\in(0,1)$, Binary Tokenization problem does not have polynomial-time $n^{1-\varepsilon}$-approximation algorithms unless $\mathsf{P}=\mathsf{NP}$. To complement the hardness result, we give a polynomial-time $(\gamma,\gamma)$-bicriteria algorithm, with $\gamma = \sqrt{M}\log n$: The algorithm outputs a vocabulary of size at most $\gamma K$ with number of tokens at most $\gamma {\rm OPT}_K$, where ${\rm OPT}_K$ is the optimal number of tokens under the original budget $K$. We also study a storage-budget variant, in which the sum of the selected substrings' lengths is bounded by $B$. For $2\le B<n$, we obtain an $(O(\log n\log B),O(\log n\log B))$-bicriteria approximation algorithm.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2611.15074v1

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.