본 논문은 토크나이저를 최적화 문제로 공식화하여, 정점 덮개 문제로부터의 간단한 환원을 통해 NP-hard임을 보여줍니다. 그리고 다항 시간 그리디 알고리즘인 GreedTok을 제안합니다. 이 공식은 잘 연구된 가중 최대 범위 문제로 자연스럽게 완화되며, 간단한 (1 - 1/e)-근사 알고리즘인 GreedWMC를 가지고 있습니다. 실제 말뭉치에 대한 실험적 평가를 통해 GreedTok이 BPE와 Unigram보다 압축 성능이 우수하며 GreedWMC와 비슷한 범위 점수를 달성함을 보여줍니다. 마지막으로, 10억 개 매개변수를 가진 두 개의 트랜스포머 기반 언어 모델에 대한 광범위한 사전 훈련을 통해 토크나이저로 BPE와 GreedTok을 비교한 결과, 전체 데이터셋 비율이나 전체 훈련 토큰 수를 제어하더라도 GreedTok이 바이트당 비트 수가 더 낮음을 보여줍니다.
