4 ms·

Initial release (according to Wikipedia) 24 April 2011. It is derived from the LZ77 family of compression algorithms, which have papers published in 1977 and 1

Initial release (according to Wikipedia) 24 April 2011. It is derived from the LZ77 family of compression algorithms, which have papers published in 1977 and 1978 and thus US patent expiration around the year 2000. It is understandable that it would take time for discourse, inclusion in educational curriculum, and programmers feeling free to tinker with the concepts to produce useful new art. It's almost like patents are a bad thing for the progress of science and skilled arts.

speedgoose 5y ago
I'm very thankful we don't have software patents in Europe. And you should be thankful too if you use vlc or ffmpeg for example.
klodolph 5y ago
Was LZ77 patented? As far as I can tell, patents related to various techniques in LZ77 were filed by various parties in the mid 80s and 90s, but that wouldn't matter, since LZ77 was already published at that point. PNG was explicitly designed to be unencumbered by patents, and it was released in 1996.
- maskros 5y ago
  I take it you don't remember the Unisys GIF patent licensing mess that prompted the development of the PNG format? https://en.wikipedia.org/wiki/GIF#Unisys_and_LZW_patent_enforcement https://en.wikipedia.org/wiki/GIF#Unisys_and_LZW_patent_enfo...
  - deleted 5y ago
    [deleted]
  - st_goliath 5y ago
    Yes, but GIF is based on LZW, as the article you linked to says. LZW was derived from LZ78. They both IIRC use a dictionary coding approach with an explicit dictionary that is constructed during processing. Indices into the dictionary are used to encode repetitions. PNG uses deflate, which is based on a combination of Huffman coding and LZSS, which is derived from LZ77. LZ77 encodes repetitions using back references into a sliding window. To my understanding, LZSS also uses a dictionary based approach, but only for finding such repetitions during encoding. So this does not answer the question if LZ77 was patented or not. The Wikipedia article about LZ77 does cite a patent (https://en.wikipedia.org/wiki/LZ77_and_LZ78#cite_note-3 https://en.wikipedia.org/wiki/LZ77_and_LZ78#cite_note-3) and somebody in the talk page mentions that there's been a law suite (https://en.wikipedia.org/wiki/Talk:LZ77_and_LZ78#Patent_contravercies https://en.wikipedia.org/wiki/Talk:LZ77_and_LZ78#Patent_cont...). However, quickly scanning over the patent, it seems to discuss an improved algorithm based on LZ77, perhaps it relates to LZS? (Note: not LZSS from above; this is again is a different algorithm) The LZS page mentions a law suite sounding similar to the one from the talk page, but contains no direct reference to the patent: https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Stac#Patents https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Sta... It also states that the LZS patent was filed in 1993 and expired in 2007 (due to not paying their fees).
    - deleted 5y ago
      [deleted]
cogman10 5y ago
At very least, tech patents really should be shortened to something like 5 years instead of being 20 years. It's nuts that the SSE2 instruction set has JUST come out of patent protection.

speedgoose 5y ago

I'm very thankful we don't have software patents in Europe. And you should be thankful too if you use vlc or ffmpeg for example.

klodolph 5y ago

Was LZ77 patented? As far as I can tell, patents related to various techniques in LZ77 were filed by various parties in the mid 80s and 90s, but that wouldn't matter, since LZ77 was already published at that point. PNG was explicitly designed to be unencumbered by patents, and it was released in 1996.

maskros 5y ago
I take it you don't remember the Unisys GIF patent licensing mess that prompted the development of the PNG format? https://en.wikipedia.org/wiki/GIF#Unisys_and_LZW_patent_enforcement https://en.wikipedia.org/wiki/GIF#Unisys_and_LZW_patent_enfo...
- deleted 5y ago
  [deleted]
- st_goliath 5y ago
  Yes, but GIF is based on LZW, as the article you linked to says. LZW was derived from LZ78. They both IIRC use a dictionary coding approach with an explicit dictionary that is constructed during processing. Indices into the dictionary are used to encode repetitions. PNG uses deflate, which is based on a combination of Huffman coding and LZSS, which is derived from LZ77. LZ77 encodes repetitions using back references into a sliding window. To my understanding, LZSS also uses a dictionary based approach, but only for finding such repetitions during encoding. So this does not answer the question if LZ77 was patented or not. The Wikipedia article about LZ77 does cite a patent (https://en.wikipedia.org/wiki/LZ77_and_LZ78#cite_note-3 https://en.wikipedia.org/wiki/LZ77_and_LZ78#cite_note-3) and somebody in the talk page mentions that there's been a law suite (https://en.wikipedia.org/wiki/Talk:LZ77_and_LZ78#Patent_contravercies https://en.wikipedia.org/wiki/Talk:LZ77_and_LZ78#Patent_cont...). However, quickly scanning over the patent, it seems to discuss an improved algorithm based on LZ77, perhaps it relates to LZS? (Note: not LZSS from above; this is again is a different algorithm) The LZS page mentions a law suite sounding similar to the one from the talk page, but contains no direct reference to the patent: https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Stac#Patents https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Sta... It also states that the LZS patent was filed in 1993 and expired in 2007 (due to not paying their fees).
  - deleted 5y ago
    [deleted]

cogman10 5y ago

At very least, tech patents really should be shortened to something like 5 years instead of being 20 years. It's nuts that the SSE2 instruction set has JUST come out of patent protection.