6 ms·

GPT-2 is not just a dictionary, it's enormous non-linear function. This compressor gets compression levels which are unachievable with a dictionary. Alas, its

• blackbear_ 6y ago
  > GPT-2 is not just a dictionary, it's enormous non-linear function. Dictionaries are non-linear functions. > This compressor gets compression levels which are unachievable with a dictionary. I don't see why this is the case, care to elaborate?
  • croddin 6y ago
    A dictionary doesn’t give a prediction about what the next word in string will be. GPT-2 does and those predictions can be used so save space.
    • cma 6y ago
      A dictionary of n-grams does, which I think is what he is describing.
      • sidarape 6y ago
        GPT is way better at next-word predictions than n-grams. However, I agree with OP that the resulting compression scheme is probably not very practical all things considered.
      • TheRealPomax 6y ago
        A dictionary of n-grams does not change its probabilities based on "text seen so far", so you'd need an unbounded n. In practice, n-gram dictionaries don't encode for more than very low values of n, so while yes, abstractly we can say that GPT-2 is equivalent to an n-gram dictionary with some high n, those dictionary cannot be constructed, let alone used, leaving the equivalency is purely theoretical. GPT-2 is not a dictionary.
        • cma 6y ago
          >GPT-2 is not a dictionary. I was only responding to the statement that dictionary methods don't give a prediction of the next word in a string will be. I wasn't in any way saying GPT-2 is a dictionary.
• rahimnathwani 6y ago
  "Alas, its arithmetic coder isn't bijective-- so you can't just decompress encrypted input back into english." OP calls it a lossless encoder. What makes you say it's not bijective?
  • djbtkvehvf 6y ago
    If it was bijective, any possible string of bytes could be decoded, even a random string. Here's an example of a bijective compression system—one of the first AFAIK: http://www3.sympatico.ca/mt0000/bicom/ http://www3.sympatico.ca/mt0000/bicom/
    • nicoburns 6y ago
      > If it was bijective, any possible string of bytes could be decoded Is that true? Couldn't it is also just have a different output domain. For example the function: f: non-zero positive integers -> even non-zero positive integers f(x) = 2x is bijective.
      • snakeboy 6y ago
        I believe here "bijective" is being used with the implicit assumption that we're talking about the same finite sets, "byte-strings up to a fixed length". From the link on BiCom: > compression with bicom is completely bijective -- any file is a possible bicom output that can be decompressed, and then recompressed back to its original form.
        • nicoburns 6y ago
          "any possible string of bytes could be decoded" still doesn't seem like the right criteria though. Gzipping is lossless/bijective, but an arbitrary byte stream won't necessarily be a valid gzip archive.
          • lidjfsljbn 6y ago
            Lossless is not equivalent to bijective. Gzip is not bijective. The definition of bijective compression is that an arbitrary bytestream is valid for decompression. To put it another way: because there are some output files that gzip compression can never create (whatever the input), it's a not surjective function from the set of possible inputs to the set of possible outputs. For this reason it is not bijective.
• jkhdigital 6y ago
  Yes, you can decompress a random string. Might be garbage, but arithmetic coding won’t “fail”.
  • nullc 6y ago
    Not all random strings decompress, also termination is an explicit symbol that can only happen once, so for most random inputs it only consumes a tiny amount of the input.