Kodowanie Huffmana wypierane przez ANS pochodzące z Polski (m.in. Apple, Facebook, Google)

4

Chyba wszyscy informatycy słyszeli o kodowaniu Huffmana - jest ono szybkie ale niedokładne (przybliża prawdopodobieństwa potęgami 1/2), lepszy stopień kompresji daje kodowanie arytmetyczne, tyle że jest znacznie bardziej kosztowne obliczeniowo (potrzebuje mnożenia).
Okazuje się że od 2014 nowe kompresory są oparte już na innym kodowaniu (ANS), które pochodzi z Uniwersytetu Jagiellońskiego - jest ono dokładne i tanie obliczeniowo (nie potrzebuje mnożenia):
Wikipedia: https://en.wikipedia.org/wiki/Asymmetric_Numeral_Systems
wiadomość z UJ: http://www.uj.edu.pl/wiadomosci/-/journal_content/56_INSTANCE_d82lKZvhit4m/10172/134381865
materiały: http://encode.ru/threads/2078-List-of-Asymmetric-Numeral-Systems-implementations

Przykładowo obecnie domyślny kompresor Apple (LZFSE), czy open-source kompresor z Facebook (Zstandard), który ma aspiracje do wyparcia standardowego gzip/zlib (zip-y) jako że jest kilkukrotnie szybszy i pozwala na znacznie lepszą kompresję:
https://github.com/facebook/zstd
user image

8

ANS zostało wymyślone przez Jarosława Dudę. Znam typka, miałem z nim ćwiczenia z algebry, a on robił jednocześnie 4 doktoraty.

0

Właśnie Google próbuje patentować podstawowe zastosowanie ANS - tutaj jest 400+ komentarzy:
https://www.reddit.com/r/programming/comments/6h08z5/google_is_currently_trying_to_patent_video/?sort=confidence

0
elenorf napisał(a):

Właśnie Google próbuje patentować podstawowe zastosowanie ANS - tutaj jest 400+ komentarzy:
https://www.reddit.com/r/programming/comments/6h08z5/google_is_currently_trying_to_patent_video/?sort=confidence

a czego sie spodziewaliscie, oni tam w departamencie internetowym CIA (tzw. "google") sie nie p---la w uprzejmosci...

0

"Zamiast opatentować, udostępnił swój wynalazek publicznie" - a później się dziwimy że polish jokes cieszą się popularnością :/

0

ZTCW to nie miał pieniędzy by opatentować i jednocześnie nie miał zamiaru pobierać opłat licencyjnych, więc nie opatentował.

0

Pewnie to inaczej by wyglądało gdyby był np. z Wisconsin: https://www.reuters.com/article/us-ip-apple-patent-idUSKBN1AB023 - dostaną 506 mln $ od Apple.

0

@Wibowit: to tłumaczenie jest naiwne - patent nie służy robieniu kasy tylko do zachowania kontroli nad swoim odkryciem. To są podstawy które poznaje każdy kto otarł się o pracę naukową - jeśli twoje odkrycie jest naprawdę nowatorskie to najpierw patentujesz a dopiero później publikujesz. Brak kasy jest może podstawą ale nie chce mi się wierzyć że nie istnieją instytucje ani fundacje (nie mówiąc o firmach) które nie chciałyby partycypować w takim przedsięwzięciu w zamian za jakieś korzyści.

W świetle tego to to co robi Google to po prostu naprawienie błędu polskiego naukowca. Skoro on nie opatentował to mogłaby to zrobić każda troll firma i zacząć kosić opłaty licencyjne - zwłaszcza w systemie patentowym USA, gdzie jeśli się nie mylę decyduje pierwszeństwo wniosku patentowego a nie autorstwo czy pierwszeństwo użycia.

0

