Results 1 to 6 of 6

Thread: Map random string to another string of the same size on average

  1. #1
    Member
    Join Date
    Jan 2018
    Location
    Norway
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Map random string to another string of the same size on average

    Would it be possible to map (a reversible mapping) a random string of bits S1, to another random string of bits S2 which has a different length (length S1 != length S2) but that on average has the same length (avg length S2 = length S1)?

    Thanks.

  2. #2
    Member
    Join Date
    Jan 2018
    Location
    Norway
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Example:

    - open a file
    - read the first 1000 bits
    - replace these bits with another string that is shorter or longer, but on average still 1000 bits
    - save and close

  3. #3
    Member
    Join Date
    Jun 2015
    Location
    Switzerland
    Posts
    667
    Thanks
    204
    Thanked 241 Times in 146 Posts
    Quote Originally Posted by slope View Post
    Would it be possible to map (a reversible mapping) a random string of bits S1, to another random string of bits S2 which has a different length (length S1 != length S2) but that on average has the same length (avg length S2 = length S1)?

    Thanks.
    In the general case, no.

  4. #4
    Member
    Join Date
    Aug 2016
    Location
    USA
    Posts
    41
    Thanks
    9
    Thanked 16 Times in 11 Posts
    Unless you have a way of knowing the lengths of S1 and S2 a priori, it's not possible (and if you do, it's triavial to map all S1 starting with 1 to a length(S1)-1 string and those starting with 0 to a length(S1)+1 string; inverting would simply compare length(S2) to length(S1); note that this also obviously would let you to compress, if only by a half-bit on average).

    Without side information, it is indeed impossible. Only mappings where S2 have the same length as S1 can achieve the same average length (trivially).

  5. #5
    Member
    Join Date
    Jan 2018
    Location
    Norway
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts
    > Unless you have a way of knowing the lengths of S1 and S2 a priori

    Maybe if length(S1) is known a priori, but not length(S2)?

  6. #6
    Member
    Join Date
    Aug 2016
    Location
    USA
    Posts
    41
    Thanks
    9
    Thanked 16 Times in 11 Posts
    If you can't compute the length of S2, then it's still impossible. Basically if I hand you a stream of bits, you need to have a way of saying "S2 ends here". The thing is, that extra bit of information to know when S2 stops makes the task impossible - encoding that information in any way costs bits, and this pushes the average length higher. I am trying to think of a more intuitive counting argument for that but am drawing a blank...

Similar Threads

  1. Semilocal string comparison (3 lectures [in russian])
    By lz77 in forum Data Compression
    Replies: 0
    Last Post: 29th November 2016, 12:21
  2. sorting rotations of a string - detecting an never-ending comparision
    By just a worm in forum The Off-Topic Lounge
    Replies: 9
    Last Post: 5th June 2015, 17:53
  3. UV map compression
    By Cyan in forum Data Compression
    Replies: 0
    Last Post: 7th October 2014, 15:54
  4. Directory hash as one string
    By FatBit in forum The Off-Topic Lounge
    Replies: 6
    Last Post: 17th January 2012, 00:29
  5. which tool has the samllest size/orignal size * time
    By l1t in forum Data Compression
    Replies: 7
    Last Post: 27th August 2010, 06:10

Posting Permissions

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