Results 1 to 4 of 4

Thread: Homework

  1. #1
    Member
    Join Date
    Jul 2016
    Location
    Russia
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Homework

    Hi all!

    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.

    Code:
        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
    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

  2. #2
    Member
    Join Date
    Jul 2016
    Location
    Russia
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts
    No ideas?

  3. #3
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    Sorry, but your description is not quite comprehensible.
    For example, a string of 2l bits has l bits of extra information comparing to a string of l bits, not one like you presume.
    Also, something like you describe is possible easily enough, but doesn't make any sense:
    1. Compress your original l-bit string to m bits with any existing codec (eg. paq8)
    2. Randomly double or halve the length of m-bit string, but don't let it become shorter than m bits (ie only halve it if l>=2*m)
    (doubling the length can be done by padding it with zeroes, for example)
    3. To make the average length of output converge to l, we can simply skew the probability distribution of operation choice towards that.

  4. #4
    Member
    Join Date
    Jul 2013
    Location
    United States
    Posts
    194
    Thanks
    44
    Thanked 140 Times in 69 Posts
    I'm not really clear on what you're trying to do, either, but this does sound a bit like secret sharing.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •