Somewhat tangential, but if you want to obtain an intuitive understanding between probability and information (and thus understand many compression algorithms), play around with this excellent interactive graphic from Wikipedia that explains arithmetic coding:
The ANS algorithm mentioned in the article has the theoretically-close-to-optimal compression ratio of arithmetic coding and the speed of Huffman coding (https://en.wikipedia.org/wiki/Huffman_coding)
Arithmetic coding is generally superiour to Huffman coding, but was very underused because of the patent situation. Will we see a rerun? If so, it would be another case a software patent set back the industry.
I haven't looked at the patent in detail, but in my experience as a former patent examiner, likely the claims cover some new detail missing from the prior art. You need to look at what was claimed to know what is covered.
I'm not familiar with this technology and don't have time to take a closer look. But if I were to take a closer look, I'd check out what the examiner wrote in their allowance (Notice of Allowance and Fees Due) to see if they identified a specific feature that makes it patentable.
> But if I were to take a closer look, I'd check out what the examiner wrote in their allowance (Notice of Allowance and Fees Due) to see if they identified a specific feature that makes it patentable.
Thanks. That seems helpful.
To save people some digging and so it's easier to discuss, I've copied (actually retyped) something I found which seems relevant. At your second link, there's a document called "Notice of Allowance and Fees Due (PTOL-85)", and starting on p. 10, there's a section called "Reasons for Allowance", which reads:
----------
Reasons for Allowance
Claims 1 - 28 are allowed in light of the Examiner's Amendment and the Applicant's response filed on August 23, 2021.
The following is an Examiner's statement of reasons for allowance: Applicant has amended independent claim to incorporate detailed subject matter of the decoding process and apparatus.
The closest prior art Greenfield et al., (US 2016/0248440 A1), Li et al., (US 2015/0103902 A1) and Converse (US 2017/0164007 A1) do not disclose the claimed element, "during a first phase of the two-phase structure, selectively updating, depending on a determination of whether or not an output symbol from a previous iteration was generated, state of the RANS decoder using probability information for the output symbol from the previous iteration, the state of the RANS decoder being tracked using a value;" and "during the second phase of the two-phase structure, selectively generating, depending on a determination of whether or not the state of the RANS decoder includes sufficient information to generate an output symbol for a current iteration, the output symbol for the current iteration using the state of the RANS decoder, the state of the RANS decoder including sufficient information to generate the output symbol for the current iteration if the state of the RANS decoder is greater than a threshold". Therefore, the prior art references taken either alone or in combination fails to anticipate or fairly suggest the limitations of the independent claims. While using a range asymmetric number system (RANS) decoder was known at the time of the invention, Applicant's very specific claimed structure is considered patentable over the prior art of record.
----------
As a total layman, not knowing the tech here (or patents or law), it sounds promising to me, in the sense that it probably doesn't stop everyone from using RANS.
It mentions prior art and says "RANS" ... "was known" in conjunction with that. And it also says "very specific claimed structure", which also sounds like this doesn't cover all of RANS.
> decoder using probability information for the output symbol from the previous iteration, the state of the RANS decoder being tracked using a value
> state of the RANS decoder including sufficient information to generate the output symbol for the current iteration if the state of the RANS decoder is greater than a threshold
I am not a lawyer. That reads to me like a 'relaxation'/optimization of the decoder to allow for iterations that don't yield any symbols, but still transforms the decoder state which affects subsequent symbols.
It's interesting, but feels a bit obvious to me. IIRC zstd decoder spec explicitly describes a state machine that is updated as bytes are read and symbols emitted and it doesn't seem like a big leap to imagine some ops taking multiple iterations. Then again I'm not exactly drowning in novel compression algorithms that I invented myself, so...
I wonder if you'd work around it if you it 'transpose' the problem and consider it to be variable bytes-per-instruction but still one instruction-per-symbol.
It's really hard to tell based on an article like this. The ANS creator is quoted as saying, "I don't know what to do with it - [Microsoft's patent] looks like just the description of the standard algorithm." However, who knows how much experience he has with patents? It may be that Duda invented the shoelace, and Microsoft invented the plastic sleeve at the tip of the shoelace.
As Timothy Lee says in the article, the problem with this type of patent is that it boxes in how you can use the original technology: you can freely tie your shoes with this shoelace, but if you use a double knot, now you infringe a patent.
In some ways, this mirrors the difference between copyleft and permissive copright licenses. By failing to patent the original invention, Duda made ANS useful and widely available, but he now has no leverage against Microsoft.
If you're implying that only filed patent applications are available as prior art, that's not right. Anything available to the public can be prior art in the US. (Even some private things can be prior art in the US, for example, an offer to sell the invention creates prior art even if completely confidential.) If MS filed a patent application before anyone else, they could still receive a prior art rejection for anything available to the public like code available online, academic papers, etc.
The US is hobbling itself with software patents. China pretty much ignores all patents and will win in the global market because of this. US companies need to quit the stupid patent wars, lest the become irrelevant on the world markets.
I agree that patents are unrealistic in the modern world.
Frankly, it seems that most (nearly all) patents have only a trivial amount of money invested to create the idea, other than what the patent lawyer costs. For example, "playing checkers --- with a computer" patents. Ending all patents would not slow down innovation at all.
There is one exception, drug patenting, where billions are spent developing a drug and getting it approved.
I'm not the parent, but I think patents for drugs are a good thing. I'm willing to be convinced otherwise, but the ease of copying them (once a chemical is known) combined with the cost of finding the drugs seem to fit very well with the spirit of patents, where new knowledge development is rewarded with a temporary monopoly.
I do grant that the practice of patenting small incremental changes to existing patented things ("this drug, with slower release!") does seem a bit questionable, but overall it still seems like a good thing. I'd be interested in hearing your argument for why it's not a good fit.
How many things have you developed after spending unkown amount of time? You don't feel you're entitled to ensure you are credited with that work and allowed to earn from that work?
As I've stated elsewhere in this thread, you don't have to be a dick about owning the patent. It's your patent, and you can do with it what you want. There are patent pools that are managed to ensure they can't be used for evil that you can donate your patent to if you can't afford the time to manage it.
> How many things have you developed after spending unkown amount of time? You don't feel you're entitled to ensure you are credited with that work and allowed to earn from that work?
I do feel that if I spend my time creating something on my own, I should be free to use it, yes. Unfortunately, the patent system means I'm not necessarily allowed to use something I invented and created myself, because it may be patented.
As John Carmack said:
"The idea that I can be presented with a problem, set out to logically solve it with the tools at hand, and wind up with a program that could not be legally used because someone else followed the same logical steps some years ago and filed for a patent on it is horrifying."
There is an inherent disconnect in your argument. Concrete implementations of software deserve protection sure, and do under copyright law. Software patents are attempting to reserve concepts and generally only hurt innovation by restricting other unrelated ideas from using a technique even if they came up with the algorithm entirely in a white box. History has shown time after time of simultaneous development of ideas once all the pieces are available (just look at Calculus).
This algorithm is a great example as its a general use encoding mechanism. If I develop software to encode and decode radio transmissions to a satellite using it, patenting it will prevent it from being using for say image encoding and decoding across the web. That use has zero impact on my concrete implementation or my commercial sector.
Even for overlapping industries, if there are zero patents, and two competing companies independently come to the same technological solution what is the justification for being able to patent that? If they didn't come to it independently because its available publicly on the web, then its prior art and shouldn't be patent-able anyway. If one reversed engineered the other solution and reproduced it, that's perfectly legal for other industries under certain circumstances and is explicitly allowed under the DMCA. I'm not arguing its right, but if that is supposed to be illegal patents as designed are the wrong tool for enforcement.
This isn't a patent covering a specific use of a specific algorithm for a specific industry (which even then I don't think should be patent-able) but the general algorithm itself restricting ALL uses of it. This is an existing concept that was intended to be open, already exists in the real world, and is on route to becoming part of international standards being gobbled up by Microsoft. There does not appear to be a significant or meaningful contribution to the work in this patent and should really have been rejected due to prior art.
Saying the original author should have patented this is also facile as that takes an enormous amount of resources that isn't available to most lone developers, or researchers, especially when the intent is to give it away freely to world.
The intent of filing a patent to give away freely is specifically to protect against someone else filing the patent. It can be expensive, but not prohibitively so if you're willing to do some of the leg work yourself.
In this case it's an international patent as the original author is not based in or from the US which adds complications. That aside you're looking at a minimum of $500 in patent office fees alone. That's probably fairly reasonable if that was all it is, and if you can get it right on the first try it might be. That cost is per submission and there is a huge schedule of fees that might expand that.
You're also glossing over the personal value of time expenditure to do that which even with professional guidance can take hundreds of hours. It is absolutely prohibitively expensive for something someone is going to give away for free and even most small independent companies.
There should be no reason that a donated public idea or concept should require any expenditure for protection.
As the author of the CRAM implementationn of rANS, I can say that these sort of articles aren't helpful. Clearly my work predates this by several years, so there is nothing here which can realistically impact on CRAM, however fear alone is sufficient to damage uptake and usage. It's back to the classic strategy of FUD: Fear, Uncertainty, Doubt.
Sadly the patent is woefully vague. I understand RANS and a lot of the optimisations used for doing it efficiently, but I don't understand that patent. It's just not clear enough for someone skilled in that field to know exactly what it is they're patenting.
Specifically rANS states are updated on a symbol by symbol basis. A query is made to get a range, that is looked up to determine the symbol for that range, and then the state is updated and possibly renormalised to fit in the desired range of valid states. There is no whether-or-not a previous symbol was decoded scenario. So I think they're talking at a higher level of block based decoding and using stats from the previous block for decoding the current block, and the possibility of a symbol in the current block not being observed in the previous one (ie escape codes, as used in PPM etc). However I'm really not sure. That's just me grasping at straws trying to think of something that makes sense.
In short, the patent fails the most basic test of being implementable by someone else having read the patent. It's deliberately vague, so they can then apply it to as much of the problem space as possible. That annoys me! As does patenting trivial modifications to rANS that aren't inventive. rANS is just a drop in replacement for the earlier (arithmetic) range-coders, albeit in reverse order. Therefore any tricks and techniques previously applied to range coders can also be applied to rANS. However being the first to do such a thing is no more an invention that the first person to use fiberglass or carbon-fiber in a boring every day item such as a chair. The new material is the invention, not being the first to use it in a particular manner that is obvious to all.
If the original creator patented ANS and then just basically waived the patent for everyone, would that not help the situation with other implementations that are "close enough" to the original?
Generally no, simply publishing is enough prior art to avoid someone else getting a patent. It can be helpful in indirect ways, like being more likely to be seen by a patent examiner. Alternately, you can license it under a defensive patent license which is very useful in some situations (see e.g. Opus, AV1).
The only way of this maybe working I can think of is to patent ANS and license it for free to anyone with one exception - forbidden use by anyone who patents or licenses further patents on ANS. This would only leave out patent trolls, but at the same time incentivize everyone else to never touch patent troll patent and always fight them to the death.
Patents do more harm than good. Ideas aren't scarce and obviously, this is abused by bad players to restrict competition. Doesn't make sense to restrict the right of someone to do a sequence of calculations on his own computer.
I think patents are fine, but the criterion used to award them are strange.
We only need a simple criterion: absent this patent, would this technology have been invented anyway (within a reasonable timeframe)? Yes, then don't award a patent. It's a bit subjective, but so is "substantiality".
By this criterion, would a certain drug have been invented if it was not expected to receive a patent. That is usually a clear no. It takes a lot of money and resources to develop new drugs but little to copy, therefore companies would stop doing research altogether.
Another example, would e-ink displays have been invented if it was not rewarded a patent? Absolutely yes, by multiple independent parties probably, thus should not deserve a patent.
I don't think there is a single software patent that would pass this criterion.
> absent this patent, would this technology have been invented anyway (within a reasonable timeframe)?
This would be the criteria of non-obviousness that already exists in US patent law. The problem is it seems like lots of patent agents seem to approve what lots of people "skilled in the art" would consider obvious (one-click checkout? shopping cart? really?!). Which then requires some level of litigation to have a lot of people "skilled in the art" to testify of the obviousness of the patent.
IMO a lot of these patent issues we see today could be solved if we had more patent agents and more skilled patent agents, but then we've got a ton of otherwise smart engineers and other kinds of people spending their days reviewing patents instead of actually making new things.
> Another example, would e-ink displays have been invented if it was not rewarded a patent? Absolutely yes, by multiple independent parties probably, thus should not deserve a patent.
Tell us, how exactly do you think e-ink displays work? Because everytime I hear someone say exactly what you've said above, I've asked them to explain it and you know what, they talk about the rotating ball gyricon which is Xerox PARC's patent, or they talk about microcapsules (often googling it as they try to respond to me). I like to be specific since I work in the display industry and if you look at my comment history you'll see how disappointed I am with the lack of actual understanding of the technologies involved and the blaise reference to patents without knowing anything about what's limiting progress in electrophoretics. In short, physics is what is limiting it.
I often demonize pharma because my partner works in that field. People in that field are often blind to its faults, like perverse incentive structures and Byzantine regulatory processes that often harm more than help. Pharma companies' R&D budget is dwarfed by its marketing and expenditures on financial games like stock buybacks, so this talk of recouping costs doesn't hold much water in my opinion.
If something is necessary but unprofitable in the near term, the early research is often already publically funded, like the mRNA vaccines.
Mm, no, you're right. But they'd spend a lot less on research, they'd have to. I don't claim to know a lot about that industry so I may be wrong, it's just an example. Can't think of an example where patents are more defensible though.
Would you say the concept of patents is inherently bad, or the current patent system?
Without some protection for original research being published, genuine inventors are forced to keep their ideas secret and/or find other ways to protect them.
I agree the current system is deeply flawed. The question I want to address is how do we ensure original ideas are not lost to humanity (either because they are kept secret, or because the research is never done in the first place).
> how do we ensure original ideas are not lost to humanity either because they are kept secret...
I understand what you mean but patents are not a good means for this goal.
I know a bit the patent world (I was granted 12 patents), patents are for small innovations. I am not even sure it's possible to patent some complex intellectual work, because a patent is basically the description of a process, not the description of knowledge.
There is little in common between a patent and a scientific article which conveys much more information. Yes, you can provide a lot information in the description section but they are not protected, only the claims are protected by law. Claims are either descriptive or describing a method to process something. After all patents were invented to protect things during the industrial revolution, essentially bolts, nuts and new steam machines.
Another thing is that most inventors do not recognize their work once the patent engineers have translated it in legal language.
Sometimes in my case, the patent engineers did not understood at all what my colleagues and me meant, or they tried to make "improvements" indeed without the slightest knowledge about the application domain. What value have those patents to describe what was meant?
Most companies which have to reproduce a patent, have a hard time. Generic drugs companies tell it is impossible to reproduce drugs from the patent and they have to be helped by the inventors.
I am not a lawyer but here are some random ideas:
Societies have invented patents as an exception to a generic right to copy: Something which is patented must not be copied without authorization. They were also invented because copyright/brand name can't protect industrial objects which were often simple in design.
So the innovation that patent laws brought was to protect the way something is working to reach some goal.
Claim 1: This is a car toy equipped with rockets
Claim 2: Where rockets uses water
Claim 3: Where water is produced from thin air
There are possibly similar legal objects with similar goals.
For example some companies sell their knowledge to government in exchange of keeping it secret. Why not imagine the reverse?
Could companies sell their knowledge to government in exchange of making it public? After all it's the interest of any government to make economy thrive and make non strategic knowledge to diffuse as quickly as possible.
This is the model used by IBM/Oracle/Redhat/etc: They sell something now almost trivial (OSes, DB, workflows) yet which needs an army of consultants to be production ready and conform to current legislation.
It's possible also to protect your product by the power of your brand. They were thousand manufacturers which tried producing pseudo iPhones but nearly nobody wants to buy one which would be obviously fake.
If companies prefer patents, it's because they don't like competition and it is easy to kill nascent competitors with an expensive trial.
Interesting ideas. Don't get rights with patents, get cash for publication! Not sure how that could be economically assessed fairly, but it might work for some kinds of thing. And maybe there isn't one thing that could replace all patents, rather a selection of things which work in different circumstances.
To me, the two most egregious ways current patents fail is how they frequently don't explain the innovation to a skilled practioner, and then how they can be subsequently interpreted overly broadly.
The first violates the entire point of being granted a patent, and the second makes them a minefield for everyone else.
I wonder if the structure of patents as a series of claims is something that could be altered. What if a patent had to clearly state what the non obvious part of the claim is (the originality that requires protection). And only that original part is then deserving of protection?
Another idea I've been toying with is how to incentivize use of good ideas. What if the value of a patent is somehow determined by how used it is? Somewhat like a stock market for ideas. You could buy shares in ideas. If they become popular, the value of those shares increases. Owning shares in the idea protects you from litigation.
This isnt very well worked out at all, just some musings on how to fix other aspects of the current system.
> Without some protection for original research being published, genuine inventors are forced to keep their ideas secret and/or find other ways to protect them.
Publication of "secrets" and general know-how can be incented via post-facto prize awards. Unlike patents, these don't forbid anyone from making use of the innovation unless they pay up. They replace a focus on enforcement - with publication often a mere afterthought in practice - with one on publication itself.
I do like the idea of prizes, they seem to work quite well for some well defined problems that needs solving.
I'm not sure they would prevent ideas being kept secret for most forms of commercial research though. Publicly funded research should be available to everyone in any case IMHO.
I agree that software patents are inherently bad, along with maths.
I still see a role for patents in other spheres, although the current system seems deeply flawed.
The main problem to be addressed in how we ensure society as a whole benefits from original research. The original conception of patents was to grant limited rights for original ideas, as long as the work is published and does not remain secret.
Not sure I agree with that completely but I do think our patent system needs to be updated and overhauled.
Everyone shits on China for stealing ideas but at the same time the general culture there does not have the same respect for the idea of patenting an idea - for better or worse.
Personally I think there is a nice middle ground between those two
How many parents are coming out of corporations that are just meant for resumes? None of which will ever be looked at again or enforced by the corporation. This is cancer.
I just came off a project where one of the developers secured a patent for some data aggregation in Spark. I wasn't interested enough to read the patent because so many basic things about the system sucked.
The act of receiving a patent doesn't make one a dick on it's own. You could file for the patent, but freely license it and not be a dick. You could even license it at a very modest fee and still not be a dick. There are ways of doing things without being a dick, just most chose to be a dick. It's not the patent's fault.
The mere act of having to ask for a licence already has a chilling effect, and the legal uncertainty just makes it worse.
For example, if Google ever gets into a patent war with Microsoft, would their 'free' licence be revoked? Does that mean the moment they'd use this coding they risk having their own patent portofolio be unenforceable? If so, they would have an interest in not using the technology from the 'free' licence, and software would be set back.
https://upload.wikimedia.org/wikipedia/commons/8/81/Arithmet...
It's from here:
https://en.wikipedia.org/wiki/Arithmetic_coding
The ANS algorithm mentioned in the article has the theoretically-close-to-optimal compression ratio of arithmetic coding and the speed of Huffman coding (https://en.wikipedia.org/wiki/Huffman_coding)