# Finding Patterns in Signals Using Lossy Text Compression
### Related Work  
**Reverse Engineering.** There are many systems and applications that suggest imitating remote controllers. For example, a \"universal remote controller\" can record IR signals and send them again by pressing on the corresponding button of this remote controller. However, such a simple controller with a small number of states, cannot replace the remote controller of, e.g., a common quadcopter with seven channels whose protocol can be used to generate unbounded types of signals.  
**String Algorithms.** The notion of runs and periodicity of strings is at the core of many stringology questions [(5; 6)]. It constitutes a fundamental area of string combinatorics due to important applications of text algorithms, data compression, biological sequences analysis, music analysis, etc. The notion of runs was introduced by [PERSON], [PERSON], and [PERSON] [(5)], who showed that Fibonacci words contain only a linear number of runs according to their length. [PERSON] and [PERSON] [(6)] (see also [(7)], Chapter 8) proved that the property holds for any string and designed an algorithm to compute all runs in a string, which extends previous algorithms [(8; 9)]. Other methods are presented in [(7; 10; 11; 12; 13; 14; 15)].  
All of the above mentioned works have focused on exact runs; i.e., runs that include exactly the same repeated period. Other works focused on approximate runs. For example, when a string \(S\) is a concatenation of a non-empty substrings, by the modification of at most \(k\) letters, they form an exact run. This problem was widely researched [(16; 17; 18; 19; 20)]. However, none of these previous works have focused on recursive runs, as defined in this paper.  
The RRLE compression presented in this paper is a novel definition of recursive approximate runs. Informally, our problem is an optimization problem that looks for approximate runs that include  
Figure 1: The recursive run-length encoding (RRLE) tree of the string (\(abcccabccgghhekmllffccdcccd\)), which is compressed from 29 letters to 22 (12 letters and 10 counters).  
a period that may be a run by autonomously. In addition to run length encoding, RRLE is also closely related to run-length straight line program (RLSLP) compression scheme, which is an extension of straight line programs (SLPs) [21; 22].  
There are many other compression schemes of strings, such as SLP [23], macro schemes [24], and LZ77 [25], that might be even more useful than the RRLE suggested in this paper. However, the main goal of the study was not to simply compress strings, but actually extract patterns from noisy strings. This was the motivation for the approximation algorithm that is our main result in Section 3.  
In the case of communication protocols, the idea of using recursive trees of patterns is important and more relevant than pointers that are more relevant to text documents. In addition, RRLE is not based on the longest repeated factor (substring), but rather based on finding repeated substrings that are well compressed by themselves.  
This version of finding recursive approximate runs is challenging, since most known techniques for finding exact or approximate runs cannot be used here without introducing exponential running time. To the best of our knowledge, there are no known efficient (polynomial time) algorithms for the RRLE problem.  
**Roadmap:** In Section 2, we provide the basic stringology notation needed for the algorithms, and a full definitions of the problem we are solving. In Section 3, we present our reverse engineering algorithms, which are the algorithms for exact and lossy text compression. In Section 4 we explain how we can apply these algorithms on our system. Then, in Section 5, we give an example of a protocol, and present in detail our reverse engineering system. Finally, in Section 7 we conclude this paper, and discuss some interesting directions for future work.