As pointed out: it's done, look for algorithmics over grammar-based compression. Querying and search is one of the operation that is doable on compressed data.

As pointed out: it's done, look for algorithmics over grammar-based compression. Querying and search is one of the operation that is doable on compressed data. See Algorithmics on SLP-compressed strings: A survey (Markus Lohrey) (https://www.degruyter.com/document/doi/10.1515/gcc-2012-0016/html https://www.degruyter.com/document/doi/10.1515/gcc-2012-0016...) Implementation-wise, you probably loose on the first goal, gain on the second and third (simpler, faster implementations), if you make the fourth one easy to implement.