How to represent (serialise) an arbitrarily nested array, as a one-dimensional array of values (and meta-data) so that the original nested array and it's structure can be recreated from the serialised one-dimensional array?
I'm looking for a space efficient algorithms for this problem.
For example:
[
[
[1, 2, 3, 4]
],
[
[5, 6, 7, 8],
[9, 10]
]
]
Should be serialised / deserialised to / from something like this
[/* elements of meta data* /, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
CodePudding user response:
You could represent a nested array with a sequence that first contains the length of that array (also providing the information that the following content is a sub-array) and then the elements themselves.
If you only have positive numbers as your values, but can store negative numbers, you could use negative numbers as the indicator for sub-arrays (if not, you can of course just use an offset O, which is the highest number you want to store, and treat all numbers greater then O as indicator for a new sub-array). The serialized version of your example would then look like this:
[-2, -1, -4, 1, 2, 3, 4, -2, -4, 5, 6, 7, 8, -2, 9, 10]
To understand better how it's working, here is an indented version of the same serialized array:
[-2,
-1,
-4
1, 2, 3, 4
-2
-4
5, 6, 7, 8
-2
9, 10
]
This structure can be serialized and deserialized in linear time using a recursive algorithm.