Results 1 to 24 of 24

Thread: Fractal text compression, imperfect match LZ and distortion-resistant hash function?

Threaded View

Previous Post Previous Post   Next Post Next Post
  1. #1
    Member
    Join Date
    Nov 2013
    Location
    Kraków, Poland
    Posts
    819
    Thanks
    253
    Thanked 264 Times in 163 Posts

    Lightbulb Fractal text compression, imperfect match LZ and distortion-resistant hash function?

    There is a nice old concept for fractal compression of pictures: trying to find self-similarities and utilize them, for example encoding the mappings and differences:
    https://en.wikipedia.org/wiki/Fractal_compression

    It didn’t seem to be successful, however maybe analogous approach could be reasonable for text or binary file compression?
    Specifically, while standard LZ schemes require perfect match for a sequence, there should be much more sequences with a nearly perfect match – it might be beneficial to extend LZ scheme to allow also for imperfect match and then encode the differences: for example byte sequence to XOR with, with dominating zeros – such difference could be cheaply stored using entropy coder.

    The problem is that finding similar sequences (by encoder) seems very costly.
    This is a very common task in DNA alignment and a few days ago I have realized that such search can be done in a relatively cheap way: http://arxiv.org/pdf/1602.05889
    Specifically, rate distortion theory allows to find Distortion-Resistant Hashing (DRH): hash values which are not changed while small distortion of object (like sequence).
    So searching for similar sequences can be reduced to having the same DRH value, and such collisions are relatively cheap to find.

    Does LZ scheme which (additionally!) allows partial match and then coding of differences seem reasonable? Have you met with such approaches?
    What other applications of distortion-resistant hashing can you think of?

  2. Thanks (2):

    Cyan (19th February 2016),Turtle (20th February 2016)

Similar Threads

  1. Perfect Hash Function to Hash Strings
    By joey in forum Data Compression
    Replies: 18
    Last Post: 22nd March 2016, 11:59
  2. text compression?
    By codebox in forum The Off-Topic Lounge
    Replies: 2
    Last Post: 16th March 2015, 17:31
  3. 2D fractal Haar wavelet transform (implemented)
    By Jarek in forum Data Compression
    Replies: 2
    Last Post: 12th September 2014, 16:50
  4. Rationale for Text Compression
    By cfeck in forum Data Compression
    Replies: 34
    Last Post: 20th November 2013, 04:43
  5. Fastest non-secure hash function!?
    By Sanmayce in forum Data Compression
    Replies: 13
    Last Post: 20th November 2010, 20:54

Posting Permissions

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