Zip 2

Datacompressie en Afrikaanse taalstructuren Stijn Lamers, student T&C Luuk Stoop, student BDM Universiteit van Tilburg [email protected] [email protected] 10 mei 2007

Abstract In dit paper wordt onderzocht welke Afrikaanse taalfamilies te onderscheiden zijn. Hierbij wordt gebruik gemaakt van gzip-compressie in Unix. Middels de open source client PuTTy is het mogelijk om (in Unix) teksten door middel van een script (een commando voor de computer) aan elkaar te koppelen in een gecomprimeerd bestand. Aan de hand van deze gecomprimeerde bestanden is het mogelijk om taalfamilies te herkennen. De huidige generatie zip-programma’s maakt gebruik van een woordenlijst, waarin alle woorden van een tekst voorkomen, en nummers, om de woorden in de tekst zelf mee te vervangen. De gouden regel hierbij luidt: hoe kleiner het bestand, hoe meer de teksten op elkaar lijken. Een woord dat in beide teksten voorkomt hoeft immers maar één keer gecategoriseerd te worden.

1 Introductie 1.1 Inleiding Van het ene verschijnsel maken we allemaal dagelijks gebruik, van het andere verschijnsel op zijn minst wekelijks. We hebben het hier over taal en datacompressie. Taal is essentieel om actief deel te kunnen nemen aan onze maatschappij en om te kunnen overleven. Datacompressie lijkt op het eerste gezicht minder prominent aanwezig in onze samenleving, maar schijn bedriegt. Veel computerprogramma’s maken zonder dat je het zelf door hebt gebruik van datacompressie [1]. Daarnaast maken veel computergebruikers bewust gebruik van datacompressie met behulp van programma’s als WinZip en WinRar, om nog maar te zwijgen van de miljoenen mp3spelers die dagelijks gebruikt worden. Een mp3-file is namelijk ook niets meer dan een gecomprimeerde versie van een originele, analoge geluidsgolf. Hieronder proberen we een beknopt doch doeltreffend beeld te schetsen van wat

27

datacompressie is, hoe het werkt, en wat er al aan onderzoek [2] naar is gedaan. Wij zijn van plan om Afrikaanse talen te onderwerpen aan een duale compressie, om zo een poging te wagen taalfamilies te identificeren. Er is gekozen voor Afrikaanse talen, omdat deze talen behoorlijk inheems zijn, maar tegelijkertijd gebruik maakt van het Latijnse alfabet (het alfabet dat wij dagelijks gebruiken).

1.1.1 ZIP: een introductie Om grote bestanden via het internet te verzenden wordt vaak gebruik gemaakt van ZIP-files. Kortweg komt het er op neer dat een ZIP-file een kleine versie is van een bestand. De ontvanger kan dit bestand vervolgens uitpakken (middels programma’s als WinZip en WinRar) en zien zoals het bestand er oorspronkelijk uitzag (meer hierover verderop) en met de oorspronkelijke grootte. Andere voorbeelden zijn .mp3, .jpg en .mpeg. Bij compressie wordt gebruik gemaakt van algoritmen. Een algoritme is een set regels plus de hiërarchische ordening daarvan, die door de computer verwerkt worden. Een recept is bijvoorbeeld een algoritme [3]. Het beschrijft verschillende processen die in een min of meer vaste volgorde afgewerkt moeten worden. Zo is het verstandig om het water pas aan de kook te brengen als het ei erin zit. Sommige processen, zoals het ei uit de eierdoos halen en de pan pakken, zijn niet gebonden aan een vaste volgorde.

1.1.2 Lossy compressie Er zijn twee soorten datacompressie: lossy en lossless [1]. Zoals de namen al enigszins doen vermoeden heb je bij lossy te maken met enige vorm van dataverlies, en bij lossless niet. Lossy compressie elimineert overbodige ruimte binnen het bestand om deze zodoende kleiner te maken. Dit heeft een zeer minimaal effect op de verwerking van het bestand (je hoort het niet bij mp3’s; je ziet het niet op .jpg afbeeldingen), maar verkleint de bestandsgrootte aanzienlijk. Bestanden die er baat bij hebben om in exact dezelfde vorm te blijven bestaan (zoals tekstbestanden) zijn dus niet geschikt om lossy gecomprimeerd te worden.

