0
$\begingroup$

In a program I am writing, I represent an array of strings as a long string and have pointers point at the various substrings to present my array. E.g.

str_array = struc string_array
   long_str = "abcdefab"
   pointer_array = [(start = 0, len = 3), (start = 3, len = 3), (start = 6, len=2))
end

So str_array = ["abc", "def", "ab"], but notice that I can actually compress the long string so by getting rid of "ab" at the end. E.g.

str_array2 = struc string_array
   long_str = "abcdef"
   pointer_array = [(start = 0, len = 3), (start = 3, len = 3), (start = 0, len=2))
end

and note that str_array2 is also ["abc", "def", "ab"] === str_array.

What's this type of compresssion callled in computer science? I assume there's already literature on this type of algorithms?

$\endgroup$
  • 1
    $\begingroup$ the closest compression I see would be related to lz77 and lz78 algorithms. $\endgroup$ – Phillip Williams Sep 15 at 1:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.