@loza_szydercow: biedna samotna metoda, Google musiało się nią zaopiekować ...
Polecam sobie poczytać wypowiedzi autora: https://encode.ru/threads/2648-Published-rANS-patent-by-Storeleap/page3
Zamiast patentować, Duda robił te koncepcje publiczne, też te na których oparty jest patent Google (i to na ich forum dyskusyjnym) - czyniąc je "prior art", co uniemożliwia patentowanie ... przynajmniej w teorii.
Też jest pełno publicznych implementacji - łącznie z Google, czyli nie mają co się bać o troli patentowych - jedyne znaczenie takiego patentu to odstraszanie konkurencji przed użyciem tego kodowania.

Przerażające jest to że każdy z nas wrzucając coś np. na githuba naraża się na takich sępów patentowych - że jeśli to okaże się cokolwiek warte, nawet nie zauważysz jak ktoś kto to znajdzie dostanie patent na Twoją metodę, co potem jest kosmicznie trudne i kosztowne do okręcenia.

0

"Nothing personal, it's just business" - Google robi to bo patent w USA może zgłosić każdy i jest on uznany za prawidłowy (formalnie) dopóki ktoś go nie zakwestionuje a to wymaga już przewodu przed sądem i kasy na prawników. Sorry, taki mają system i stąd ta moda na patentowanie wszystkiego co się da. Nie posądzam Google o dobre intencje, taki patent w ich portfolio może być potężną bronią w walce przeciwko portfolio MPEG LA które już poinformowało jakoby VP9 (czy VP10) "może" naruszać kilka ich patentów.

Tu idzie gra o duże pieniądze więc gadki o moralności i "don't be evil" są trochę jakby nie na miejscu. Co do GH - jeśli ktoś publikuje tam naprawdę rewolucyjne algorytmy to pozostaje mi tylko wzruszenie ramion. Nauka to też biznes - przecież uczelnie mają w programach zajęcia z podstaw prawa i ochrony własności intelektualnej.

0

Gdyby każdy miał takie podejście, na GH znalazłbyś tylko podstawowe implementacje podręcznikowych algorytmów - każdą nietypową kombinację powinieneś od razu patentować, co trwa rzędu 2 lat i kosztuje kupę kasy ... a potem nikt tego przez 20 lat nie używa aż do wygaśnięcia patentu - jak np. z kodowaniem arytmetycznym który z powodu patentów leżał w szufladzie przez kilka dekad: https://en.wikipedia.org/wiki/Arithmetic_coding#US_patents

0

Całe szczęście niektórzy rozsądni naukowcy mają takie podejście co procentuje w przyszłości ich odkryć -> https://morris.cymru/2009/01/penroses-patent-and-the-battle-of-the-tissue-tiles-contains-mathematics/

2
loza_szydercow napisał(a):

"Nothing personal, it's just business" - Google robi to bo patent w USA może zgłosić każdy i jest on uznany za prawidłowy (formalnie) dopóki ktoś go nie zakwestionuje a to wymaga już przewodu przed sądem i kasy na prawników. Sorry, taki mają system i stąd ta moda na patentowanie wszystkiego co się da. Nie posądzam Google o dobre intencje, taki patent w ich portfolio może być potężną bronią w walce przeciwko portfolio MPEG LA które już poinformowało jakoby VP9 (czy VP10) "może" naruszać kilka ich patentów.

Tu idzie gra o duże pieniądze więc gadki o moralności i "don't be evil" są trochę jakby nie na miejscu. Co do GH - jeśli ktoś publikuje tam naprawdę rewolucyjne algorytmy to pozostaje mi tylko wzruszenie ramion. Nauka to też biznes - przecież uczelnie mają w programach zajęcia z podstaw prawa i ochrony własności intelektualnej.

Złodziej to złodziej. Usprawiedliwianie tego dużymi kwotami do mnie nie przemawia, to argument dobry jedynie dla innych potencjalnych złodziei lub ludzi, których moralność jest na sprzedaż.

0
loza_szydercow napisał(a):

