Compressieprogramma's kunnen talen herkennen

UniSci heeft een artikel gepubliceerd waarin zij melden dat Zip-programma's accuraat de taal en zelfs de auteur van een document kunnen herkennen. Dario Benedetto en Emanuele Caglioti hebben dit aangetoond aan de hand van de compressie-efficiëntie. De basis van zip-programma's bestaat uit het opsporen van dubbele tekstelementen. Het programma slaat zo'n tekstelement één keer op en verwijst er bij meerdere instanties naar. Op dit moment houdt men zich alleen nog bezig met tekstbestanden, maar later kan deze analyse ook gebruikt gaan worden voor DNA, geologische processen en medische data. Hieronder een gedeelte uit het artikel:

The researchers found that file compression analysis worked well in identifying the language of files as short as twenty characters in length, and could correctly sort books by author more than 93% of the time.

Because subject matter often dictates vocabulary, a program based on the analysis could automatically classify documents by semantic content, leading to sophisticated search engines. The technique also provides a rigorous method for various linguistic applications, such as the study of the relationships among various languages.

Verwijderd bracht ons op de hoogte.

Reacties (19)

[SvMp]

Voor de duidelijkheid: Dit heeft ondanks het icoon en de term "zip" niks met Winzip te maken.
Ze hadden het woord zip ook beter niet kunnen gebruiken, maar bv. compressie-software

[Verwijderd]

Eigenlijk had je beter Lempel-Ziff kunnen gebruiken. Want deze twee heren zijn de grond leggers van ongeveer alle dictionary compressie algoritmes.
Want er zijn ook nog andere compressie algortimes zoals: RAR, ACE, LHA, LZH, LZW, ARJ, etc... Deze zijn in principe allemaal een LZ compressie algortime alleen zijn er een aantal verbeteringen in gebracht zoals bijvoorbeel encoding van de data voor de compressie (Huffman, Welch, ...)

[ddofborg]

meeste compressie programma's (RAR/ACE, dus voor random data) zijn gebaseerd op ZIP algorithme geloof ik, vandaar...

[GarBaGe]

"ZIP-algoritme" En wat is dat dan ??
Alle compressieprogramma's gebruiken o.a. huffman-encoding. Ook ZIP. ZIP is geen algoritme, alleen een programma.
En dat is maar goed ook, want ik vind ZIP nog steeds een van de slechtste compressie programma's, in alle opzichten. compressie is het slechtst, doet het het langst over en kan niet goed multi-volume (gebruikt bij floppy's de volumenaam van de floppy om de floppy's te scheiden, dit kan je dus nooit op een harddisk doen, omdat alle bestanden dan hetzelfde heten).
Dus gelukkig hebben de meeste programma's nog een eigen interpretatie van de compressie-algoritmes.

[AxiMaxi]

Ze zijn niet op ZIP gebaseerd, maar op de Huffman codering. In principe betekent dat een kortere bitcombinatie gebruiken voor veel voorkomende bytes. Maar pas na die sequence-methode (LZW)zoals in het stukje beschreven staat.

{edit}shit, te laat omdat ik m'n password verkeerd intypte :({/edit}

[stappel_]

En ZIP is geen algorithme maar een implementatie van LZW en Huffman. Het gebruikte algorithme is dus meestal LZW (Lempel-Ziv-Welch)

[Verwijderd]

Waarom is dit zo'n geweldig nieuws? Er waren al heel wat andere soorten software die talen kunnen herkennen (Denk aan MS Office)... Dat ze ook de auteur kunnen herkennen aan zijn schrijfstijl, dat vind ik nu wel bijzonder! Maar ja, misschien had dit bericht dus gewoon onder een andere naam naar buiten moeten komen. Compressieprogramma's herkennen auteur ofzo.

[Verwijderd]

Ja, maar dat je het ook kan gebruiken als slim algoritme om ook DNA te kunnen analyseren is wel totaal nieuw.
Zo zie je maar weer eens dat de ene ontwikkeling tot meerdere kunnen gaan leiden. Denk maar aan de Teflon-coatings; van space tot onder het gebakken eitje

[machiel]

Zo bijzonder is een compressieprogramma niet. Het is een kwestie van tellen van woorden/letters. (Het coderen is een ander verhaal). Waarom dit in verband moet worden gebracht met zip begrijp ik ook niet.

[Verwijderd]

Is wel een interessante toepassing. Een compressieprogramma moet inderdaad de bestanden analyseren om dubbele stukken te herkennen en zo, dan ben je al een stapje in de richting van tekstanalyse.
Maar voor de rest heb je het niet echt nodig lijkt me om taal en auteur te herkennen om daarmee de compressie te verbeteren. Of zouden ze omslachtige taalconstructies door een korter synoniem vervangen?

* 786562 fremar

[Rukapul]

Is dit nieuws?

Mensen met een beetje kennis van cryptografie weten dit allang. Natuurlijke taal heeft maar een paar bits werkelijke informatie en de rest is redundant. De mate van redundantie verschilt per taal. Ook herhalende lettergroepen zijn onderwerp van onderzoek in cryptografische toepassingen aangezien dergelijke herhalende elementen door een cryptografisch algoritme zodanig verborgen moeten worden dat de structuur in het vercijferde bericht niet aanwezig is.

[Verwijderd]

Bingo!

[nAFutro]

dit is gewoon een volgende stap in slimmere compressie, raar dat dit er nog neit was. maar volgens mij gaat het comprimeren nu wel een heel stuk langer duren omdat eerst het hele document moet worden gescand naar reeksen die herhaald worden en de programma's worden stukken groter.

[General_Failure]

Volgens mij heeft dit niets met betere compressie te maken, maar met het feit dat compressieprogramma's bestanden in dezelfde taal op dezelfde manier comprimeren, omdat de structuur hetzelfde is.

Op deze manier kun je automatisch (in 93% van de gevallen) archiveren.

[Verwijderd]

Wat er dus in het artikel staat is het volgende:
Ze nemen basisbestanden van alle talen die beschikbaar zijn. Achter die basisbestanden plakken ze de tekst waarvan ze de taal willen weten. Dan gaan ze comprimeren. De combinatie basis-tekst met de beste compressie is dus indicatief voor de taal van het document.

Dit werkt vanuit de volgende veronderstelling: Het zip-algoritme (LZW om precies te zijn) en vele andere compressiealgoritmen werken met adaptive dictionaries. Dit houd in dat het algoritme zich aanpast aan het bestand dat gecomprimeerd word.

Wat ze nu bedacht hebben is dat documenten van dezelfde taal meer lijken op documenten van een verschillende taal, en dus een betere compressie hebben.

Overigens is het niet perse nodig alle basisbestanden elke keer opnieuw te comprimeren. Je kunt ook het woordenboek aan het eind van de compressie bewaren en dat gebruiken.

[Verwijderd]

ZIP is volgens mij geen LZW variant. LZW is namelijk copyrighted door ... uhm.. was compuserve maar ik weet niet van wie dat tegenwoordig is. Hoedan ook. Je mag niet zomaar de LZW gebruiken. Volgens mij was ZIP een afleiding van LZH.

[Verwijderd]

door Unisys, zie hier