First of all I want to apologize if this is not the best forum to post my question, but I've asked it on StackOverflow before and it got deleted. Probably because it's an "homework question" or something. I figured maybe you guys could help me.
I've tried to strip down my question to the essentials, as it's part of a larger homework/teaser which doesn't have however other significant relations with this problem I have.
So, here's the question.
I have a string. It's an arbitrary string with text, but this is not really important I guess and I'd like to consider any string. Is there any function/algorithm that, given the string, "transforms" it (or just a part of it) into another string such that:
- the function is reversible (I can retrieve the original string)
- during the conversion, the function either "gains" or "loses" zero or more bits of information (not of the original string). For example if I have a string of length l=10, I can double its length to 2l or 2l+1 (gains 1 bit) or halve it to l/2 (loses 1 bit) - see example below
- when applied several times, the "gain" or "loss" is on average 0. Basically sometimes I gain 1 or more, other times I lose 1 or more, but on average 0.
A practical example: string s with length l.
If I know the new string and which choice I made, I can retrieve the original string. In the case of "double" I can say I have "gained" 1 bit because I chose either of (2l, 2l+1) and just need to look if the new length is even or odd. In the other case, "halve", I say I have "lost" one bit because I need to remember somewhere what the original length was (for example l=10 and l=11 both give new_length = l/2 = 5). The average is zero though, because sometimes I gain something, other times I lose something. The problem that I have with this solution is that the new length is very far apart from the original length. If a string has thousands (or millions) of bits, the difference can become huge fast. Like, exponentially fast, which means I can hit zero length or pretty much infinity (for my practical needs). Does anybody have any idea if I can do something similar to this, but without this huge variability in the string length? For example by increasing/reducing the string by a much smaller amount? Alternatively any other algorithm that satisfies the 3 points above would be nice (my example is just an example). Thanks in advance
if choice == double
new_length = random(2l, 2l+1)
// Add bits to s until it reaches new_length.
else if choice == halve
new_length = l/2
// Split string in half