Online Information Compression of Finite-Valued Networks via Finite Automata Approach and Reinforcement Learning

The storage and transmission of large-scale data are recognized as significant challenges that incur substantial costs due to the massive volume of information involved. Lossless compression offers a potential solution to this problem. In this work, we explore the online lossless state compression (LSC) in finite-valued networks by effectively combining the methods of finite state automata and reinforcement learning. To achieve online lossless compression, the concept of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i>-step compressed walks (state sequences) is introduced. By constructing a finite state automaton to identify all insertable walks, the recoverability conditions of online lossless compression are presented. For any given compressed walk <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">w’_c</i>, one algorithm is proposed to find a minimal recoverable <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k_min</i>-step compressed walk, thereby improving the compression ratio. Furthermore, it can be found that if a compressed walk keeps recoverability, adding more states to it would not break this property. Additionally, a model-free reinforcement learning framework based on Q-learning is developed to obtain globally minimal recoverable compressed walks. Finally, a numerical example is given to demonstrate the efficiency of the proposed online lossless compression scheme, achieving a compression ratio of 44.4%.