@Wibowit: to tłumaczenie jest naiwne - patent nie służy robieniu kasy tylko do zachowania kontroli nad swoim odkryciem. To są podstawy które poznaje każdy kto otarł się o pracę naukową - jeśli twoje odkrycie jest naprawdę nowatorskie to najpierw patentujesz a dopiero później publikujesz. Brak kasy jest może podstawą ale nie chce mi się wierzyć że nie istnieją instytucje ani fundacje (nie mówiąc o firmach) które nie chciałyby partycypować w takim przedsięwzięciu w zamian za jakieś korzyści.

Za jakie korzyści? Podaj przykład takiego sponsoringu.

Za stroną http://www.ipwatchdog.com/2015/04/04/the-cost-of-obtaining-a-patent-in-the-us/id=56485/ koszt uzyskania patentu komputerowego na obszarze samych USA to ok 20 tysięcy zielonych:

Example 1: Computer implemented method for facilitating certain functionality via the Internet

  • Patent search with attorney opinion = $2,500 to $3,000
  • Provisional patent application prepared and filed = $6,000
  • Filing fee to the USPTO for provisional patent application = $130 (small entity)
  • Nonprovisional patent application based off provisional filing = $10,000 to $12,000
  • Filing fee to the USPTO for nonprovisional patent application = $800 to $1,250 (small entity)
  • Professional illustrations for nonprovisional patent application = $500
  • TOTAL COST through filing nonprovisional patent application = $19,930.00 to $22,880 (if provisional patent application is skipped the cost would be $130 less)

Kolejna sprawa to to, że ANS na początku było nieinteresujące, bo było powolne w porównaniu do kodowania arytmetycznego. Dopiero po jakimś czasie od wynalezienia (chyba kilka lat) wynaleziono super-szybkie metody na zaimplementowanie ANS i te metody były już szybsze niż kodowanie arytmetyczne. Dojście do takiej wydajności odbyło się wysiłkiem wielu niezależnych osób.

0

@Wibowit - z korzyści przychodzi mi na myśl choćby prawo do użycia bez ponoszenia opłat licencyjnych jeśli autorowi by się kiedyś odwidziało. Albo deklaracja że patent podlega pod Royalty-Free Patent Licensing. Zresztą co do opłat za proces to nie ma już pozarządowych NGOsów, subwencji rządowych czy nawet programów UE? Bo nawet patrząc na USA nie wszystkie wnioski to domena korporacji.

Autor pokpił sprawę i tyle.

EDIT: Takie coś na szybko http://www.pi.gov.pl/Finanse/chapter_94644.asp

1

@loza_szydercow: Jest też prostszy sposób na uczynienie czegoś public domain, zabezpieczając przed patentowaniem jako obecność "prior art" - przez po prostu upublicznienie, co autor zrobił: w postaci publikacji i wypowiedzi na publicznych forach.
Też tak w teorii powinno działać upublicznienie np. przez Github, problem w tym że wygląda na to że osoba która to tam sprawdza domyślnie szuka tylko po słowach kluczowych patenty amerykańskie - kwestia rozszerzenia takiego sprawdzania, co niestety jest technicznie trudne.

0

@elenorf: no to teraz trzeba czekać aż ktoś to zakwestionuje (patent litigation) do tego czasu większość mniejszych podmiotów pewnie się wstrzyma z użyciem z obawy o wynik.

0

@loza_szydercow: Owszem ktoś dodał kilkadziesiąt pozycji lekturek dla sprawdzającego, w wątku z encode.ru jest sugestia że pewnie ktoś z MPEG:
https://register.epo.org/documentView?number=US.201615370840.A&documentId=1-9-US++1537084008P1+

0

Blah, myślałem że wniosek patentowy Gugla został przyjęty i patent przyznany, teraz uświadomiłem sobie że jest dopiero na etapie rozpatrzenia. O ile urzędnik nie pokpi sprawy to zostanie odrzucony. Pozostaje pytanie na co liczył Google nadając temu bieg, skoro sukces jest wątpliwy. Chyba że jego prawnicy i spece od prawa patentowego wiedzą coś więcej i gra jest warta świeczki.

5

Nawet już w radiu o tym mówili. UJ zamierza oficjalnie zaprotestować, cokolwiek to oznacza.