1.1.3 Lossless compressie Bij lossless compressie heb je te maken met algoritmes, die de informatie in het doelbestand groeperen, sorteren en zodoende ordenen. Het bestand wordt verkleind en kan weer exact gereproduceerd worden zonder enig verlies van data. Maar hoe is het mogelijk om een bestand te verkleinen, te versturen, en weer uit te pakken tot haar oorspronkelijke grootte? De truc hier is een fenomeen met de naam ‘redundantie’ [4]. Vandale.nl spreekt van een overvloed aan gegevens. Het volgende voorbeeld kan dit duidelijker aangeven. ‘Ask not what your country can do for you – ask what you can do for your country.’ Deze uitspraak is afkomstig van John F. Kennedy in zijn inaugurele rede van 1981 [3]. Als we gaan turven zien we dat ieder woord 2 keer voorkomt. De helft van de tekst is dus redundant [5].

28

Twee bekende vormen van lossless datacompressie zijn die van Lempel Ziv, en van David Huffman. We zullen nu aan de hand van het Kennedy-voorbeeld gaan kijken hoe Huffman en Lempel Ziv Welch werken in het comprimeren.

1.1.4 Huffman codering David Huffman’s manier van coderen (1952) is een vorm van lossless compressie. Gebaseerd op de gegevens van de taal van het bestand (het gaat hier dus om tekstbestanden) wordt een frequentielijst opgesteld van de letters van de taal. Hoe vaker een symbool voorkomt, hoe kleiner de code deze letter krijgt [6]. Het coderingsprincipe is binair en werkt als volgt (deel van de frequentielijst van het Nederlands, gevonden op http://www.onzetaal.nl/advies/letterfreq.html): 1. 2. 3. 4. 5. 6. 7.

E N A T I R O

18,91 % 10,03 % 7,49 % 6,79 % 6,50 % 6,41 % 6,06 %

We beginnen met de E. Deze krijgt de code ‘0’. N is de volgende, deze krijgt ‘1’. De lijst codes werkt altijd hetzelfde: eerst worden alle codes die mogelijk zijn gegeven 0 en 1 afgewerkt die 1 bit (1 karakter) beslaan. In dit geval zijn dat alleen 0 en 1, omdat er niet meer mogelijk is. Vervolgens gebeurd hetzelfde voor 2 karakters (de keuzes zijn dan 00, 01, 10, 11), voor 3 karakters, en zo verder tot alle karakters die in het doelbestand voorkomen een code hebben. Door het gebruik van kortere codes voor meer voorkomende letters is het mogelijk om data te comprimeren: de letter ‘E’ is in ASCII code 1 byte (oftewel 8 bits) groot. Nadat je er Huffman op loslaat is de ‘E’ nog maar 1 bits groot – een winst van 7 bits, oftewel 83%.

1.1.5 Lempel Ziv (Welch) Abraham Lempel en Jacob Ziv zijn in 1977 met een compressiemethode gekomen die gebruik maakt van een gecatalogiseerde bibliotheek van data. Voluit heet deze methode de adaptive dictionary-based algorithm [3]. Kort gezegd wordt er van een bestand een lijst gemaakt van alle woorden die erin zitten. Deze worden genummerd, en het doelbestand wordt dus een tekst waar alleen maar getallen in staan. In 1984 hebben Lempel en Ziv samengewerkt met Terry Welch aan een verbeterde versie [7]. In plaats van woorden ging deze compressiemethode uit van veel voorkomende patronen, niet zozeer woorden op zich. Omdat de LZ (Lempel Ziv) methode (later de LZW (Lempel Ziv Welch) methode) de meest gebruikte is zullen we hier meer aandacht aan besteden.

29

Voor het Kennedy-voorbeeld zou de woordenlijst er als volgt uit zien: 1. 2. 3. 4. 5. 6. 7. 8.

ask what your country can do for you

(Opmerking: ‘not’ is niet opgenomen in de lijst omdat dit een booleaanse operator is.) De zin ziet er dan als volgt uit: “1 not 2 3 4 5 6 7 8 – 1 2 8 5 6 7 3 4.” Deze zin op zich is, inclusief de database, amper gecomprimeerd te noemen. Maar met elke zin die erbij komt wordt het percentage gecomprimeerde bits groter: er zullen woorden voorkomen die al in de database stonden, en die dus geen nieuwe ‘entry’ meer nodig hebben. De huidige datacompressie-toepassingen doen dit proces volledig automatisch. Het grote verschil is dat er geen ‘echte’ bibliotheek wordt opgebouwd, maar een verzameling van (veel) voorkomende frases. Hierbij is de compressie niet gelimiteerd tot woorden, maar zoekt deze enkel patronen: dat kúnnen woorden zijn, maar meestal zijn het onderdelen van woorden, soms met een spatie of leesteken.

1.1.6 ZIP en talen De patronen brengen ons op het volgende onderwerp, namelijk talen. Ook in talen komen patronen voor. Elke taal heeft vaste opeenvolgingen van woorden en/of klanken, de een meer dan de ander. Dit laatste opvallende weetje is de sleutel in datacompressie als het gaat om talen. Door een stuk tekst te pakken (liefst een identiek stuk tekst) in verschillende talen, kan men kijken – door enkel het gezipte bestand te zien – welke talen op elkaar lijken. Als er twee talen zijn die veel op elkaar zouden lijken, is dat middels ZIP eenvoudig te controleren: komen de bestandsgrootten een beetje overeen, dan zijn ze inderdaad gelijkend.

1.1.7 Taal Zoals gezegd maakt iedereen elke dag gebruik van taal, en ondanks het feit dat taal een van de meest complexe systemen is die we kennen, kan (bijna) iedereen het leren. Wat taal zo moeilijk maakt is dat de relatie tussen een woord en haar betekenis volledig arbitrair is, onomatopeeën1 uitgesloten. Er is geen enkele zinnige reden dat we een stoel stoel noemen en een tafel tafel, het omgekeerde was namelijk ook acceptabel geweest. Daarnaast stelt de grammatica de mens in staat deze woorden te combineren tot een oneindig aantal mogelijke zinnen. Een lichtpuntje dat deels door de regels van de grammatica wordt verschaft is dat we in taal altijd structuur aantreffen. Deze patronen treffen we op alle niveaus van een tekst aan. Zo zit er structuur in de tekst als geheel, maar ook binnen de alinea’s, binnen de zinnen, en zelfs binnen de woorden. Zo wijkt de zinsstructuur van het

1

Onomatopee: een door klanknabootsing gevormd woord (bv. Tiktak, koekoek) [Bron: www.vandale.nl]

30

Engels vaak sterk af van die van het Nederlands en komt de lettercombinatie sch in het Nederlands en Duits veel vaker voor dan in het Frans. Deze patronen herhalen zich constant en zijn voor zowel mensen als computers te herkennen. Het is bekend dat het mogelijk is om deze patronen ‘af te korten’ en zo opslagruimte te besparen, maar misschien kan datacompressie ook nog voor andere doeleinden gebruikt worden. Dat laatste willen we in deze paper onderzoeken. [8]

1.1.8 Eerder onderzoek Zonder uitzondering zijn structuren in alle talen terug te vinden. Er zijn een aantal universele taalstructuren, en er zijn structuren die gezien kunnen worden als eigen aan een bepaalde taal. Dit laatste stelt ons in staat vast te stellen in welke taal een bepaald document geschreven is zonder het document te openen. Wanneer we bijvoorbeeld een tekst hebben die Nederlands óf Frans kan zijn, kunnen we erachter komen welke van de twee het is door deze tekst toe te voegen aan zowel een zip van een Frans corpus als een zip van een Nederlands corpus. Als de tekst Nederlands is zal de grootte van de Nederlandstalige zip minder toenemen dan de grootte van de Franse zip. Dit komt doordat het zip-programma in de Nederlandse tekst patronen herkent die hij al eerder heeft gezien in de andere Nederlandse teksten. Als de Nederlandse tekst aan de zip-file van het Franse corpus wordt toegevoegd moet het programma als het ware een andere taal leren. Het is in eerder onderzoek al bewezen dat zip-programma’s inderdaad kunnen helpen bij het identificeren van talen. [2] Het bleek zelfs mogelijk om de schrijver van een document te achterhalen aan de hand van teksten van een beperkt aantal schrijvers. Zo werd met behulp van een zip-programma bewezen dat schrijver Marek van der Jagt dezelfde persoon is als Arnon Grunberg. De schrijver en zijn pseudoniem maakten dus blijkbaar gebruik van bepaalde woorden en zinsstructuren die zoveel op elkaar leken dat ze wel van dezelfde hand moesten zijn. Het woordgebruik en de opbouw van een tekst is logischerwijs in eerste instantie afhankelijk van de taal waarin de tekst is geschreven, maar ook het onderwerp van een tekst bepaalt mede het vocabulaire en de structuur van de tekst. Zo wordt het dus mogelijk om een computerprogramma onderscheid te laten maken tussen teksten op basis van hun onderwerp, een eigenschap die voor zoekmachines wellicht interessant is. [9] Een ander onderzoek laat zien hoe je een zip-programma als spamfilter kun laten fungeren. [2] Je neemt een lijst met zogenaamde spam e-mails en zipt deze tot een bestand met grootte S. Vervolgens comprimeer je een lijst met ‘echte’ e-mails (ham) tot een bestand met grootte H. Een nieuwe e-mail, waarvan het niet bekend is of het spam of ham is, wordt aan beide zip-files toegevoegd en vormt daarmee de bestanden HT en HS. De e-mail wordt dan gekwalificeerd als ham wanneer HT – H < ST – S. WinRar schijnt hier overigens geschikter voor te zijn dan WinZip. [2] We mogen daarom aannemen dat de logaritmen waarmee WinRar werkt beter aansluiten bij de structuur van taal dan de logaritmen die door WinZip gebruikt worden.

31

Het is bij het toepassen van deze techniek dus van wezenlijk belang dat de efficiëntie van de compressie nauwkeurig wordt gemeten. Daarnaast bleek uit onderzoek dat de methode beter werkt bij langere teksten, omdat de kans op terugkerende patronen dan groter is. [2]

1.2 Vraagstelling en hypothese Kunnen we door middel van datacompressie taalfamilies onderscheiden binnen de 10 officiële Afrikaanse talen? We verwachten een significant verschil in de groottes van de zip-bestanden te vinden waaruit we verschillende taalfamilies af kunnen leiden. Zo is het bijvoorbeeld zeer voor de hand liggend dat Nederlands en Afrikaans samen een klein zip-bestand vormt, wat hun relatie aangeeft.

2 Methode 2.1 Corpus Het belangrijkste kenmerk van het corpus moet zijn dat de teksten die erin voorkomen vergelijkbaar zijn. Daarom is hier gekozen voor de Universele Verklaring voor de Rechten van de Mens. Naast het feit dat de teksten allemaal dezelfde inhoud hebben, zijn deze teksten ook gratis en eenvoudig verkrijgbaar in alle officiële talen van de wereld. [10] We hebben gekozen voor de officiële Afrikaanse talen volgens Wikipedia [11], met uitzondering van Engels, omdat deze taal als vanzelfsprekend ver af staat van de ‘echte’ Afrikaanse talen. Deze talen zijn: • Afrikaans • Ndebele • Noord-Sotho • Swazi / Siswati • Tsonga • Tswana • Venda (deze taal was niet in de lijst te vinden) • Xhosa • Zulu Deze talen hebben we opgezocht op eerdergenoemde site, en vervolgens opgeslagen in Joe. We hebben elk bestand de extensie .snl (deze was zelf verzonnen en staat voor ‘Stijn (e)n Luuk’) gegeven, omdat de manier van werken dit vereiste (i.e. dat alle bestanden eenzelfde, niet-bestaande extensie hebben). Enkele teksten bleken te lang in kladblokformaat. Op deze manier is het moeilijk oordelen: het zijn dan wel dezelfde teksten, maar als ze significant in omvang verschillen, is vergelijken een moeilijk karwei.

32

Om dit te verhelpen zijn we uit gegaan van de kleinste tekst, en alle andere teksten hebben we daarom verkleind – één alinea per keer, totdat de teksten in omvang veel meer op elkaar leken dan voorheen. De kleinste tekst vóór deze aanpassingen was de Ndebele (9069 bytes), en de grootste was Swazi / Siswati (17026 bytes). Na de veranderingen was de kleinste Zulu (9568 bytes). De grootste was Sotho (10401 bytes).

2.2 Verwerking in Gzip Nadat we alle afzonderlijke teksten hebben ingevoerd, hebben we de teksten onderworpen aan een computatie. Het doel van deze computatie was om een gecomprimeerd bestand te maken (in dit geval .gzip) voor elke mogelijke talencombinatie. Doel van dit alles zoeken naar gelijkenissen binnen de talen. De theorie zegt dat een .zip bestand kleiner wordt naarmate de talen meer op elkaar gaan lijken. Het zip-programma hoeft minder woorden / structuren te categoriseren en daarom kan er een groter percentage gecomprimeerd worden. Dit gebeurde middels het volgende script: for x in *.snl ; do for y in *.snl ; do cat $x $y > $x.$y gzip $x.$y done done

Vervolgens kregen we een lijst waar, op alfabetische volgorde, aller taalcombinaties uitkwamen plus de bestandsgrootte van elk paar. Hiervoor gebruikten we: dir *.snl.gz | awk '{print $5,$8}' –

Hieruit kwam een lijst met elke mogelijke taalcombinatie (inclusief twee keer dezelfde taal in eenzelfde bestand. Bestandsnamen zagen er uit als ‘Taal1.snl.Taal2.snl.gz’. Voor elke taal hebben we vervolgens gekeken wat de kleinste en wat de grootste combinatie was, en per taal de grootte van elk zipbestand genoteerd. Vervolgens zijn we op zoek gegaan naar structuur in de data.

33

3 Resultaten In tabel 1 zijn resp. de originele bestandsgroottes, de gezipte bestandsgroottes, en de compressiepercentages te vinden per taal weergegeven. Tabel 1 Taal

Bestandsgrootte

Bestandsgrootte gezipt

Compressiepercentage*

Afrikaans

9584

3628

62,15 %

Ndebele

9917

3434

65,37 %

Nederlands

9726

3628

62,70 %

Noord-Sotho

9743

3355

65,57 %

Sotho

10401

3505

66,30 %

Swazi / Siswati

10234

3938

61,52 %

Tsonga

10078

3537

64,90 %

Tswana

10130

3426

66,18 %

Xhosa

10127

3736

63,11 %

Zulu

9568

3690

61,43 %

* percentage van de originele bestandsgrootte

In tabel 2 staan alle bestandsgroottes nadat de twee aangegeven teksten samen gezipt zijn. Tabel 2 AFR

NDB

NED

NSO

SOT

SWA

TSO

TSW

XHO

ZUL

AFR NDB NED NSO SOT

3628

6738

6543

6646

6800

7235

6849

6725

7047

7005

6740

3434

6730

6469

6607

6890

6633

6535

6590

6449

6539

6732

3628

6644

6799

7230

6847

6733

7034

6995

6647

6451

6646

3355

6309

6959

6572

6196

6767

6722

6800

6595

6800

6301

3505

7095

6716

6350

6903

6862

SWA TSO TSW

7233

6852

7226

6959

7111

3938

7136

7035

7205

7059

6849

6613

6847

6573

6716

7106

3537

6637

6938

6866

6728

6512

6728

6196

6353

7015

6639

3426

6828

6789

XHO

7042

6564

7027

6771

6901

7214

6941

6830

3736

6751

ZUL

7005

6447

6999

6738

6876

7098

6905

6800

6767

3690

34

In tabel 3 is telkens aangeven, voor elke taal, welke zip het grootste bestand opleverde, en welke het kleinste. Tabel 3

Afrikaans Ndebele Nederlands Noord-Sotho Sotho Swazi/Siswati Tsonga Tswana Xhosa Zulu

Grootste zip met Swazi/Siswati Swazi/Siswati Swazi/Siswati Swazi/Siswati Swazi/Siswati Afrikaans Swazi/Siswati Swazi/Siswati Swazi/Siswati Swazi/Siswati

Kleinste zip met Nederlands Zulu Afrikaans Tswana Noord-Sotho Ndebele Ndebele Noord-Sotho Ndebele Ndebele

4 Conclusie en discussie Het eerste wat opvalt als we naar Tabel 3 kijken is dat Swazi/Siswati een taal is die blijkbaar sterk afwijkt van de andere 9 talen. Het originele bestand van deze taal was namelijk niet eens het grootst, maar levert in combinatie met elk van de andere talen wel duidelijk de grootste zip-bestanden op. Uit Tabel 1 blijkt ook dat Swazi/Siswati op zich een vrij moeilijk te comprimeren taal is, slechts 61,5%. Daarnaast blijkt uit Tabel 3 dat Ndebele vrij goed te comprimeren is met de talen Swazi/Siswati, Tsonga, Tswana, Xhosa en Zulu. Ook Noord-Sotho is aardig te zippen met andere talen: deze taal komt twee keer als kleinste uit de bus in combinatie met de talen Sotho en Tswana. Wat verder opvalt is de bevestiging van ons vermoeden dat Nederlands en Afrikaans goed samen gaan. Wanneer Nederlands en Afrikaans samen gezipt worden levert dit de kleinste zip-bestanden op. Ook wanneer een andere taal gezipt wordt met Afrikaans of Nederlands lijken de bestandsgroottes van de zip-bestanden op elkaar. Verder viel het ons op dat het zippen van twee talen verschillende bestandsgroottes op kan leveren, afhankelijk van de volgorde waarin zij gezipt worden. Zo is de grootte van de zip ndebele.snl.afrikaans.snl.gz niet gelijk aan afrikaans.snl.ndebele.snl.gz. Wanneer we kijken naar de rijen en kolommen van Tabel 2 lijken de bestandsgroottes van sommige zip-bestanden per taal overeen te komen. Zo lijken Xhosa en Zulu, Ndebele en Tswana, en Sotho en Tsonga onderling overeen te komen. Helaas zijn de verschillen in bestandsgrootte voor alle zip-bestanden zo miniem dat we geen significante conclusies hieraan kunnen verbinden.

35

Tot slot dient de vraag zich aan, in hoeverre we conclusies kunnen verbinden aan een wiskundige manier van talen ordenen. Is het betrouwbaar om uit te gaan van woorden en zinsconstructies, om hier vervolgens over te oordelen? Zijn dit alle kenmerken die nodig zijn bij het herkennen van taalverschillen, en is zip daadwerkelijk in staat om dit in overweging te nemen? We zijn geneigd om hier ‘nee’ te zeggen, temeer omdat we behalve de écht voor de hand liggende paren (zoals Nederlands en Afrikaans) geen significante groepen hebben geidentificeerd. Dit lijkt een interessant beginpunt voor volgend onderzoek, waarbij mogelijk grotere corpora gebruikt kunnen worden.

36

Referenties [1]

http://www.data-compression.com/theory.html

[2]

http://studeren.uva.nl/profielwerkstukken/object.cfm/objectid=A1004C1E-D819-468681555738A5945384/templateid=31A2F78E-0FC1-4A1F-812C0A64D30A526E

[3]

http://www.howstuffworks.com/file-compression.htm

[4]

Algoritme. (2007, maart 22). Wikipedia, de vrije encyclopedie. Opgehaald van http://nl.wikipedia.org/w/index.php?title=Algoritme&oldid=7414936.

[5]

Datacompressie. (2007, april 20). Wikipedia, de vrije encyclopedie. Opgehaald van http://nl.wikipedia.org/w/index.php?title=Datacompressie&oldid=7735517.

[6]

Huffmancodering. (2007, april 30). Wikipedia, de vrije encyclopedie. Opgehaald van http://nl.wikipedia.org/w/index.php?title=Huffmancodering&oldid=7839162.

[7]

Lempel Ziv Welch. (2007, mei 3). Wikipedia, de vrije encyclopedie. Opgehaald van http://nl.wikipedia.org/w/index.php?title=Lempel_Ziv_Welch&oldid=7873887.

[8]

V.Fromkin, R.Rodman & A.Neijt, Universele taalkunde, een inleiding in de algemene taalwetenschap, Foris Publications, Dordrecht, 1994 (6de druk).

[9]

http://unisi.com/stories/20021/0204024.htm

[10]

http://www.unhchr.ch/udhr/navigate/alpha.htm

[11]

Officiële talen van Zuid-Afrika. (2007, maart 10). Wikipedia, de vrije encyclopedie. Opgehaald van http://nl.wikipedia.org/w/index.php?title=Offici%C3%ABle_talen_van_ZuidAfrika&oldid=7257762.

37