3 papers
cs.CL2024
Vaporetto: Efficient Japanese Tokenization Based on Improved Pointwise Linear Classification
Koichi Akabe, Shunsuke Kanda, Yusuke Oda +1
This paper proposes an approach to improve the runtime efficiency of Japanese tokenization based on the pointwise linear classification (PLC) framework, which formulates the whole…
cs.DS2024
NP-Completeness for the Space-Optimality of Double-Array Tries
Hideo Bannai, Keisuke Goto, Shunsuke Kanda +1
Indexing a set of strings for prefix search or membership queries is a fundamental task with many applications such as information retrieval or database systems. A classic abstract…
cs.DS2022
Computing NP-hard Repetitiveness Measures via MAX-SAT
Hideo Bannai, Keisuke Goto, Masakazu Ishihata +3
Repetitiveness measures reveal profound characteristics of datasets, and give rise to compressed data structures and algorithms working in compressed space. Alas, the computation o…