One Bit-Flipping/Insertion/Deletion Correcting Methods for Substrings of Binary Circular String
Takahiro Ota, Keita Kamiya, Akiko Manada · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2025
Compression by Substring Enumeration (CSE), which is one of the lossless data compression algorithms, and various versions of CSE have been proposed. In encoding of CSE, substrings of given fixed length and their frequencies within circular string for an input string are output as a codeword. The circular string is made by connecting the first symbol and the last symbol of an input string. In decoding of CSE, the circular string is reconstructed from its substrings and their frequencies. Furthermore, the minimum length of substrings for which the decoding does reconstruct the circular string has been proved, together with a reconstruction algorithm. However, the algorithm requires substrings to have no errors.