0

Polskie kodowanie od kilku miesięcy jest w jądrze Linuxa (od 4.14): https://www.phoronix.com/scan.php?page=news_item&px=Linux-4.14-Zstd-Pull
Niedługo będzie w naszych mailach - trwa standaryzacja MIME ( https://en.wikipedia.org/wiki/MIME ): https://datatracker.ietf.org/doc/draft-kucherawy-dispatch-zstd/

Szkoda że nie ma jakiegoś wideo które łatwo by je tłumaczyło ...

ps. patent gugła wstępnie odrzucony, ale oczywiście walczą dalej: https://encode.ru/threads/2648-Published-rANS-patent-by-Storeleap?p=54339&viewfull=1#post54339

1

Ostatnio Free Software Foundation wsparło walkę z patentem: https://twitter.com/fsf/status/1034181158429515778
Po czym Electronic Frontier Foundation poinformowało że jest non-final rejection, prosząc Google o zaprzestanie dalszego starania o ten patent: https://www.eff.org/deeplinks/2018/08/after-patent-office-rejection-it-time-google-abandon-its-attempt-patent-use-public
W czerwcu sprawa doszła na górę redita (~25k): https://old.reddit.com/r/programming/duplicates/8q3kp8/inventor_says_google_is_patenting_work_he_put_in/
Teraz znowu (~30k): https://old.reddit.com/r/technology/duplicates/9c7kw6/google_is_trying_to_patent_use_of_a_data/

0
elenorf napisał(a):

Ostatnio Free Software Foundation wsparło walkę z patentem: https://twitter.com/fsf/status/1034181158429515778
Po czym Electronic Frontier Foundation poinformowało że jest non-final rejection, prosząc Google o zaprzestanie dalszego starania o ten patent: https://www.eff.org/deeplinks/2018/08/after-patent-office-rejection-it-time-google-abandon-its-attempt-patent-use-public
W czerwcu sprawa doszła na górę redita (~25k): https://old.reddit.com/r/programming/duplicates/8q3kp8/inventor_says_google_is_patenting_work_he_put_in/
Teraz znowu (~30k): https://old.reddit.com/r/technology/duplicates/9c7kw6/google_is_trying_to_patent_use_of_a_data/

Może przetestuję to jak należy, a wtedy zobaczymy... co to jest warte.

Masz algorytm tej swojej metody - w postaci ogólno-matematycznej?

0

Jest cały artykuł o tym na wiki: https://en.wikipedia.org/wiki/Asymmetric_numeral_systems
Jest tam opis matematyczny jak i linki do implementacji.

0

You have to consider how many times Google got fucked by this in the past. They created a webm video compression standard and made it open source and granted free use of the patent and immediately got sued by a consortium of software companies dedicated to pooling patents in order to maintain a monopoly on video compression. Literally every device you own that plays mp4's pays royalties to these jerks (Apple is a memeber and has contributed patents and collects a share of the royalties).

Since then, Google is all about patenting any bullshit they can but only ever using them defensively (i.e. you sue me for bullshit, we have something in our portfolio we can use to sue you back). If you can get a patent for a novel use (stretching it to call this novel) for an old tech, it behooves you to get it lest someone else does it first and sue your ass.

Sadly, this is the game they quite literally have to play. Trying to patent any bullshit you possibly can just so you can countersue trolls is, in fact, the least evil way to do things. As far as I know, Google never sued anyone for patent violations who didn't sue them first. That's how fucked up our patent system is.

lul.

0
Wibowit napisał(a):

Jest cały artykuł o tym na wiki: https://en.wikipedia.org/wiki/Asymmetric_numeral_systems
Jest tam opis matematyczny jak i linki do implementacji.

Nie widzę tam wzorów, ani algorytmu, który można byłoby zakodować wprost.
A grzebanie się w słownych opisach, aby to wycisnąć, raczej nie specjalnie mnie interesuje - kilka dni roboty..

1 użytkowników online, w tym zalogowanych: 0, gości: 1