Alignering van Tweetalige Corpora als Vertaalhulp

Alignering van Tweetalige Corpora als Vertaalhulp AFSTUDEERSCRIPTIE ALFA-INFORMATICA

ROBBERT PRINS

SCRIPTIEBEGELEIDER EN EERSTE LEZER

Prof. dr. ir. J. Nerbonne TWEEDE LEZER

Dr. G.J.M. van Noord

ALFA-INFORMATICA RIJKSUNIVERSITEIT GRONINGEN OKTOBER 2000

INHOUDSOPGAVE

Voorwoord

14

1

Inleiding

15

2

Probleemstelling

16

3

Introductie tot het onderwerp

17

3.1 Sequentievergelijking

18

3.2 Het Levenshtein algorithme

19

3.3 Toepassingen van tekstalignering

12

3.3.1 3.3.2 3.3.3 3.3.4 3.3.5

4

12 12 12 13 13

Overzicht van methoden

14

4.1 Statistische methoden 4.1.1 Zinslengte

15 15

4.2 Lexicale methoden

16

4.2.1 4.2.2 4.2.3 4.2.4

5

Machinaal vertalen Lexicale ambiguïteiten Dialectometrie Tweetalige concordanties Hulp bij vertaling

Verwante woorden Lexicon Woorddistributie Patroonherkenning

16 17 18 19

4.3 Conclusies

20

Implementatie van de Gale en Church methode

23

5.1 De verschilfunctie

23

Alignering van Tweetalige Corpora als Vertaalhulp

2

5.2 Berekening van de parameters 5.2.1 Het gemiddelde c 5.2.2 De variantie s2 5.2.3 De a priori kansen

6

27

5.4 Optimalisatie van het algorithme

28

5.5 Het opsplitsen van de tekst in kleinere delen

30

5.6 Het herkennen van zinsgrenzen

31

Resultaten

33

6.1 Aligneringsresultaten

33

6.2 Vergelijking met oorspronkelijke implementatie

35

6.3 Vergelijking met andere methoden

35

6.4 Computationele efficiëntie

36

6.5 Voorkomende problemen

37

6.5.1 Zinsherkenning 6.5.2 Geheugengebruik

37 37

6.6.1 Aantal woorden als lengtemaat 6.6.2 Taalonafhankelijk gemiddelde

8

26 26 27

5.3 Toepassing van het Levenshtein algorithme

6.6 Variaties binnen de methode

7

25

38 38 39

Presentatie van de alignering

40

7.1 Gebruikte operaties

40

7.2 Concordantie 7.3 Controle bij vertaling

40 40

Conclusie

42

Literatuurlijst

43

Bijlage: C++ broncode

45


3

VOORWOORD De studie Alfa-Informatica is een praktische studie. Dit komt ook naar voren in het scriptieonderzoek, dat vaak voor een deel bestaat uit het implementeren van een beschreven techniek. In het geval van mijn onderzoek resulteerde dit in een programma dat dient om vertalingen met elkaar in verband te brengen op zinsniveau. In dit verslag wordt beschreven hoe de methode functioneert, en hoe de implementatie verliep. Om de geïnteresseerde lezer in staat te stellen het programma zelf te bekijken of te modificeren is de broncode toegevoegd. Tot slot van dit voorwoord zou ik graag de heer Nerbonne willen bedanken voor het voorstellen van het onderwerp, en voor de begeleiding van mijn scriptieonderzoek.

Robbert Prins Ten Boer, oktober 2000


4

HOOFDSTUK 1

INLEIDING

Het scriptieonderzoek dat in dit verslag wordt weergegeven heeft als onderwerp tekstalignering. Tekstalignering, waarbij wordt gezocht naar correspondenties tussen teksten, wordt meestal gebruikt om data te verkrijgen voor verdere toepassingen, die dan vaak van computationele aard zijn. Zo wordt tekstalignering ingezet bij machinaal vertalen om gegevens te verzamelen die vervolgens de computer moeten helpen bij het vinden van vertalingen van andere teksten. Voor deze toepassing worden tweetalige corpora gealigneerd. Dit onderzoek richt zich op het aligneren van tweetalige corpora, en in het bijzonder op het taalpaar Nederlands-Engels. Als toepassing van de uiteindelijke alignering wordt niet een computationele toepassing voor ogen gehouden, maar een menselijke. Gealigneerde tweetalige teksten kunnen namelijk ook de menselijke vertaler op verschillende manieren van dienst zijn. De methode die wordt geïmplementeerd is die van Gale en Church (1993). Dit is een statistische benadering van het probleem, terwijl andere methoden tevens of uitsluitend gebruik maken van lexicale informatie. Binnen de methode wordt gebruik gemaakt van het Levenshtein algorithme, een techniek die via vergelijking en backtracking de optimale alignering tracht te achterhalen. Hoofdstuk 2 geeft via de probleemstelling weer wat de belangrijkste aandachtspunten en vragen in dit onderzoek zijn. Vervolgens zal in hoofdstuk 3 een introductie tot het onderwerp tekstalignering worden gegeven, waarbij dieper wordt ingegaan op het Levenshtein algorithme. Zowel de statistische methode van Gale en Church als lexicale methoden worden besproken en vergeleken in hoofdstuk 4. In hoofdstuk 5 wordt vervolgens de implementatie van de Gale en Church methode weergegeven. Hierbij wordt ook aandacht geschonken aan manieren om het algorithme te optimaliseren en aan het herkennen van zinsgrenzen. Dit laatste is een cruciaal onderdeel van de methode, waar in sommige andere onderzoeksverslagen in verhouding te weinig aandacht aan wordt besteed. De resultaten van de beschreven implementatie komen in hoofdstuk 6 aan de orde. Het gaat hier zowel om de kwaliteit van de alignering, als om de efficiëntie waarmee de alignering tot stand wordt gebracht. In dit hoofdstuk worden tevens de effecten van enkele variaties besproken die ook door Gale en Church werden toegepast. Met het oog op de voorziene toepassing wordt in hoofdstuk 7 kort ingegaan op enkele manieren waarop de alignering gepresenteerd zou kunnen worden. Hoofdstuk 8 vat uiteindelijk de eerdere hoofdstukken samen in een conclusie. De programmeercode van de implementatie is als bijlage aan dit verslag toegevoegd.


5

HOOFDSTUK 2

PROBLEEMSTELLING

Het aligneren van twee teksten houdt in dat tekstfragmenten uit één van de twee teksten worden geassocieerd met fragmenten uit de andere tekst, op grond van statistische of lexicale informatie. Gealigneerde tweetalige corpora kunnen gebruikt worden door systemen die machinaal vertalen, maar ook als vertaalhulp voor menselijke vertalers. Dit onderzoek richt zich op deze laatste toepassing. Een aligneerprogramma dat in de praktijk voor dit doel gebruikt zou worden, moet niet alleen een zo goed mogelijk resultaat afleveren in de vorm van een alignering, maar moet dit ook doen binnen een aanvaardbaar tijdsbestek en zonder de geheugencapaciteiten van de hardware te overschrijden. Verder moet het eindresultaat op een bruikbare manier gepresenteerd worden. De gekozen methode, te weten die van Gale en Church (1993), maakt gebruik van het Levenshtein algorithme. Aangezien dit algorithme quadratisch van aard is, moet extra aandacht worden geschonken aan de implementatie van een optimalisatie, aangezien ook langere teksten door het programma gealigneerd moeten kunnen worden. Aan de hand van testdata in het Nederlands en het Engels zal worden bepaald hoe goed de implementatie voldoet. Het resultaat van de methode wordt uitgedrukt in een foutenpercentage, zoals ook in andere onderzoeken het geval is. Op deze wijze kunnen vergelijkingen worden getrokken met andere methoden, waaronder methoden die gebruik maken van lexicale informatie alsmede methoden die aligneren aan de hand van statistische informatie, en met de oorspronkelijke implementatie van de onderzoekers Gale en Church.


6

HOOFDSTUK 3

INTRODUCTIE TOT HET ONDERWERP

Tweetalige corpora vormen een waardevolle bron van informatie voor verscheidene doeleinden. Teksten die dezelfde inhoud hebben, maar in de gebruikte taal van elkaar verschillen, kunnen worden gebruikt als data voor toepassingen die met vertalen te maken hebben. Hieronder valt het onderzoeksgebied van machinaal vertalen, maar ook menselijke vertalers kunnen de corpora gebruiken om hun eigen vertalingen te verbeteren. Uiteraard is het zo dat een eenvoudig woordenboek wellicht de belangrijkste hulp van de vertaler is, maar een tweetalige tekst heeft als voordeel dat er complete uitdrukkingen in voor kunnen komen en dat deze uitdrukkingen, of losse woorden, altijd in een context staan. Deze context kan bepalend zijn voor de correcte vertaling. Wil de vertaler een tweetalig corpora op een dergelijke manier kunnen gebruiken, dan heeft hij niet genoeg aan een set van twee teksten zonder meer. De teksten moeten met elkaar in verband worden gebracht, zodat inhoudelijk overeenkomstige delen in beide teksten met elkaar geassocieerd zijn. Om dit te bereiken moeten de teksten worden gealigneerd. Het aligneren van twee teksten houdt in dat ze op een bepaald niveau aan elkaar worden gekoppeld, op grond van één of meer gekozen criteria. Het niveau waarop wordt gealigneerd hangt vaak nauw samen met de gekozen criteria, en deze verschillen van methode tot methode. Figuur 1 is een voorbeeld van een alignering op zinsniveau van een tekst in het Nederlands en het Engels. In de praktijk zijn er twee stromingen aan te wijzen binnen de geautomatiseerde aligneringstechnieken: methoden die gebruik maken van statistische gegevens en methoden die gebruik maken van lexicale informatie. Een veel gebruikt statistisch gegeven is de lengte van de eventueel te koppelen zinnen. Lexicale informatie kan bestaan uit een database waarin woorden uit de eerste taal opgeslagen zijn, tezamen met de vertaling in de tweede taal. Een dergelijk lexicon kan overigens het product zijn van eerdere aligneringen. Hij wees naar het uiteinde van de grafzerk die hij aan het bewerken was, en ik ging zitten. 'Dat is een opvallend mooi stuk marmer wat u daar hebt,' zei ik. Hij schudde zijn hoofd. 'In zekere zin, ja,' antwoordde hij. 'De bovenkant die u ziet is zo mooi als je maar wensen kunt, maar aan de onderkant zit een lelijke zwakke plek, al denk ik niet dat u 't ooit op zou merken.

He pointed to the end of the gravestone on which he was at work, and I sat down. 'That's a beautiful piece of stone you've got hold of,' I said. He shook his head. 'In a way it is,' he answered; 'the surface here is as fine as anything you could wish, but there's a big flaw at the back, though I don't expect you'd ever notice it.

figuur 1: voorbeeld van een tweetalige alignering (tekst uit: August Heat, W.F. Harvey)


7

3.1 Sequentievergelijking Aan de basis van tekstalignering, een vorm van sequentiealignering, staat sequentievergelijking. Toepassingen van sequentievergelijking zijn in te delen in twee categoriën, te weten discreet en continu (Kruskal 1983). In het discrete geval is er sprake van elementen die deel uit maken van een alfabet. Dit alfabet kan bestaan uit letters, maar in het geval van DNA sequenties, een ander mogelijk onderwerp van sequentievergelijking, komen de elementen uit het alfabet van de aminozuren. De continue variant gebruikt niet een eindige set van elementen, maar functiewaarden. Deze waarden zijn vaak een functie van de tijd. Wanneer tekstalignering wordt uitgevoerd op het niveau van de afzonderlijke letters dan ligt het voor de hand dit tot de discrete categorie te rekenen. Het is ook mogelijk, zoals in dit onderzoek zal blijken, om gebruik te maken van statistische gegevens zoals de lengtes van de zinnen in beide teksten. In dat geval is het onderwerp van de alignering in feite een sequentie van getallen. Deze toepassing is eveneens een voorbeeld van een discreet geval, aangezien het hier uitsluitend om gehele getallen gaat. Het verschil tussen twee sequenties wordt door Levenshtein (1966) beschreven als het kleinste aantal elementaire operaties dat nodig is om de eerste sequentie te veranderen in de tweede sequentie. De elementaire operaties waar Levenshtein op doelt zijn insertie, deletie en substitutie. Het uiteindelijke aantal benodigde operaties is een maat voor het verschil tussen de sequenties. Wanneer er voor wordt gekozen om een bepaald gewicht aan de operaties toe te kennen, zodat een kwantitatief onderscheid tussen de verschillende operaties kan worden gemaakt, dan is het verschil gelijk aan het totale gewicht van de gebruikte operaties. Het gewicht dat aan een uit te voeren stap wordt toegekend kan mede afhankelijk zijn van de elementen waarop de operatie van toepassing is. Als het verschil tussen twee sequenties op deze manier is bepaald, dan is tevens een optimale opeenvolging van operaties gevonden die dit verschil overbrugt. Hierin ligt besloten welke elementen uit de eerste sequentie worden vervangen door welke elementen uit de tweede sequentie en welke elementen dienen te worden verwijderd of juist toegevoegd. Wanneer vervolgens deze informatie wordt gebruikt, niet om de eerste sequentie daadwerkelijk te veranderen, maar om beide sequenties op de aangegeven wijze aan elkaar te koppelen, dan is sprake van sequentiealignering.

[F R I E T . . .] [F . I E T S E N]

[F R I E T . .] [F I E T S E N]

figuur 2: twee mogelijke aligneringen

In de voorbeelden afgebeeld als figuur 2, waarin het aligneren gebeurt op het niveau van de afzonderlijke letters, worden zowel substitutie als insertie en deletie toegepast om het woord friet te aligneren aan het woord fietsen. De inserties en deleties die nodig zouden zijn om het eerste woord in het tweede te veranderen, worden weergegeven door gebruik te maken van lege posities, terwijl in het geval van substitutie de te vervangen letter boven de nieuwe letter staat. De eerste alignering is optimaal te noemen. Als men er van uit gaat dat een substitutie uitgevoerd op twee


8

identieke letters minder zwaar weegt dan een substitutie van twee verschillende letters, dan is deze alignering te verkiezen boven de tweede alignering.

3.2 Het Levenshtein algorithme Een algorithme dat in staat is om een sequentievergelijking uit te voeren, op basis van het hierboven beschreven principe dat het verschil tussen twee sequenties het kleinste aantal operaties is dat nodig is om de eerste sequentie te veranderen in de tweede, is het Levenshtein algorithme. Dit algorithme is een toepassing van dynamisch programmeren, een concept dat voor het eerst werd beschreven door Richard Bellman (1957). Het belangrijkste idee van dynamisch programmeren is dat een probleem wordt opgelost door vanuit elke zich aandienende toestand van het probleem een optimale stap te ondernemen naar een volgende toestand. Door op deze manier steeds kleine subproblemen aan te pakken, wordt een oplossing voor het geheel gevonden. Het Levenshtein algorithme gebruikt geheugenruimte en rekentijd in een hoeveelheid die gelijk is aan de lengte van de eerste sequentie, vermenigvuldigd met de lengte van de tweede sequentie. Wanneer beide sequenties de lengte n hebben, dan wordt n2 aan geheugen en tijd gebruikt. Dit quadratische geheugengebruik komt voort uit het feit dat het algorithme elk element uit de eerste sequentie vergelijkt met elk element uit de tweede sequentie. Op deze manier kan uit alle mogelijke aligneringen de optimale alignering gekozen worden. De vergelijkingen worden uitgevoerd door gebruik te maken van een matrix. Op de horizontale en verticale as van de matrix worden respectievelijk de doelsequentie, met lengte n, en de bronsequentie, met lengte m, geplaatst. Figuur 3 toont de matrix voor een vergelijking van de sequenties friet en fietsen.

0

F

I

E

T

S

E

N

1

2

3

4

5

6

7

0 F

1

R

2

I

3

E

4

T

5 figuur 3: de matrix

De op deze manier geconstrueerde matrix geeft het aligneringsprobleem in zijn geheel weer. Het algorithme begint in de linkerbovenhoek van de matrix op positie (0,0). Alignering van Tweetalige Corpora als Vertaalhulp

9

Deze positie is de begintoestand van het probleem, en de positie rechtsonder, positie (n,m), is de doeltoestand. De tussenliggende posities vormen, tezamen met de doeltoestand, de subproblemen die in de geest van dynamisch programmeren door het algorithme moeten worden opgelost. Dit houdt in dat voor elke positie moet worden bepaald welke elementaire operatie wordt gekozen. Deze elementaire operaties hebben betrekking op de elementen die op de corresponderende posities in de op de beide assen geplaatste sequenties worden aangetroffen. Als de sequenties a en b zijn, dan bestaan de subsequenties ai en bj uit de elementen a1⋅⋅⋅ai en b1⋅⋅⋅bj. Om alle mogelijke toestanden van het probleem te betrekken in de zoekactie naar de optimale alignering, begint het algorithme in de eerste kolom, j = 0, in de eerste rij, i = 0, en bepaalt het vervolgens voor een steeds groter wordende i de te nemen stap op posities (0,i). Hierna wordt de volgende kolom behandeld, totdat uiteindelijk ook de laatste kolom aan de beurt is geweest. Voor elke positie (j,i) wordt bepaald hoe groot het verschil tussen de tot dan toe behandelde subsequenties is en welke operatie geselecteerd moet worden om dit verschil zo klein mogelijk te houden. Het verschil op positie (0,0) wordt op nul gesteld, aangezien de twee subsequenties met lengte nul niet van elkaar verschillen. De laatste positie in de matrix bevat uiteindelijk de waarde die staat voor het verschil tussen de beide totale sequenties a en b. Om te kiezen tussen insertie, deletie en substitutie, moet worden berekend welke operatie het kleinste totale verschil oplevert. Dit totale verschil bestaat uit het verschil zoals dat in de vorige toestand bestond, opgeteld bij het gewicht van de gekozen operatie. Deze operatie bepaalt welke positie in de matrix gebruikt wordt als vorige toestand. De minimalisatie kan als volgt worden weergegeven, waarbij d(ai, bj) staat voor het verschil tussen de eerder behandelde subsequenties ai en bj, en w(ai,bj) voor het gewicht van de betreffende operatie uitgevoerd op de elementen ai en bj:

d(ai, bj) = min

d(ai, bj-1) + w(0, bj)

(insertie van bj)

d(ai-1, bj) + w(ai, 0)

(deletie van ai)

d(ai-1, bj-1) + w(ai, bj)

(substitutie van ai door bj)

Wanneer bijvoorbeeld op positie (j,i) wordt gekozen voor insertie van bj, dan wordt het totale verschil tussen ai en bj berekend als het verschil tussen de subsequenties ai en bj-1, verhoogd met het gewicht dat de insertie van het element bj met zich meebrengt. Per subprobleem wordt niet alleen het totale verschil tussen de subsequenties tot dan toe opgeslagen, maar ook de geselecteerde operatie. Als de sequentievergelijking afgerond is, dan zal deze informatie worden gebruikt om de alignering te achterhalen. Figuur 4 laat zien hoe de operaties in de vorm van verwijzingen worden opgeslagen. De pijlen, die ook wel pointers worden genoemd, wijzen vanaf de positie waarop de operatie betrekking heeft, naar de positie die de vorige toestand representeert.


10

b

1

2

1

1

b

2

1

1

a

2

1

a 2

b

a 2

substitutie van a2 door b2

2 insertie van b2

deletie van a2

figuur 4: substitutie, insertie en deletie

Aangezien de operatiepointers steeds terugwijzen naar het vorige subprobleem en er per subprobleem een optimale operatie wordt gekozen voor de bij die toestand behorende subsequenties, wordt de uiteindelijke alignering in omgekeerde volgorde verkregen door vanuit de laatste positie de pointers terug te volgen naar de eerste positie. Dit proces wordt ook wel backtracking genoemd. Figuur 5 toont de matrix voor de vergelijking van de sequenties friet en fietsen, nadat het Levenshtein algorithme alle mogelijkheden berekend heeft. De weergave is vereenvoudigd zodat alleen de pointers die de optimale alignering vormen te zien zijn.

0

F

I

E

T

S

E

N

1

2

3

4

5

6

7

0 F

1

R

2

I

3

E

4

T

5 figuur 5: de matrix na toepassing van het algorithme


11

3.3 Toepassingen van tekstalignering Sequentievergelijkingstechnieken in het algemeen worden in veel gebieden van de wetenschap toegepast, aangezien sequenties bijna overal voorkomen. Enkele voorbeelden hiervan zijn DNA, taal en muziek. Kruskal (1983) geeft dan ook onder andere de volgende toepassingsgebieden: moleculaire biologie, informatica, gas chromotografie en spraak. Binnen het toepassingsgebied van de taalwetenschappen kan de sequentievergelijking worden gebruikt om onderscheid of juist overeenkomst tussen twee teksten te ontdekken. Het aligneren van teksten is hiervan afgeleid. De techniek wordt gebruikt bij het machinaal vertalen, bij het oplossen van lexicale ambiguïteiten, in de dialectometrie en als hulp bij het vertalen.

3.3.1 Machinaal vertalen Machinaal vertalen wordt onder andere door Gale en Church (1993) en Church (1993) genoemd als toepassingsgebied. Met behulp van tekstalignering kan een probabilistisch woordenboek worden geconstrueerd, dat bij het vertalen door de computer gebruikt kan worden als hulp bij het construeren van de meest waarschijnlijke vertaling. Dit gebeurt bijvoorbeeld in (Brown et al. 1990), waarin het probleem van machinaal vertalen statistisch wordt benaderd. Hierbij maakt men gebruik van taal- en vertaalmodellen, waarvan de parameters worden ingevuld door te kijken naar data van bestaande vertalingen. Deze data werd verkregen door een deel van de Canadese Hansards te aligneren. Dit corpus is een verslag van de bijeenkomsten van het Canadese parlement, in het Engels en het Frans. De Engelse versie van het gebruikte deel was 100 miljoen woorden groot. De aligneermethode maakte gebruik van de zinslengtes om de zinnen aan elkaar te koppelen, en de uiteindelijk verkregen set van zinsparen bestond voor 99 procent uit daadwerkelijke vertalingen.

3.3.2 Lexicale ambiguïteiten Lexicale ambiguïteiten kunnen een probleem vormen bij het machinaal vertalen, of in het algemeen bij een computationele toepassing waarbinnen met taal wordt gewerkt. Statistische gegevens die verkregen worden met behulp van alignering kunnen worden gebruikt voor het desambigueren van de betekenis van woorden (Blank 1995). Hierbij wordt statistische informatie over lexicale relaties binnen een taal gebruikt om de betekenis van een woord te koppelen aan een woord in een andere taal. Juist omdat bij toepassingen van statistische aard grote hoeveelheden data verwerkt moeten worden, is het automatiseren van een proces als tekstalignering hier van belang.

3.3.3 Dialectometrie Binnen de dialectometrie houdt men zich bezig met het onderzoeken van dialecten. Door de computer hierbij in te zetten kunnen grote hoeveelheden data verwerkt worden, bestaande uit teksten die in de te onderzoeken dialecten zijn uitgesproken. Op deze wijze kunnen verschillende dialecten op statistische gronden met elkaar worden vergeleken. Aangezien tekstalignering een toepassing van sequentievergelijking is, Alignering van Tweetalige Corpora als Vertaalhulp

12

zijn veel methoden in staat om een zekere verschilwaarde af te leveren. Deze waarde komt overeen met de minimale kosten die nodig zijn om de twee teksten aan elkaar te aligneren. Een dergelijk verschilwaarde kan, bij gebruik van omvangrijke hoeveelheden data, geprojecteerd worden op de dialecten zelf. In (Nerbonne 1999) wordt beschreven hoe met dit doel voor ogen de Levenshtein afstand wordt bepaald tussen verschillende manieren waarop een woord wordt uitgesproken.

3.3.4 Tweetalige concordanties In veel gevallen van tekstalignering vindt de koppeling tussen de teksten op zinsniveau plaats. Wanneer de teksten ieder in een andere taal zijn geschreven, dan kan met behulp van alignering een tweetalige concordantie worden gemaakt (Gale en Church 1993). Vertalers hebben soms moeite met het vinden van het equivalent van een uitdrukking in een vreemde taal. Hierbij kan een uitgebreide tweetalige concordantie van pas komen. De vertaler kan hierin complete uitdrukkingen en nieuw ontstane woorden terugvinden, die wellicht in een regulier woordenboek niet te vinden zijn. Verder speelt binnen een concordantie de context van een woord, die bepalend kan zijn voor de juiste vertaling, een grote rol.

3.3.5 Hulp bij vertaling Naast het gebruik voor het vervaardigen van een concordantie kan de vertaler een alignering ook inzetten in de oorspronkelijke vorm. Hierbij valt te denken aan een student in een vreemde taal, die de alignering gebruikt om zijn of haar eigen vertaling te controleren op fouten. Uiteraard moet de alignering hiervoor van goede kwaliteit zijn. Het is waarschijnlijk dat het resultaat van een aligneerprogramma voor een dergelijke toepassing uitgebreid wordt gecontroleerd alvorens in de praktijk te worden gebruikt, maar desalniettemin vormt de automatisch verkregen alignering een zeer goed uitgangspunt.


13

HOOFDSTUK 4

OVERZICHT VAN METHODEN

Methoden ter alignering van teksten zijn over het algemeen in te delen in twee groepen: methoden die alleen gebruik maken van statistische gegevens, en methoden die, vaak naast statistische gegevens, gebruik maken van lexicale informatie. In het laatste geval wordt de lexicale inhoud van de teksten betrokken bij de vergelijking, terwijl in het eerste geval slechts van oppervlakkige kenmerken zoals zinslengte gebruik wordt gemaakt. In de nu volgende paragrafen zal een reeks van implementaties worden beschreven. De gebruikte vergelijkingscriteria worden vermeld, alsmede optredende problemen en oplossingen voor deze problemen, en verkregen resultaten. De eerste paragraaf beschrijft de methode van Gale en Church (1993). Deze methode zal in de rest van het onderzoek worden geïmplementeerd. De Gale en Church methode gebruikt uitsluitend statistische informatie, in de vorm van zinslengtes, terwijl de overige methoden tevens gebruik maken van lexicale gegevens. In de laatste paragraaf van dit hoofdstuk worden de verschillen en overeenkomsten tussen de methoden nader toegelicht, waarbij punten als snelheid en kwaliteit van het resultaat aan bod zullen komen. Lexicale methoden berusten vaak op het idee van verwante woorden, in het Engels aangeduid met de term cognates. Dit zijn woorden die in twee talen op een vergelijkbare manier worden geschreven en dezelfde betekenis hebben. Door naar verwante woorden te zoeken zijn punten binnen twee teksten te aligneren, zodat ook de rest gealigneerd kan worden. Het gebruik van deze techniek werd voorgesteld door Simard, Foster en Isabelle (1992), als aanvulling op de uitsluitend statistische methode die zinslengte gebruikt als vergelijkingscriterium. De methode beschreven door Church (1993) maakt in feite gebruik van verwante woorden doordat op letterniveau wordt vergeleken. Overeenkomende letters die in elkaars buurt voorkomen zorgen voor een connectie, met als gevolg dat grotendeels identiek geschreven woorden voor veel connecties zullen zorgen. Chen (1992) beschrijft een methode die eerder gealigneerde teksten gebruikt om een lexicon vast te stellen, dat vervolgens toegepast wordt bij het aligneren van andere teksten. Een vergelijkbare methode wordt beschreven door Kay en Röscheisen (1993) en Fung en Church (1994). Bij deze methoden wordt het lexicon echter opgebouwd uit de onder behandeling zijnde teksten zelf. De laatste methode, van Melamed (1999), gebruikt patroonherkenning om teksten te aligneren. Hierbij wordt tevens gebruik gemaakt van een lexicon en van verwante woorden.


14

4.1 Statistische methoden 4.1.1 Zinslengte: Gale en Church (1993) Gale en Church (1993) geven een beschrijving van een aligneringsmethode die de lengte van de zinnen gebruikt om de teksten te aligneren. Hierbij wordt er van uit gegaan dat een lange zin in de ene taal meestal zal worden vertaald met een lange zin in de andere taal en dat korte zinnen worden vertaald met korte zinnen. Als lengtemaat wordt het aantal letters in een zin genomen. Het Levenshtein algorithme wordt gebruikt om aan de hand van de zinslengtes de beste alignering te vinden. In deze implementatie is echter niet alleen sprake van de elementaire operaties insertie, deletie en substitutie, maar ook van contractie, expansie en swap. Contractie houdt in dat twee zinnen worden vervangen door een enkele zin. Expansie behelst het omgekeerde geval, waarbij één zin wordt vertaald met twee zinnen. De swap wordt gebruikt wanneer twee zinnen worden vertaald met twee andere zinnen, waarbij de betekenis die door de eerste twee zinnen wordt uitgedrukt in een andere volgorde of samenstelling in de twee andere zinnen terugkeert. Dit is bijvoorbeeld het geval wanneer de zinnen worden omgedraaid, of wanneer een gedeelte van de eerste zin in de vertaling in de tweede zin terecht komt. Zoals bij de uitleg over het Levenshtein algorithme werd beschreven, gebruikt dit algorithme een waarde die het gewicht van de gekozen elementaire operatie, uitgevoerd op de betreffende elementen, weergeeft. Voor elke operatie geldt dat het gewicht wordt bepaald aan de hand van een verschilfunctie, die een waarde toekent aan het verschil tussen de elementen. De verschilfunctie die in de methode van Gale en Church wordt gebruikt is gebaseerd op de kans dat twee zinnen, gegeven hun lengte, vertalingen van elkaar zouden zijn. Van deze kans wordt de negatieve waarde genomen en de logarithme, zodat een bruikbare afstandsmaat ontstaat die toeneemt bij een kleiner wordende kans. De uiteindelijke functie is -log Prob(match | δ). De waarde delta staat voor het lengteverschil tussen de twee zinnen. Het uitgangspunt bij de berekening van dit verschil is dat een karakter in taal L1 een willekeurig aantal karakters genereert in taal L2 wanneer het vertaald wordt. Delta wordt berekend door de verdeling van deze aantallen, die normaal is, te standaardiseren via de functie (l2 - l1c) / √(l1s2). Hierbij staat c voor het gemiddelde aantal karakters dat een karakter in L1 genereert in L2, s2 voor de variatie binnen de verdeling, en l1 en l2 voor de lengtes van de twee zinnen. Voordat het programma kan beginnen met de alignering moeten de teksten zijn opgesplitst in zinnen. Dit is een lastig proces, maar Gale en Church gebruiken een methode die een acceptabel resultaat oplevert. Vervolgens worden de overeenkomende paragrafen bij elkaar gezocht. Dit gebeurt ook automatisch, maar titels van hoofdstukken en andere losstaande tekstelementen leveren soms problemen op. Het is voor een programma moeilijk om paragrafen te aligneren doordat de teksten op dit punt vaak niet helemaal overeenkomen en omdat ook binnen een tekst de paragraaf indeling onduidelijk kan zijn. De resultaten worden door Gale en Church dan ook met de hand gecontroleerd. De resultaten van de gebruikte methode zijn goed. De auteurs merken op dat het te behandelen corpus mede het resultaat bepaalt; met een Engels-Duitse tekst combinatie werden betere resultaten bereikt dan met dezelfde tekst in het Engels en het Frans. Als verklaring hiervoor wordt opgegeven dat de Duitse tekst het origineel was. Hierdoor verschilt het Engels-Duitse paar één vertaling van elkaar, terwijl de Engelse en de Franse tekst twee vertalingen van elkaar verschillen. Alignering van Tweetalige Corpora als Vertaalhulp

15

In plaats van het aantal letters per zin, kan ook het aantal woorden per zin als lengtemaat worden gebruikt. Deze variatie wordt door Gale en Church toegepast, maar levert een veel minder goed resultaat op. Als verklaring hiervoor wordt aangevoerd dat een zin meer letters dan woorden bevat. Letters zijn hierdoor een betrouwbaardere lengtemaat dan woorden. Een toevoeging die wel tot een beter resultaat leidde was het uitbreiden van de set van mogelijke koppelingen. Een zin hoeft niet altijd aan één zin in de andere tekst te worden gekoppeld: soms is er sprake van bijvoorbeeld een 1-2 of 2-1 verhouding. Gale en Church hielden aanvankelijk geen rekening met een 2-2 koppeling. Nadat deze mogelijkheid was toegevoegd, werden ook aligneringen uit deze categorie in de meeste gevallen goed uitgevoerd. De methode zoals beschreven door Gale en Church werd door Tjong Kim Sang (1996) gebruikt bij het aligneren van het zogenaamde Scania corpus. In dit onderzoek werd getoetst of de methode ook bij andere dan de door Gale en Church in hun onderzoek betrokken talen bruikbaar is. In het geval van het Scania corpus gaat het om de taalcombinaties Zweeds-Nederlands, Zweeds-Engels, Zweeds-Fins, ZweedsFrans, Zweeds-Duits, Zweeds-Italiaans en Zweeds-Spaans. Over het geheel werd een score behaald van 93 procent correcte aligneringen. Evenals bij het onderzoek van Gale en Church worden alleen de 1-1, 1-2 en 2-1 categoriën herkend. De 2-2 categorie, die wel door het algorithme wordt ondersteund, kwam niet in het corpus voor.

4.2 Lexicale methoden 4.2.1 Verwante woorden: Church (1993) In plaats van het aligneren van zinnen, kan ook op een lager niveau worden gealigneerd. Church (1993) beschrijft een programma dat teksten aligneert op letterniveau. Het voordeel hiervan is dat de methode geen last heeft van de eerder beschreven problemen bij het vinden van paragraaf- en zinsgrenzen. Deze problemen ontstaan volgens Church doordat teksten, vooral wanneer ze met behulp van een OCR proces zijn verkregen, vaak ruis bevatten. De methode maakt gebruik van het eerder beschreven concept van verwante woorden. Een voorbeeld dat gegeven wordt is het Engelse government en het Franse gouvernement. Niet alleen talen die veel van dergelijke woorden delen, als het Engels en het Frans, kunnen op deze manier vergeleken worden, ook andere talen die gebruik maken van het Romeinse alfabet komen in aanmerking; eigennamen, plaatsnamen, jaartallen en andere getallen worden in veel talen op dezelfde manier geschreven. De tekens worden met elkaar vergeleken door middel van een zogenaamde dotplot. Hiervoor worden beide teksten ieder op een as van een puntsdiagram geplaatst. Elke positie op de ene as wordt vergeleken met elke andere positie op de andere as. Hierbij moet worden opgemerkt dat Church niet afzonderlijke tekens met elkaar vergelijkt, maar vier-grammen; sequenties van vier tekens. Wanneer de twee vier-grammen overeenkomen, wordt een punt geplaatst op de corresponderende positie in de diagram. Een voorbeeld van een dergelijke dotplot is afgebeeld als figuur 6. De meeste punten bevinden zich op de diagonaal die van linksboven naar rechtsonder loopt. Dit betekent dat de teksten die op de beide assen zijn geplaatst inderdaad een grote gelijkheid vertonen; identieke vier-grammen komen op dezelfde posities in de twee teksten voor.


16

figuur 6: een dotplot (bron: Church 1993)

In de praktijk wordt een bereik B vastgesteld voor de te vergelijken tekens: een teken op positie i in de eerste sequentie wordt vergeleken met de tekens vanaf positie (i - B) tot en met positie (i + B) in de tweede sequentie. Het gevolg is een verkleining van de benodigde hoeveelheid geheugenruimte en rekentijd.. Dit bereik wordt de verticale resolutie genoemd. Er is ook sprake van horizontale resolutie; deze maat bepaalt hoeveel vergelijkingen in feite worden weergegeven door hetzelfde punt in het diagram. Wederom is het namelijk zo dat er bij het aligneren van grote teksten teveel geheugen nodig zou zijn om elke vergelijking apart te noteren. Zowel de verticale als de horizontale resolutie worden tijdens het aligneerproces aangepast om het best mogelijke resultaat te verkrijgen. Wanneer de bereiken immers te laag worden ingesteld, is het mogelijk dat het algorithme nooit de correcte koppeling kan vinden omdat die buiten het bereik gezocht moet worden. Elk gekoppeld n-gram wordt een bepaald gewicht toegekend. De minst frequente n-grammen wegen het zwaarst mee in de alignering, en de meest frequente ngrammen kunnen worden genegeerd. Dit levert een beter resultaat op en vooral een grote tijdwinst. De beste alignering wordt uiteindelijk gevonden door binnen het puntsdiagram te zoeken naar het pad met het grootste gemiddelde gewicht. De methode verkiest korte paden boven lange paden en paden met veel treffers boven paden met weinig treffers. Zoals eerder werd vermeld is het bij deze methode niet nodig om bestaande grenzen in de tekst, zoals paragraafgrenzen, te gebruiken. De belangrijkste reden om een tekst eerst onder te verdelen in paragrafen is dat de op deze wijze ontstane korte tekstdelen makkelijker te aligneren zijn. De methode werkt dan ook minder goed al naar gelang de te aligneren tekst langer is.

4.2.2 Lexicon: Chen (1993) Een tweede aligneermethode die gebruik maakt van lexicale informatie kijkt naar de individuele woorden. Door het programma te trainen op een reeds gealigneerde tekst wordt een serie van tweetalige woordparen verkregen met daarnaast de kans dat het betreffende woordpaar optreedt. Dit lexicon wordt bij het aligneren van twee teksten Alignering van Tweetalige Corpora als Vertaalhulp

17

gebruikt om de kans te berekenen dat twee zinnen inderdaad elkaars vertaling zijn. Deze methode, die wordt beschreven door Chen (1993), maakt net als andere programma's gebruik van een dynamisch programmeer algorithme. Om de rekentijd te verkorten en de benodigde geheugenruimte te verkleinen werd thresholding toegepast. Dit houdt in dat gedurende het zoeken naar de meest waarschijnlijke alignering gedeeltelijke aligneringen die een substantieel lagere waarschijnlijkheid vertonen dan de op dat moment meest waarschijnlijke alignering worden uitgesloten van het zoekproces. Dit heeft als resultaat dat de benodigde berekeningen lineair worden in tijd en geheugenruimte in plaats van quadratisch. Ondanks deze optimalisatie is de methode nog altijd veel langzamer dan de methoden die zinslengte als vergelijkingscriterium gebruiken. De aligneersnelheid bedroeg bij Chen 2000 tot 5000 zinnen per uur. Daar staat tegenover dat de resultaten beter zijn. Doordat gebruik wordt gemaakt van lexicale informatie worden erg grote fouten vermeden die wel kunnen worden gemaakt door programma's die deze informatie niet gebruiken. Als verdere verbetering wordt genoemd het toevoegen van een geavanceerder model voor woordvolgorde aan het vertaalmodel. Hier wordt bij vermeld dat een dergelijke toevoeging eveneens een grotere rekenkracht vereist.

4.2.3 Woorddistributie: Kay en Röscheisen (1993) en Fung en Church (1994) De methode beschreven door Kay en Röscheisen (1993) maakt uitsluitend gebruik van gegevens die in de te aligneren teksten besloten liggen. Dit betekent dat er geen externe lexicons aan te pas komen. De methode vergelijkt de distributie van woorden in de twee teksten om te achterhalen of het om dezelfde woorden gaat. Vervolgens wordt deze kennis gebruikt om de teksten te aligneren. In dit proces worden drie belangrijke tabellen gebruikt: een set van woordparen, een set van mogelijke zinskoppelingen en een tabel met daarin de zinsparen die de uiteindelijke alignering vormen. De eerste stap is het vullen van de tabel voor woordparen met woorden die worden gekoppeld op basis van hun distributie. De distributie van twee woorden vertoont overeenkomst als het eerste woord voorkomt in een zin in de eerste tekst en het tweede woord in een zin uit de tweede tekst die kandidaat is voor alignering met de zin uit de eerste tekst. Deze set van mogelijke koppelingen van zinnen wordt aanvankelijk opgesteld aan de hand van de posities van de zinnen in de tekst. Hierbij geldt dat hoe dichter een zin bij het midden van de tekst ligt, hoe meer mogelijke koppelingen er zijn met zinnen uit de andere tekst. De set woordparen die op deze manier wordt samengesteld wordt vervolgens gebruikt om een set van zinsparen te maken. Voor elke connectie tussen twee zinnen, gemaakt op basis van de woordparen, wordt bijgehouden hoe vaak deze correspondentie wordt onderschreven door de set van woordparen. Met behulp van deze informatie wordt de verzameling van mogelijke koppelingen weer bijgesteld, en begint het proces opnieuw. Bij een test met teksten van enkele honderden regels bleek dat de methode geen moeite had met het verschijnsel waarbij een enkele zin vertaald wordt door meerdere zinnen, noch met het omgekeerde geval. Het algorithme staat meerdere connecties per zin toe. Ook het resultaat bij een langere tekst, samengesteld uit twee dagen van het Frans-Engelse Hansard corpus, was zeer goed. De eerste 1000 gealigneerde zinnen werden met de hand gecontroleerd en vertoonden zeven fouten. Hiervan werden vijf Alignering van Tweetalige Corpora als Vertaalhulp

18

fouten veroorzaakt door het niet juist detecteren van zinsgrenzen. Voor het aligneren waren vijf omlopen van het algorithme nodig, waarbij de benodigde rekentijd, die aanvankelijk ongeveer acht minuten bedroeg op een Sun 4/ 75, per keer afnam. Uit verder onderzoek bleek dat de methode een beter resultaat oplevert bij langere teksten dan bij kortere. Bij teksten langer dan 150 zinnen wordt een precisie van bijna 1 behaald, terwijl teksten die slechts 20 tot 60 zinnen lang zijn met een precisie van 0,5 worden gealigneerd. Dezelfde methode wordt ook beschreven door Fung en Church (1994), onder de naam K-Vec. Deze naam komt voort uit het feit dat de distributie van woorden afhangt van hun voorkomen in een in K stukken opgedeelde tekst. De distributie van een woord wordt weergegeven door een K-dimensionale vector. Een probleem dat bij beide implementaties speelt zijn woorden met een lage frequentie. De kans dat dergelijke woorden toevallig overeenkomstige distributies vertonen is groot. Dit probleem wordt echter omzeild door dergelijke insignificante data te negeren. Om te voorkomen dat te veel data als insignificant wordt aangemerkt moet het getal K niet te klein zijn. Een te grote K daarentegen zou er voor zorgen dat veel correspondenties worden gemist doordat door toevallige fluctuaties woorden niet dezelfde distributie vertonen.

4.2.4 Patroonherkenning: Melamed (1999) Melamed (1999) beschrijft een methode die patroonherkenning gebruikt om teksten in lineaire tijd en geheugenruimte te aligneren. Deze methode maakt gebruik van verwante woorden. Naast de gebruikelijke gevallen, waarbij woorden op vergelijkbare wijze geschreven worden, spelen bij deze methode ook phonologisch verwante woorden een rol: woorden die in twee talen een vergelijkbare uitspraak hebben, en hetzelfde betekenen. Verder zet het algorithme een lexicon in om vertalingen te kunnen herkennen. Een dergelijk lexicon kan worden gegenereerd met de methode beschreven door Fung en Church (1994). In de te aligneren teksten wordt gezocht naar verwante woorden en woorden die in het lexicon voorkomen. Wanneer op deze gronden aan elkaar verwante woorden in beide teksten worden aangetroffen, dan wordt dit een connectie genoemd. De methode is erop gebaseerd dat deze connecties volgens een bepaald patroon zullen optreden, gesteld dat de teksten inderdaad dezelfde semantische inhoud hebben. Door te zoeken naar een patroon van connecties dat aan bepaalde eisen voldoet, kan de juiste alignering tussen de twee teksten worden vastgesteld. De zoekruimte wordt net als bij veel andere methoden gevormd door de sequenties op de horizontale en verticale assen van een matrix te zetten. Elke positie in deze matrix vormt een potentiële connectie. Het proces bestaat uit twee fases: de connectie generatie fase en de herkenningsfase. In de eerste fase van het proces wordt in een beperkt gedeelte van de totale zoekruimte gezocht naar mogelijke connecties, waarbij een connectie kan bestaan uit twee verwante woorden, of een woordpaar dat in het lexicon wordt teruggevonden. In de tweede fase, de herkenningsfase, probeert het algorithme in de gevonden punten een zogenaamde chain te herkennen, een reeks van connecties die aan bepaalde voorwaarden voldoet. De parameters die een rol spelen bij het vinden van een dergelijke aaneenschakeling van connecties worden verkregen door het algorithme te trainen op een kleine tweetalige tekst. Als geen significante aaneenschakeling wordt gevonden, wordt het gedeelte van de zoekruimte waarin Alignering van Tweetalige Corpora als Vertaalhulp

19

gezocht werd vergroot en wordt het proces herhaald. Dit gaat door totdat een aaneenschakeling is gevonden. Op dat moment wordt een ander gedeelte van het zoekgebied geselecteerd om naar een volgende aaneenschakeling te zoeken. Het eerste zoekgebied dat wordt onderzocht, bevindt zich in het begin van de tweetalige tekst, aangezien het begin van beide teksten een betrouwbare connectie vormt. Volgende zoekgebieden beginnen altijd aan het einde van een gevonden aaneenschakeling. Figuur 7 is een weergave van de totale zoekruimte. De zwarte stippen, true points of correspondence (TPC), geven de connecties weer die in de connectie generatie fase zijn gevonden en die in de herkenningsfase zijn herkend als behorende tot een opeenvolging die aan de gestelde eisen voldoet.

figuur 7: de methode van Melamed (bron: Melamed 1999)

De aanpak is ook wanneer er in één van de twee teksten een gedeelte ontbreekt in staat de juiste alignering te vinden. Aanvankelijk zal in het zoekgebied weliswaar geen significante reeks van connecties worden aangetroffen, maar aangezien dit zoekgebied steeds verder groeit, zal op een gegeven moment de juiste reeks toch worden ontdekt, zoals ook te zien is in figuur 7. De methode steekt qua resultaat goed af tegen andere methoden. Een gedeelte van de Hansards wordt gealigneerd met een foutenpercentage van 1,3. Op hetzelfde tekstfragment heeft een methode van Gale en Church (1991) 3,0 procent fout gekoppeld en de methode van Simard, Foster en Isabelle (1992) 3,8 procent.

4.3 Conclusies De belangrijkste kenmerken van de in de voorafgaande paragrafen besproken methoden zijn samengevat in tabel 8. De foutenpercentages zijn afkomstig uit de beschrijvingen van de verschillende methoden. Deze getallen kunnen in feite nauwelijks met elkaar vergeleken worden, doordat in de meeste onderzoeken met verschillende data en criteria is gewerkt. Gale en Church (1993) geven bijvoorbeeld Alignering van Tweetalige Corpora als Vertaalhulp

20

aan dat hun foutenscore van 4,2%, die werd behaald bij alignering van rapporteringen van Zwitserse banken, gehalveerd worden wanneer als data de Hansards worden gebruikt.

METHODE

GEBRUIKTE GEGEVENS

ALIGNERING

FOUTENSCORE

Gale & Church 1993 Church 1993 Chen 1993 Kay & Röscheisen 1993 Melamed 1999

statistisch lexicaal lexicaal lexicaal lexicaal

alignering correspondentie alignering correspondentie correspondentie

4,2% ? 0,4% 0,7% 1,3%

tabel 8: overzicht van de verschillende methoden

Behalve het resultaat van een alignering, uitgedrukt in een foutenpercentage, kan ook de snelheid van een algorithme van belang zijn. Vooral bij het werken met langere teksten wordt duidelijk dat de lexicale methoden van Chen (1993) en Kay en Röscheisen (1993) zeer traag zijn in vergelijking met de Gale en Church methode. Eerstgenoemde methoden aligneren duizend zinnen in ongeveer 15 minuten. De Gale en Church methode aligneerde een gedeelte van de Hansards met een snelheid van ongeveer 1,3 minuten per duizend zinnen. Naast het reeds gemaakte onderscheid betreffende het gebruik van statistische dan wel lexicale gegevens is er ook een onderscheid te maken op grond van het uiteindelijke resultaat van de alignering. Dit onderscheid wordt in tabel 8 weergegeven in de kolom alignering. Tekstvergelijkingsproblemen zijn namelijk op te delen in aligneringsproblemen en correspondentieproblemen. Aligneringsproblemen staan niet toe dat associaties elkaar overlappen, wat bij correspondentie wel mogelijk is. Correspondentie wordt vaak toegepast op het niveau van karakters, oftewel bytes. In dit geval spelen onderverdelingen in de tekst, zoals zinsgrenzen, geen rol. Alignering en correspondentie worden weergegeven in figuur 9.

correspondentie

alignering

figuur 9: verschillen tussen correspondentie en alignering

Beide benaderingen hebben hun eigen voor- en nadelen. Het grootste nadeel van het aligneren op zinsniveau is dat zinsgrenzen vaak niet makkelijk te herkennen zijn. Chen zowel als Kay en Röscheisen vermelden dan ook dat een aanzienlijk deel van de door hun methoden gemaakte fouten te wijten zijn aan fouten bij de zinsherkenning. Alignering van Tweetalige Corpora als Vertaalhulp

21

De correspondentiemethode toegepast op het niveau van de afzonderlijke karakters ontwijkt deze problemen maar heeft als nadeel dat het resultaat minder bruikbaar kan zijn. Veel toepassingen, waaronder ook het gebruik door menselijke vertalers, hebben behoefte aan een koppeling op zinsniveau.


22

HOOFDSTUK 5

IMPLEMENTATIE VAN DE GALE EN CHURCH METHODE

Voor de implementatie van een aligneermethode, met als doel de alignering van teksten als hulp bij het vertalen, is gekozen voor de methode beschreven door Gale en Church (1993). Deze benadering, waarbij verschillen in zinslengte in het Levenshtein algorithme worden gebruikt om teksten te aligneren, is qua achterliggende gedachte en gebruikt algorithme onder de eenvoudigsten te rangschikken. Dat toch voor deze methode werd gekozen moet worden toegeschreven aan het feit dat de resultaten, mede gelet op de beperkte complexiteit van het algorithme, relatief goed zijn. De alignering wordt uitgevoerd op zinsniveau, wat goed aansluit op de beoogde toepassing. Tevens is de methode sneller dan andere, ingewikkeldere en daardoor ook computationeel zwaardere methoden, die veelal gebruik maken van lexicale informatie. Een laatste voordeel, van meer praktische aard, is dat de methode binnen een beperkte tijdsduur te realiseren valt. Bij de implementatie van deze methode komen overigens problemen en oplossingen naar voren die ook bij andere methoden een rol spelen. In dit opzicht is de Gale en Church methode een goed uitgangspunt te noemen voor eventuele verkenning van andere technieken.

5.1 De verschilfunctie Zoals in de algemene beschrijving van sequentievergelijking al naar voren kwam, is het aligneren van sequenties met gebruik van het Levenshtein algorithme een kwestie van het selecteren van de juiste elementaire operaties. De optimale operatie wordt steeds gekozen door te minimaliseren over de gewichten die worden toegekend aan alle mogelijke operaties op een bepaald moment, opgeteld bij het totale verschil van de bij die operatie horende vorige toestand. Het gewicht van een operatie is gedeeltelijk afhankelijk van het type operatie onder beschouwing, maar meer nog van de elementen waarop de operatie van toepassing is, en dan met name van het verschil tussen deze elementen. Om het verschil tussen elementen te bepalen wordt een verschilfunctie gebruikt. Deze functie drukt het verschil uit als de kans dat de gegeven elementen met elkaar geassocieerd dienen te worden. Aangezien de elementen hier zinnen zijn, gaat het om de kans dat deze twee zinnen vertalingen van elkaar zijn. Van de verkregen kans wordt de negatieve waarde genomen, zodat de verschilwaarde groter wordt wanneer de overeenkomst kleiner wordt: verschil tussen twee zinnen = - Prob (match | δ)


23

In de functie die het verschil tussen twee zinnen bepaalt, wordt gebruik gemaakt van het verschil in lengte tussen de twee zinnen. Dit verschil wordt weergeven als δ. De volgende formule bepaalt hoe groot deze delta is:

δ =

(l 2 − l1c ) l1 s 2

Het idee achter het berekenen van het verschil tussen twee zinnen die ieder in een andere taal zijn geschreven, is dat elk karakter in de eerste taal, L1, tijdens de vertaling een willekeurig aantal karakters zal genereren in de tweede taal. In de functie staat c voor het gemiddelde aantal karakters dat een karakter in L1 genereert in L2, s2 voor de variatie binnen de verdeling van verschillen in lengte en l1 en l2 voor de lengtes van de twee zinnen. Delta is een genormaliseerde weergave van het lengteverschil tussen twee zinnen en zal derhalve gebruikt kunnen worden om te bepalen hoe groot de kans op een bepaald verschil is. Deze kansberekening is alleen mogelijk wanneer de verdeling inderdaad normaal is. Ter controle werd delta berekend voor een set van circa 300 zinnen afkomstig uit het jaarverslag van 1996 van de Europese Ombudsman. De resultaten zijn weergegeven in figuur 10. De grafiek toont een verdeling die bij benadering normaal is, zodat geconcludeerd kan worden dat delta geschikt is voor gebruik in het algorithme. 0,8

0,7

0,6

dichtheid

0,5

0,4

0,3

0,2

0,1

0 -4

-3

-2

-1

0

1

2

3

4

delta

figuur 10: de verdeling van delta is bij benadering normaal

Aanvankelijk werd als verschilfunctie niet de door Gale en Church gebruikte functie aangewend, maar een vereenvoudigde variant. Deze functie maakte gebruik van het absolute verschil in lengte tussen twee zinnen en het daarbij behorende gemiddelde. In experimenten bleek dat deze alternatieve functie niet goed voldeed. De verklaring Alignering van Tweetalige Corpora als Vertaalhulp

24

hiervoor is dat de oorspronkelijke methode het verschil berekent in verhouding tot de lengtes van de betreffende zinnen. Een korte zin zal minder karakters genereren in een andere taal dan een lange zin, met als gevolg dat het absolute verschil ook al snel minder groot zal zijn dan bij de vertaling van een langere zin. De verschilfunctie -Prob(match | δ) wordt via de regel van Bayes omgezet naar - Prob(δ | match) Prob(match) Het eerste gedeelte van deze functie, Prob(δ | match), bepaalt de kans op een verschil delta, gegeven het feit dat er sprake is van een match. Als inderdaad sprake is van een tweetal zinnen die vertalingen van elkaar zijn, dan moet delta een waarde hebben die dicht bij het gemiddelde ligt. Daarom kan Prob(δ | match) als volgt worden herschreven, waarbij een aangetroffen match wordt verondersteld: 2(1 - Prob(|δ|)) De kans op een gegeven delta loopt van nul tot één. De gemiddelde waarde van delta zal voorkomen met een kans van 0,5. De functie 2(1 – Prob(|δ|)) kent aan een dergelijke delta een kanswaarde van 1 toe en aan een delta die voorkomt met extreme kanswaarden van 0 of 1 een kans van 0. Van het getal delta wordt de absolute waarde genomen, zodat ook negatieve verschillen gebruikt kunnen worden. De nu te berekenen standaardnormale kans Prob(|δ|) kan worden opgezocht in een tabel waarin dergelijke kansen zijn opgeslagen. In het computerprogramma wordt gebruik gemaakt van een functie, pNorm, die ook door Gale en Church wordt gebruikt. Het tweede deel van de functie, Prob(match), staat voor de a priori kans op een match van een bepaald type. Hierbij gaat het om de waarschijnlijkheid dat op een willekeurige positie in de alignering een bepaalde elementaire operatie wordt gebruikt. Substitutie zal bijvoorbeeld vaak voorkomen, terwijl operaties als insertie en deletie zeldzaam zijn. Deze kansen moeten worden vastgesteld door eerdere aligneringen te analyseren. Van de nu verkregen functie wordt de logarithme genomen en het resultaat wordt vermenigvuldigd met 100, zodat de complete functie er nu als volgt uit ziet: verschil tussen twee zinnen = -100 LOG 2(1 - Prob(|δ|)) Prob(match)

5.2 Berekening van de parameters De verdeling van de verschillen tussen zinslengtes wordt genormaliseerd om kansberekening te kunnen toepassen. Voor de normalisering zijn om te beginnen twee parameters nodig: het gemiddelde van de verdeling, c, en de variantie, s2. Beide waarden worden bepaald aan de hand van een fragment van het jaarverslag van 1996 van de Ombudsman van het Europees Parlement. Naast deze parameters moeten ook de a priori kansen op de uit te voeren operaties worden bepaald. Hiervoor wordt dezelfde data gebruikt.


25

5.2.1 Het gemiddelde c De gemiddelde verhouding van de lengte van een Engelse zin tot de Nederlandse zin wordt berekend door het aantal karakters in de Engelse tekst te delen door het aantal karakters in de Nederlandse tekst. De uitkomst hiervan is 0,904. Gale en Church bepaalden deze waarde voor de taalparen Engels-Duits en Engels-Frans. Dit leverde respectievelijk 1,1 en 1,06 op. Hier werden de lengtes van de Duitse en Franse teksten gedeeld door die van de Engelse tekst, aangezien Engels in dit geval de brontaal was. In alle drie de gevallen is Engels de taal die gemiddeld de kortste zinnen voortbrengt. Gale en Church gingen er overigens toe over het getal 1 te gebruiken als een taalonafhankelijk gemiddelde. Het effect van deze vereenvoudiging wordt besproken in hoofdstuk 6.

5.2.2 De variantie s2 De variantie binnen de lengteverschillen is afhankelijk van de lengte van de betreffende zinnen. Dit wordt ook in de formule tot uitdrukking gebracht, aangezien de waarde s2 wordt vermenigvuldigd met de lengte l1 van de Nederlandse zin. Gale en Church bepalen de grootte van s2 door de gevonden varianties in een grafiek af te zetten tegen de lengte van de zinnen, en vervolgens de gemiddelde verhouding in deze grafiek af te lezen met behulp van een regressielijn. Dit betekent dat het getal s2 in feite een factor is met behulp waarvan de feitelijke variantie wordt bepaald voor een bronzin met een gegeven lengte. Voor de taalparen Engels-Duits en Engels-Frans werden door Gale en Church respectievelijk de waarden 7,3 en 5,6 vastgesteld. Dezelfde methode levert voor Nederlands-Engels 4,7 op, waarbij als data circa 300 zinnen van het Ombudsman jaarverslag werden gebruikt. De bijbehorende grafiek is te zien als figuur 11.

kwadraten van verschillen met Engelse zinnen

7000

6000

5000

4000

3000

2000

1000

0 0

100

200

300

400

500

600

700

lengtes van Nederlandse zinnen

figuur 11: kwadraten van verschillen met Engelse zinnen afgezet tegen Nederlandse zinnen


26

5.2.3 De a priori kansen De a priori kans op het voorkomen van een bepaalde operatie wordt bepaald aan de hand van een correcte alignering. Hiervoor wordt, met behulp van het aligneerprogramma, een alignering van een gedeelte van het Ombudsman verslag vervaardigd met een omvang van 385 operaties. Een probleem wat zich hierbij voordoet is het ontbreken van deleties in de betreffende alignering. Als dit gegeven als uitgangspunt zou worden gebruikt voor alle volgende aligneringen, dan ontstaat mogelijk een probleem bij het herkennen van deleties. Om dit te voorkomen wordt de kans op een deletie gelijkgesteld aan de kans op een insertie. Gale en Church maken overigens op dit punt evenmin onderscheid tussen insertie en deletie. In het algemeen is het de vraag in hoeverre het gebruik van bepaalde data bij het vaststellen van deze gegevens de werking van het uiteindelijke programma beïnvloedt. Het is natuurlijk de bedoeling dat het programma verschillende soorten teksten kan behandelen, zonder dat parameters moeten worden veranderd. De in tabel 12 afgebeelde waarden sluiten echter aan op de waarden die Gale en Church vonden, wat het idee ondersteunt dat dit goede gemiddelden zijn.

OPERATIE substitutie contractie expansie swap deletie insertie TOTAAL

FREQUENTIE 365 8 10 1 1 (zie toelichting) 1 386

A PRIORI KANS 0,9456 0,0207 0,0259 0,0026 0,0026 0,0026 1,0000

tabel 12: berekening van de a priori kansen op een operatie

5.3 Toepassing van het Levenshtein algorithme Het basale Levenshtein algorithme wordt voor het gebruik in deze methode uitgebreid met drie operaties. Naast insertie, deletie en substitutie wordt nu ook gebruik gemaakt van compressie, expansie en swap. Compressie houdt in dat twee zinnen worden vertaald met één zin en expansie staat voor het tegenovergestelde geval waarbij één zin wordt vertaald met twee zinnen. In principe is het mogelijk dat een enkele zin met meer dan twee zinnen wordt vertaald, of dat een grotere hoeveelheid dan twee zinnen wordt samengevat in één zin, maar dit komt in de praktijk zelden voor. Implementatie van deze mogelijkheden zou de methode trager maken, met slechts een verwaarloosbaar klein rendement in de vorm van daadwerkelijk succesvol gebruik van de extra operaties. De derde operatie die aan de implementatie van het Levenshtein algorithme wordt toegevoegd is de swap. Hierbij worden twee zinnen vertaald in twee andere zinnen. Dat deze operatie niet hetzelfde is als twee opeenvolgende toepassingen van de substitutie ligt besloten in het gegeven dat de semantische inhoud van de twee zinnen uit de brontekst in een andere samenstelling terugkeert in de twee zinnen die de vertaling vormen. Dit is bijvoorbeeld het geval wanneer het einde van de eerste zin het begin van de tweede zin vormt in de vertaling. Dit gebruik van de swap wordt ook wel merge genoemd. Figuur 13 geeft een Alignering van Tweetalige Corpora als Vertaalhulp

27

compleet overzicht van de in de methode gebruikte operaties, die tevens in de hieronder weergegeven definitie van de minimaliserende functie voorkomen. Deze minimalisatie werd reeds besproken in de beschrijving van het Levenshtein algorithme en is hier uitgebreid met de drie genoemde operaties. De pijlen in figuur 13 stellen de pointers voor die uiteindelijk zullen worden gebruikt om de alignering te achterhalen.

i

j

d(ai, bj-1) + w(0, bj)

(insertie van bj)

d(ai-1, bj) + w(ai, 0)

(deletie van ai)

d(ai-1, bj-1) + w(ai, bj)

(substitutie van ai door bj)

d(ai-2, bj-1) + w(ai + ai-1, bj)

(contractie van ai en ai-1 in bj)

d(ai-1, bj-2) + w(ai, bj + bj-1)

(expansie van ai in bj en bj-1)

d(a , b ) = min

d(ai-2, bj-2) + w(ai + ai-1, bj + bj-1) (merging van ai en ai-1 in bj en bj-1)

deletie substitutie contractie insertie swap expansie

figuur 13: de zes elemenaire operaties schematisch weergegeven

5.4 Optimalisatie van het algorithme Kruskal (1983) beschrijft een manier om het Levenshtein algorithme te optimaliseren. Deze methode, die in twee varianten kan worden geïmplementeerd, is er op gericht de omvang van de zoekruimte te verkleinen. Aangezien de juiste alignering in het gemiddelde geval dicht bij de diagonaal van het zoekquadrant moet worden gezocht, ligt het voor de hand om de hoeken van de quadrant die niet door deze diagonaal worden doorkruist uit te sluiten van het zoekproces. De eerste manier om dit te bewerkstelligen is het aangeven van een maximale afstand vanaf de diagonaal Alignering van Tweetalige Corpora als Vertaalhulp

28

waarbinnen nog gezocht mag worden. Deze aanpak is afgebeeld in figuur 14. De tweede manier, die wordt weergegeven in figuur 15, beperkt het toegestane aantal opeenvolgende inserties en deleties. Het is uiteraard van belang de zoekruimte niet te sterk te verkleinen, aangezien dan de kans toeneemt dat de juiste alignering onbereikbaar wordt gemaakt. De eerste methode is hiervoor gevoeliger dan de tweede, zoals uit de vorm van de zoekruimtes kan worden afgeleid. Deze optimalisaties hebben uitsluitend betrekking op de snelheid van het algorithme en niet op het gebruik van geheugenruimte. Er wordt nog steeds een matrix gereserveerd, maar deze wordt niet meer geheel doorzocht. Het gedeelte dat doorzocht wordt beslaat bij een bereik van b zinnen circa n(2b+1) subproblemen, terwijl zonder de optimalisatie nm problemen door het algorithme worden behandeld.

figuur 14

figuur 15

figuren 14 en 15: weergave van zoekruimte bij optimalisatie (bron: Kruskal 1983)

De tweede variant lijkt aanvankelijk de beste te zijn, aangezien de vorm van de verkleinde zoekruimte doet vermoeden dat bij deze variant de kans op het uitsluiten van de correcte alignering kleiner is. Wanneer echter de eerste variant wordt gebruikt met een maximale afstand tot de diagonaal die in verhouding staat tot de omvang van de te aligneren teksten, dan is ook hier de kans dat de alignering niet gevonden kan worden klein. Een praktisch voordeel van de eerste methode boven de tweede is bovendien het verschil in het aantal benodigde berekeningen. Beide methoden beperken het zoekproces tot een afgebakend gebied, maar de eerste variant heeft hiervoor slechts een eenvoudige vergelijking nodig, terwijl de tweede variant een complexe berekening gebruikt. Het eenvoudige criterium van de eerste methode zou eventueel kunnen worden verfijnd door per positie binnen de tekst een andere maximale afstand tot de diagonaal te bepalen. Door deze afstand te laten toenemen naarmate het midden van de tekst wordt bereikt, en daarna weer te laten afnemen, wordt een zoekgebied verkregen welke dat van de tweede methode benadert. Aangezien dit per vergelijking extra computaties met zich meebrengt, zal een afweging moeten worden gemaakt aan de hand van een eventuele verbetering in het resultaat en de extra berekeningstijd die hiervoor nodig is. In hoofdstuk 6 zal worden besproken in hoeverre de geïmplementeerde optimalisatie resultaat oplevert in de vorm van tijdwinst. Hierbij kan ook een vergelijking worden getrokken met de originele implementatie van Gale en Church, waarin geen optimalisatie werd verwerkt. Alignering van Tweetalige Corpora als Vertaalhulp

29

5.5 Het opsplitsen van de tekst in kleinere delen Naast de optimalisering van het algorithme zoals beschreven in de vorige paragraaf, kan er op een relatief eenvoudige en voor de hand liggende wijze voor worden gezorgd dat het aligneringsproces aanzienlijk minder tijd in beslag neemt. Het gaat hier om het opsplitsen van de te aligneren teksten in kleinere delen. Elk deel wordt slechts vergeleken met het corresponderende deel in de andere tekst. Aangezien op deze manier een groot aantal mogelijke koppelingen wordt uitgesloten, wordt een grote tijdwinst behaald. deel 1

deel 2

deel 1 deel 2 figuur 16: gebruik van zoekruimte na opsplitsing van teksten in delen

Figuur 16 toont de zoekruimte zoals die door het algorithme wordt gebruikt wanneer de te aligneren teksten zijn opgesplitst in delen. Alleen de gearceerde gebieden binnen de zoekruimte worden bezocht. In de praktijk wordt de alignering van de afzonderlijke delen in een zoekruimte uitgevoerd die qua dimensies overeenkomt met de lengtes van de betreffende tekstfragmenten, zodat niet alleen tijdwinst wordt behaald, maar ook een efficiënter gebruik van het geheugen van de computer. De indeling die wordt aangebracht kan uiteraard niet willekeurig zijn. Om te voorkomen dat de juiste alignering onmogelijk wordt gemaakt, moeten bestaande indelingen in de tekst gebruikt worden, zoals die in hoofdstukken of paragrafen, waarvan aangenomen kan worden dat ze in beide teksten identiek zijn. Verder is het natuurlijk mogelijk om op andere posities in de teksten kunstmatige grenzen aan te brengen, wanneer eerst is vastgesteld dat dit voor de alignering geen problemen zal opleveren. Een probleem ontstaat wanneer de aangebrachte grens een associatie onmogelijk maakt die op grond van de inhoud van de betreffende zinnen wel had moeten worden herkend. In plaats van het met de hand aanbrengen van grenzen tussen hoofdstukken, zou dit ook automatisch kunnen gebeuren, zoals in de methode van Gale en Church het geval is. Zij geven hierbij aan dat het automatisch herkennen van paragraafgrenzen goed verloopt voor een gegeven tekst, aangezien de paragrafen in deze tekst voorzien zijn van duidelijke markeringen. Ondanks deze markeringen treden toch problemen op met titels en andere korte tekstfragmenten, die worden aangezien voor paragrafen. Hierdoor is het nodig het resultaat met de hand te controleren. Aangezien gebruikte markeringen per tekst kunnen verschillen en er zelfs bij duidelijke markering nog problemen kunnen ontstaan, is er bij deze implementatie voor gekozen om het Alignering van Tweetalige Corpora als Vertaalhulp

30

aanbrengen van een indeling in de teksten aan de gebruiker over te laten. Dit brengt vooral bij langere teksten het nadeel met zich mee dat het aanbrengen van grenzen relatief veel tijd kan kosten binnen een verder automatisch verlopend proces. Dit nadeel bestaat echter eveneens wanneer op dit punt wordt gekozen voor automatisering, aangezien de resultaten met de hand gecontroleerd en eventueel verbeterd zullen moeten worden.

5.6 Het herkennen van zinsgrenzen Zoals beschreven in hoofdstuk 4 behoort de Gale en Church methode tot een groep van methoden die aligneren op zinsniveau, in tegenstelling tot methoden die werken op het niveau van de afzonderlijke karakters. Dit betekent dat het algorithme de beschikking moet hebben over een verzameling zinnen waarbinnen vergelijkingen kunnen worden uitgevoerd. De meeste teksten zullen niet door middel van harde returns of speciale markeringen in zinnen zijn ingedeeld, zodat het opdelen onderdeel moet zijn van de implementatie van de gebruikte methode. Een zin kan op twee manieren worden herkend, te weten aan zijn syntactische delen en aan zijn leestekens. Het op syntactische gronden herkennen van een zin vereist een gecompliceerde parser met toegang tot een zeer uitgebreid woordenboek. Het analyseren van de zinsstructuur zou, vooral in verhouding tot de eigenlijke alignering, zeer veel tijd in beslag nemen. De meer oppervlakkige benadering daarentegen waarbij leestekens worden gebruikt werkt over het algemeen zeer snel. In plaats van een grammatica en een woordenboek maakt deze techniek gebruik van een relatief kleine set regels waarmee het concept 'zin' aan de hand van uiterlijke kenmerken wordt omschreven. Om een tekst op deze wijze op te splitsen worden de leestekens sequentieel ingelezen, waarbij op elke positie moet worden overwogen of het desbetreffende teken, in combinatie met voorafgaande en komende tekens, het einde van een zin aangeeft of niet. Hierbij is niet alleen kennis van mogelijke zinseindes vereist, maar ook van de manieren waarop een zin kan beginnen. De implementatie gebruikt de volgende aannames om zinsgrenzen te herkennen: 1: een zin eindigt met één van deze tekens: [.?!'")] 2: tussen twee zinnen zit altijd een spatie, enter of tab (white-space) 3: een zin begint niet met een kleine letter 4: de laatste letter in een zin is geen hoofdletter Gebruik makend van deze regels werd in twee teksten gezocht naar zinnen. De eerste tekst is de Nederlandse vertaling van het verhaal August Heat van W. F. Harvey. Dit verhaal telt 134 zinnen en hiervan werd 96,3% correct herkend. Een typische fout die door het programma werd gemaakt werd veroorzaakt door een afkorting. Hierdoor werd de volgende zin onterecht in twee zinnen opgesplitst: Ik werd zodanig door mijn werk in beslag genomen dat ik mijn middagmaal onaangeroerd liet, en pas met werken ophield toen de klok van St. Jude vier sloeg.


31

1) Ik werd zodanig door mijn werk in beslag genomen dat ik mijn middagmaal onaangeroerd liet, en pas met werken ophield toen de klok van St. 2) Jude vier sloeg.

Een dergelijke fout zou voorkomen kunnen worden door een lijst van afkortingen te gebruiken. Ook dan is een vergissing echter nog mogelijk, aangezien een afkorting daadwerkelijk aan het einde van een zin zou kunnen staan. Een fout van een andere aard is die waarbij losstaande tekstelementen, zoals opsommingen van namen of titels van hoofdstukken, aan een zin worden gekoppeld. Deze elementen zijn in het algemeen geen zinnen, maar aangezien ze niet bij een voorafgaande of volgende zin horen zouden ze door het programma wel zo behandeld mogen worden. De tweede tekst die aan dit proces werd onderworpen is een fragment van een jaarverslag van de Ombudsman van het Europees Parlement. Deze tekst werd gekozen als tegenhanger van de literaire tekst om te onderzoeken of ook bij een dergelijk document een hoog percentage van zinsherkenning kan worden bereikt. Dat blijkt niet het geval te zijn, aangezien nu slechts 78,8% van 148 zinnen goed wordt onderscheiden. Het grootste gedeelte van de fouten bestaat uit het niet herkennen van titels en opsommingen, zoals bij het vorige resultaat al werd vermeld. In dit geval zorgde dit voor een groot aantal fouten omdat de tekst veel kopjes en lijsten bevatte.


32

HOOFDSTUK 6

RESULTATEN

Bij het bepalen van het resultaat van een aligneringsmethode wordt gekeken naar het aantal operaties dat niet werd herkend, terwijl dit wel had moeten gebeuren. In dit geval werd dit bereikt door de alignering die door het programma werd afgeleverd met de hand te controleren. Hierbij werd bij elke operatie de vraag gesteld of deze correct was, en zo niet, voor welke operatie had moeten worden gekozen. In het geval van een fout werd ook gecontroleerd of de fout werd veroorzaakt door een onjuiste zinsherkenning.

6.1 Aligneringsresultaten De eerste test werd uitgevoerd op het jaarverslag van 1999 van de Europese Centrale Bank. De Nederlandse variant hiervan telt 1146 zinnen en de Engelse tekst is 1133 zinnen lang. In de tekst kwamen afbeeldingen voor, maar aangezien het oorspronkelijke bestand van het type PDF was en voor gebruik door het programma tekstbestanden worden vereist, gingen deze verloren. Hoewel de tekst bestaat uit verschillende hoofdstukken is deze indeling niet in het tekstbestand aangebracht. Dit zou het resultaat verbeteren, zoals werd beschreven in paragraaf 5.5, maar omdat het resultaat vooral zinvol is wanneer sprake is van een zoveel mogelijk automatisch verlopend proces werd dit achterwege gelaten. De optimalisatie werd daarentegen dan ook wel gebruikt, waarbij het bereik werd ingesteld op 25 zinnen voorafgaand en volgend op de zin in de vertaling die in verhouding op dezelfde positie staat als de zin in de brontekst. Deze optimalisatie zorgt in principe niet voor een beter, maar wel voor een sneller resultaat, wat in paragraaf 6.4 zal worden toegelicht. In de tabel 17 wordt weergegeven hoeveel fouten per categorie werden gemaakt. Het percentage van fouten die door zinsherkenning werden veroorzaakt, is een percentage van het totale aantal fouten binnen de betreffende categorie.

totaal sub 1177 con 18 exp 1 swap 1 ins 0 del 0 TOTAAL 1197

fout 260 3 0 1 0 0 264

% fout 22,1 16,7 0 100 0 0 22,1

fout zinsh. 203 2 0 1 0 0 206

% fout zinsh. 78,1 66,7 0 100 0 0 78

tabel 17: resultaten bij alignering van de ECB tekst


33

De correcte alignering bevatte, zoals in de tweede kolom van de tabel te zien is, vooral veel substituties. Hiervan werd 22,1% niet herkend, wat wil zeggen dat in plaats van een substitutie werd gekozen voor een andere operatie. Het percentage fouten gemeten over de complete alignering is eveneens 22,1%. In de laatste kolom is te zien dat 78% van deze fouten werd veroorzaakt door een fout bij het bepalen van de zinsgrenzen. Hieruit komt duidelijk naar voren dat dit deel van de methode het zwakst is. Zouden de zinnen goed zijn herkend, of zou de invoer aanvankelijk reeds uit gescheiden zinnen hebben bestaan, dan zou het resultaat van de alignering vele malen beter zijn geweest. Uit de tabel is te berekenen dat in dat geval het totale aantal fouten zou worden teruggebracht tot 58, wat neerkomt op een foutenpercentage van 4,8%. Hierbij moet worden opgemerkt dat, hoewel het percentage fouten hoog is, de bijbehorende alignering minder slecht is dan dit percentage doet vermoeden. In veel gevallen waarbij werd gekozen voor een andere operatie dan de juiste, resulteerde dit toch in een associatie tussen bij elkaar horende zinnen. Dit werd veroorzaakt door de vele kopjes en hoofdstuktitels die in de tekst voorkwamen. In principe zouden deze als aparte zinnen moeten worden behandeld. Het zinsherkenningsalgorithme koppelde deze tekstdelen echter altijd aan de erop volgende zin, aangezien kopjes nooit eindigen met een punt. Als vervolgens de op deze manier samengestelde zin wordt gekoppeld aan de op overeenkomstige wijze samengestelde zin in de andere tekst, dan levert dit twee fouten op aangezien twee substituties worden gemist. De resulterende alignering klopt echter wel, in zoverre dat geen zinnen met elkaar geassocieerd zijn die niet dezelfde semantische inhoud hebben. Figuur 18 toont twee van dergelijke gevallen. De eerste operatie, een substitutie, koppelt in feite vier zinnen aan elkaar in plaats van twee. Het tweede geval, een expansie, koppelt twee zinnen aan elkaar waarvan er één eerder in twee zinnen is opgedeeld. Deze zinsherkenningsfout bestaat eruit dat de punt van een afkorting wordt aangezien voor de punt die de zin afsluit, in combinatie met het erop volgende cijfer dat wordt aangezien als het begin van de tweede zin. Werkgelegenheidsgroei houdt aan in 1999 Volgens nationale gegevens is de werkgele-genheid in 1999 ongeveer evenveel gegroeid als in 1998, namelijk met 1,4%. ---<substitutie>--Employment growth sustained in 1999 According to national data, in 1999 employment in the euro area is estimated to have increased at broadly the same rate as in 1998, i.e. at 1.4%. Aan het einde van het jaar bedroeg de werkloosheidsgraad 9,6%, dat is 0,9 procentpunt minder dan in december 1998. ---<expansie>--At the end of the year the rate of unemployment stood at 9.6%, i.e. 0.9 percentage point lower than in December 1998. figuur 18: twee voorbeelden van strikt genomen foutieve associaties met een goed resultaat

Aangezien de alignering zal worden gebruikt door vertalers, kunnen de bovenstaande voorbeelden ook goed worden gerekend. Dit kan gebeuren door bij het controleren van de alignering alleen een fout te tellen wanneer de aangebrachte associatie er één is tussen tekstdelen die niet elkaars vertaling zijn. Dit type fouten vormt 27,5% van het totale aantal fouten, zodat het nieuwe foutenpercentage uitkomt op 6,1%. Alignering van Tweetalige Corpora als Vertaalhulp

34

6.2 Vergelijking met oorspronkelijke implementatie Gale en Church vermelden dat hun implementatie een foutenscore van 4,2% behaalt bij alignering van verslagen van de Union Bank of Switzerland (UBS). De data bestond uit Engelse, Duitse en Franse teksten van ieder ongeveer 725 zinnen. Bij het vaststellen van dit percentage werd een fout geconstateerd wanneer het programma een door een menselijke vertaler herkende associatie niet aanbracht. Er was sprake van een associatie als beide zinnen minstens een zinsdeel met elkaar gemeen hadden. Deze benadering van de foutenscore sluit meer aan bij de alternatieve controle die in dit onderzoek werd gebruikt dan bij de eerder gebruikte strikte controle. Er wordt immers niet gekeken naar de aard van de associatie, maar meer naar het effect hiervan. Met respectievelijke foutenscores van 6,1 en 4,2 procent lijken de in dit onderzoek beschreven implementatie en de versie van Gale en Church qua resultaat niet veel van elkaar te verschillen. Hierbij moet worden opgemerkt dat een dergelijke vergelijking moeilijk is, aangezien in beide gevallen verschillende data is gebruikt. Wellicht is een bepaalde tekst door de afwezigheid van typische probleemgevallen als kopjes en paragraaftitels, alsmede zich vaak herhalende afkortingen, eenvoudiger te aligneren dan een andere tekst. Verder doen Gale en Church geen uitspraken over de resultaten van de zinsherkenningsmethode en evenmin over het effect van deze resultaten op de uiteindelijke foutenscore. Het is waarschijnlijk dat een deel van de fouten door foutieve zinsherkenning werd veroorzaakt, maar aangezien hierover geen uitspraken worden gedaan is het moeilijk om de implementaties op dit punt te vergelijken. Deze gegevens horen wel in een weergave van de resultaten thuis, aangezien de zinsherkenning een essentieel onderdeel van de methode vormt. Een derde punt waarop de onderzoeken van elkaar verschillen is het feit dat Gale en Church de door hun programma te aligneren tekst in paragrafen opsplitsten. Weliswaar gebeurde dit gedeeltelijk automatisch, maar de resultaten hiervan moesten met de hand worden gecontroleerd en eventueel verbeterd. Het aanbrengen van een grens, ook wel anchor point genoemd, zorgt ervoor dat een aantal associaties reeds vaststaat. Dit betekent dat de hoeveelheid aangebrachte grenzen de resultaten van de alignering evenredig positief beïnvloedt. Het is aan de onderzoekers om te bepalen in hoeverre de complete alignering op deze manier al wordt vastgelegd, nog voordat het programma is begonnen.

6.3 Vergelijking met andere methoden In hoofdstuk 4 werd reeds een vergelijking gemaakt tussen verschillende aligneermethoden, waaronder ook de methode van Gale en Church. De belangrijkste kenmerken van de Gale en Church methode zijn uiteraard ook aanwezig bij de hier besproken implementatie. Dit houdt in dat de techniek in snelheid de andere benaderingen overtreft, maar niet in kwaliteit van de alignering. Hier moet echter opnieuw worden opgemerkt dat vergelijking op grond van uitsluitend de in de verschillende onderzoeken gevonden foutenscores niet eenvoudig is. In (Brown et al. 1990) waarin een methode wordt beschreven die eveneens gebruikt maakt van zinslengte, wordt melding gemaakt van een foutenscore van 0,6%. Gale en Church Alignering van Tweetalige Corpora als Vertaalhulp

35

relativeren het verschil met hun foutenscore van 4,2% door te wijzen op het gebruik van verschillende corpora en verschillende testmethoden in beide onderzoeken.

6.4 Computationele efficiëntie

verwerkingstijd in seconden

verwerkingstijd in seconden

Zoals beschreven in hoofdstuk 5 wordt de quadratische verwerkingstijd van het Levenshtein algorithme door toepassing van de optimalisatie van Kruskal (1983) teruggebracht tot een lineaire verwerkingstijd. Deze verandering zorgt ervoor dat het algorithme uitermate snel werkt. Voor het aligneren van 1000 zinnen is slechts 4,2 seconden nodig. Tevens is hierdoor het opsplitsen van een grote tekst in kleinere delen, wat een moeilijk te automatiseren proces is, minder belangrijk geworden. In figuur 19 en 20 is duidelijk te zien hoe de verwerkingstijd voor een tekst van toenemende omvang door de optimalisatie wordt beïnvloed. 140 120 100 80 60 40 20 0 0

200

400

600

800

1000

1200

aantal zinnen in elke tekst

figuur 19: zonder optimalisatie

4,5 4 3,5 3 2,5 2 1,5 1 0,5 0 0

200

400

600

800

1000

aantal zinnen in elke tekst

figuur 20: met optimalisatie

figuur 19 en 20: het effect van de optimalisatie op de verwerkingstijd gemeten bij een toenemende lengte van de te aligneren teksten

Gale en Church vermelden dat hun programma 890.000 zinnen aligneert in een tijd van ongeveer 10 uur. Het is niet eenvoudig om hier de benodigde tijd voor bijvoorbeeld 1000 zinnen uit af te leiden, aangezien het standaard algorithme een quadratisch toenemende verwerkingstijd kent. Dit wordt mede bemoeilijkt door het feit dat de tekst is opgedeeld in paragrafen, waarbinnen wordt gealigneerd. Het aantal paragrafen wordt niet vermeld. Om toch een vergelijking te kunnen maken wordt de verwerkingstijd van mijn implementatie geschat voor een tekst van dergelijke lengte. Dit is mogelijk aangezien de optimalisatie ervoor zorgt dat de benodigde tijd lineair toeneemt in plaats van quadratisch. Uitgaande van het vastgestelde testresultaat van 1000 zinnen in 4,2 seconden, wordt de verwerkingstijd voor 890.000 zinnen geschat op 62,3 minuten. Dit getal zal in de praktijk groter uitvallen, aangezien voor een tekst van dergelijke lengte het bereik waarmee binnen de optimalisatie wordt gewerkt aanzienlijk groter moet zijn dan het geval was bij het verkrijgen van het testresultaat, omdat rekening moet worden gehouden met grotere variaties. Overigens moet hierbij vermeld worden dat Gale en Church een Sun 4 gebruikten om hun methode te testen, terwijl de hier beschreven implementatie werkte op een P-120 personal computer. Zoals al is beschreven in paragraaf 4.3 steekt de snelheid van de Gale en Church methode, en ook van deze implementatie, zeer gunstig af tegen de snelheid van lexicale methoden. Alignering van Tweetalige Corpora als Vertaalhulp

36

1200

6.5 Voorkomende problemen 6.5.1 Zinsherkenning Problemen bij het herkennen van zinsgrenzen zorgen voor 78% van de aligneerfouten. Ondanks dat de regels die voor het herkennen van zinnen gebruikt worden beperkt te noemen zijn, geeft dit aan dat dit het zwakste punt van de methode is. Het herkennen van hoofdstuk- en paragraaftitels is namelijk nooit eenvoudig, en vaak onmogelijk. Herkenningsfouten die in de gebruikte teksten ontstonden door afkortingen, kunnen voorkomen worden door de methode uit te rusten met een lijst van afkortingen. Wat echter opviel aan het Jaarverslag van de Europese Bank was het grote aantal niet-alledaagse afkortingen. In het algemeen kan men bij technische teksten en teksten afkomstig van instellingen als banken veel termen verwachten die in de gemiddelde tekst weinig of nooit voorkomen. Om ook op deze gevallen te kunnen inspelen moet de lijst worden aangepast voor elke tekst die wordt gealigneerd, wat in de praktijk natuurlijk uiterst omslachtig is. Een meer flexibele benadering bestaat uit het herkennen van afkortingen in het algemeen, te weten aan hun gemeenschappelijke uiterlijke kenmerken. Hoewel er altijd situaties zullen blijven voorkomen waarin niet met volledige zekerheid een beslissing kan worden genomen, zal de gemiddelde score door toepassing van dergelijke technieken waarschijnlijk omhoog gaan.

6.5.2 Geheugengebruik De optimalisatie zoals die nu wordt toegepast, zorgt weliswaar voor een grotere snelheid, maar niet voor een kleiner geheugengebruik. Hierdoor is het algorithme op dit punt afhankelijk van de hardware waarop het programma wordt gebruikt. Teksten met een lengte van bijvoorbeeld 10.000 zinnen of meer kunnen problemen opleveren aangezien een matrix van honderd miljoen posities wordt gedeclareerd. Om dit te voorkomen is een andere benadering van het geheugengebruik nodig, zodat niet de complete zoekruimte wordt aangemaakt, maar slechts het gedeelte rond de diagonaal dat door toepassing van de optimalisatie zal worden bezocht.


37

m

n

b n b figuur 21: alternatieve benadering van zoekruimte voor efficiënter geheugengebruik

Deze verandering is schematisch afgebeeld als figuur 21. De rechterkant van de afbeelding toont de zoekruimte zoals die na de verandering zou zijn. De zoekruimte rond de diagonaal is geïsoleerd van de voormalige complete zoekruimte. Hier is duidelijk te zien dat nu nog slechts een gebied van het geheugen wordt gebruikt met een grootte van nb, waarbij n het aantal zinnen in de brontekst is, en b het aantal zinnen in de vertaling dat steeds met een zin uit de brontekst zal worden vergeleken.

6.6 Variaties binnen de methode 6.6.1 Aantal woorden als lengtemaat Een variatie binnen het algorithme die door Gale en Church werd toegepast bestond eruit de lengte van een zin uit te drukken in het aantal woorden in plaats van het aantal karakters. Hier wordt deze variant ook getest, nu met het verschil dat de teksten in het Nederlands en het Engels geschreven zijn. De verwachting is dat het resultaat hetzelfde zal zijn als in het onderzoek van Gale en Church, namelijk een verslechtering ten opzichte van de standaard benadering. De variantie s2 en het gemiddelde c werden opnieuw bepaald, uitgaande van het aantal woorden als lengtemaat. Hiervoor werden respectievelijk de waarden 0,65 en 0,96 gevonden. Bij alignering van het verhaal August Heat van W.F. Harvey werd vervolgens slechts ongeveer 10% van het totale aantal aligneringsoperaties goed uitgevoerd. Deze lage score werd veroorzaakt doordat een fout die vroeg in de alignering werd gemaakt niet door de erop volgende operaties werd hersteld, zoals in het normale geval vaak wel gebeurt. Aangezien dezelfde alignering bij gebruik van het aantal karakters als lengtemaat geheel foutloos wordt uitgevoerd, blijkt hieruit dat het aantal woorden inderdaad een minder geschikte lengtemaat is. Gale en Church geven aan dat karakters in dit opzicht betrouwbaarder zijn omdat ze in grotere aantallen voorkomen. Alignering van Tweetalige Corpora als Vertaalhulp

38

6.6.2 Taalonafhankelijk gemiddelde Voor het verkrijgen van de resultaten die in dit onderzoek zijn vermeld, werd gewerkt met een gemiddelde c van 0,904. Dit gemiddelde geeft weer hoeveel letters door één letter worden geproduceerd bij een vertaling van de brontaal naar de doeltaal. Gale en Church besloten om als gemiddelde 1 te gebruiken. De waarden die zij vonden voor Engels-Duits en Engels-Frans weken beiden niet veel van dit getal af, zodat het kon dienen als een taalonafhankelijk gemiddelde. Verder maakt het gebruik van dit gemiddelde het programma eenvoudiger en sneller. Toepassing van het gemiddelde 1 bij Nederlands-Engels in de hier beschreven implementatie resulteert in een foutenscore van 0% bij het aligneren van August Heat, dezelfde score als bij gebruik van het gemiddelde 0,904. Dit wijst erop dat deze variatie qua aligneringsresultaat toepasbaar is. De tijdwinst die men zou verwachten treedt echter niet op. Dit heeft waarschijnlijk met specifieke kenmerken van de implementatie te maken, aangezien in principe minder tijd nodig is doordat een vermenigvuldiging minder wordt gebruikt. Desondanks kan men concluderen dat deze variatie de methode minder taalafhankelijk maakt, zonder dat het resultaat achteruit gaat. Om de vertaalrichting om te draaien, en een Engelse tekst te aligneren met een Nederlandse vertaling, zouden overigens nieuwe waarden moeten worden vastgesteld voor de a priori kansen op het gebruik van de aligneeroperaties. Wanneer men er van uit gaat dat de operaties simpelweg in beide richtingen gelden, zodat de kans op een expansie in een gegeven vertaalrichting gelijk is aan de kans op een contractie in de tegenovergestelde vertaalrichting, dan zijn de nieuwe waarden uiteraard eenvoudig af te leiden uit de bestaande gegevens.


39

HOOFDSTUK 7

PRESENTATIE VAN DE ALIGNERING

De alignering moet voor het gebruik als vertaalhulp op een juiste manier gepresenteerd worden. Dit kan op verschillende manieren gebeuren, afhankelijk van het preciese gebruik van de alignering.

7.1 Gebruikte operaties In bepaalde omstandigheden zou interesse kunnen bestaan voor de aard van de binnen een alignering toegepaste operaties. Dit is bijvoorbeeld het geval wanneer moet worden vastgesteld in welke mate bepaalde operaties worden gebruikt, zoals ook voor dit onderzoek nodig was. Verder kan informatie over de operaties de alignering verduidelijken, doordat het aantal elementen dat meedoet aan een associatie meteen duidelijk is. De bij dit onderzoek behorende implementatie geeft per associatie de gekozen operatie weer. Hierbij worden de verschillende zinnen onder elkaar geplaatst, gescheiden door een term die de operatie weergeeft. Er zou ook kunnen worden gekozen voor een meer grafische weergave, waarbij de zinnen in kolommen naast elkaar staan en in de tussenliggende ruimte door middel van pijlen wordt aangegeven welke zinnen met elkaar in verband zijn gebracht. Het voordeel van deze benadering is dat de afzonderlijke teksten makkelijker te lezen zijn.

7.2 Concordantie Een tweetalige concordantie kan gefabriceerd worden op basis van een alignering. Hierbij geldt dat het resultaat van een geautomatiseerd proces, de alignering, als invoer wordt gebruikt voor een volgend automatisch verlopend proces, namelijk het maken van de concordantie. Hierin verschilt deze toepassing van de andere toepassingen die in dit hoofdstuk worden gegeven. Een mogelijke opmaak van de alignering zou zijn om elk deel van een gemaakte associatie op één regel te plaatsen en de verschillende associaties van elkaar te scheiden met behulp van een lege regel. Overigens kunnen de te aligneren teksten en de bijbehorende alignering ook van elkaar gescheiden worden, door de alignering weer te geven aan de hand van de posities van de betreffende zinnen in beide teksten.


40

7.3 Controle bij vertaling Een vertaler kan een alignering gebruiken als referentie of controle bij zijn of haar eigen vertaling. Hiervoor moet de alignering eenvoudigweg op een leesbare manier worden gepresenteerd. Dit kan worden bereikt, zoals ook in paragraaf 7.1 werd beschreven, door de teksten naast elkaar te plaatsen. Verder kan deze toepassing natuurlijk worden uitgewerkt aan de hand van computersoftware die de alignering op verschillende manieren aan de gebruiker toont. Zo zou bijvoorbeeld gekozen kunnen worden voor een tekst waarin zogenaamde hyperlinks, verwijzingen naar elementen in het huidige of een ander document, zijn aangebracht. Door op deze manier de bij elkaar horende zinnen of groepen van zinnen in twee richtingen met elkaar te verbinden, kan heen en weer worden bewogen tussen de vertalingen, terwijl de afzonderlijke teksten steeds goed leesbaar zijn.


41

HOOFDSTUK 8

CONCLUSIE

De in dit onderzoeksverslag gepresenteerde implementatie van de aligneermethode van Gale en Church (1993) is in staat een tweetalige tekst met grote snelheid te aligneren op zinsniveau. Specifieke problemen bij gebruik van het taalpaar Nederlands-Engels werden niet geconstateerd. De kwaliteit van de alignering komt bij benadering overeen met de resultaten die door Gale en Church werden behaald. Tijdens een test met een jaarverslag van de Europese Centrale Bank van circa 1150 zinnen werden, mede door toedoen van fouten in de zinsherkenningsfase, weliswaar niet steeds de juiste aligneeroperaties geselecteerd, maar slechts een beperkt deel van de gemaakte fouten zorgde voor foutieve associaties tussen zinnen. Op deze manier gemeten bedroeg het foutenpercentage 6,1%, terwijl Gale en Church melding maken van een foutenpercentage van 4,2%. De gekozen benadering bij het vaststellen van het aantal fouten is vooral correct aangezien bij de voorziene toepassing, te weten gebruik door vertalers, niet de gekozen operaties een rol spelen, maar enkel het resultaat van deze operaties. De toegepaste optimalisatie, beschreven door Kruskal (1983), zorgt ervoor dat het Levenshtein algorithme, waar de methode gebruik van maakt, geen quadratische maar een lineaire verwerkingstijd kent. Een tekst van 1000 zinnen werd in slechts 4,2 seconden gealigneerd op een Pentium 120 PC. Het geheugengebruik wordt door de optimalisatie niet beperkt, maar op relatief eenvoudige wijze zou hier alsnog voor kunnen worden gezorgd, zoals is beschreven in paragraaf 6.5.2. Met de vermelde resultaten steekt de implementatie goed af tegen lexicale methoden, zoals die in hoofdstuk 4 werden beschreven. Hoewel verscheidene technieken kleinere foutenscores behalen, gaat dit ook gepaard met een lage aligneersnelheid. Verder werd de hier vermelde score gemeten bij alignering van een tekst die veel afkortingen bevatte, wat tot gevolg had dat de zinsherkenning te wensen overliet. Verbetering op dit punt zou de implementatie als geheel sterk verbeteren, aangezien nu gebruik wordt gemaakt van een naïef te noemen oplossing. De variatie waarbij het aantal woorden werd gebruikt als lengte van de te aligneren zinnen, in plaats van het aantal karakters, had een negatief effect. Gebruik van een gemiddelde lengteverhouding op karakterniveau tussen het Nederlands en het Engels van 1:1 in plaats van het vastgestelde 1:0,904 had geen negatief effect, en 1:1 zou zodoende gebruikt kunnen worden als taalonafhankelijk gemiddelde, mede omdat Gale en Church deze waarde ook gebruikten voor de taalparen Engels-Duits en Engels-Frans. Concluderend kan gesteld worden dat de methode, problemen bij de zinsherkenning in aanmerking nemende, goed voldoet. Gezien de grote efficiëntie is er nog ruimte over binnen het algorithme voor eventuele toevoegingen die voor verbetering zouden Alignering van Tweetalige Corpora als Vertaalhulp

42

kunnen zorgen. Hierbij valt te denken aan het gebruik van lexicale informatie, zodat een nog grotere precisie kan worden bereikt.

LITERATUURLIJST

Bellman, Richard (1957), Dynamic Programming. Princeton University Press, Princeton, NJ. Blank, Inge (1995). "Sentence Alignment: Methods and Implementations." In Traitement Automatique des Langues , 36(1-2), 81-96. Brown, Peter F., John Cocke, Stephen A. Della Pietra, Vincent J. Della Pietra, Fredrick Jelinek, John D. Lafferty, Robert L. Mercer, and Paul S. Roossin, (1990). "A statistical approach to machine translation." In Computational Linguistics, 16(2), 79-85. Chen, Stanley F. (1993). "Aligning Sentences in Bilingual Corpora Using Lexical Information." In 31st Annual Meeting of the Association for Computational Linguistics, Association for Computational Linguistics, 9-16. Church, Kenneth W. (1993). "Char_align: A Program for Aligning Parallel Texts at the Character Level." In 31st Annual Meeting of the Association for Computational Linguistics, Association for Computational Linguistics, 1-8. Fung, P. and K. Church, (1994). "K-vec: a new approach for aligning parallel texts." In Computational Linguistics. internet: http://www.ee.ust.hk/~pascale/coling94.Fung_Church.ps Gale, William and Kenneth W. Church, (1991). "A Program for Aligning Sentences in Bilingual Corpora." In Proceedings of the 29th Annual Meeting of the Association for Computational Linguistics, Berkeley, CA, 177-184. Gale, William A. and Kenneth W. Church, (1993). "A Program for Aligning Sentences in Bilingual Corpora." In Computational Linguistics, 19(1), 75-102. Kay, Martin and Martin Röscheisen, (1993). "Text-Translation Alignment." In Computational Linguistics, 19(1), 121-142. Kruskal, Joseph B. (1983). "An Overview of Sequence Comparison." In Sankoff, David en Joseph B. Kruskal, (Eds.), Time Warps, String Edits, and Macromolecules: the Theory and Practice of Sequence Comparison. Reading, Addison-Wesley, 1-44. Levenshtein, V. I. (1966). "Binary codes capable of correcting deletions, insertions and reversals." In Cybernetics and Control Theory, Vol. 10, Nr. 8, 707-710. Alignering van Tweetalige Corpora als Vertaalhulp

43

Melamed, I. Dan (1999). "Bitext Maps and Alignment via Pattern Recognition." In Computational Linguistics, 25(1), 107-130. Nerbonne, J. (1999). "Edit Distance and Dialect Proximity." In Sankoff, David en Joseph B. Kruskal, (Eds.), Time Warps, String Edits, and Macromolecules: the Theory and Practice of Sequence Comparison. Reprint, with a foreword by John Nerbonne, Stanford, CA, CSLI Publications, v-xv. Simard, Michel, George F. Foster, and Pierre Isabelle (1992). "Using Cognates to Align Sentences in Bilingual Corpora." In Proceedings of the Fourth International Conference on Theoretical and Methodological Issues in Machine Translation (TMI-92), Montreal, Canada, 67-81. Tjong Kim Sang, Erik F. (1996). "Aligning the Scania Corpus". internet: http://santana.uni-muenster.de/Library/ParallelCorpora/tjong.ps

Gebruikt testmateriaal:

European Central Bank, Annual Report 1999. Frankfurt am Main, 2000. ISSN 1561-4573 Europese Centrale Bank, Jaarverslag 1999. Frankfurt am Main, 2000. ISSN 1561-459X Europese Ombudsman, De, Jaarverslag 1996. Luxemburg, 1997. ISBN 92-823-1015-9 European Ombudsman, The, Annual Report for 1996. Luxemburg, 1997. ISBN 92-823-1012-4 Harvey, W. F. "August Heat". In Harvey, W. F., The Beast With Five Fingers & other Midnight Tales. Ed. by Maurice Richardson. London, Aldine, 1962, 133-138. Harvey, W. F. "Augustus Hitte". In Griezelverhalen. Verzameld en vert. door Havank. Utrecht, Bruna, 1957, 118-125.


44

BIJLAGE

C++ BRONCODE

Het hieronder afgebeelde programma verwacht als invoer de twee te aligneren tekstbestanden. De bestanden bevatten per regel één zin. Grenzen tussen tekstdelen kunnen worden aangegeven met een regel die slechts bestaat uit het # teken. De uitvoer laat de alignering zien aan de hand van de toegepaste operaties. // align program v1.0 by Robbert Prins // using the Gale & Church (1993) method // USAGE: // // align <source_text> [] [> output_file] // // where: // // source_text is the original text (Dutch) // target_text is the translation (English) // opt_n is the optimalisation range to the left and right // output_file is the file that will contain the alignment // // notes: // // redirection has to be used to write to an output file // texts should contain 1 sentence on each line // lines containing only # character mark divisions // both texts must have same number of divisions (regions) #include #include #include #include #include #include #include #include

<stdlib.h> <math.h> <string>

clock_t t1,t2; ifstream input_1, input_2; ofstream output; typedef struct { float


45

D; int x,y; } gridPosition; typedef struct operationNode_tag { int operation; operationNode_tag *next; } operationNode; typedef struct regionNode_tag { int startline, endline; regionNode_tag *next; } regionNode;

//////////////////////////////// // FUNCTIONS // //////////////////////////////// int count_sentences(ifstream &sourcefile) { int sentences = 0; string sentence; while(getline(sourcefile,sentence)) ++sentences; return(sentences); } int get_lengths(ifstream &sourcefile, int *lengths, int &total_sentences, regionNode *regions) { sentence_number = 1, characters = 0, regions_counted = 0; char ch; lengths[0] = 0;

// skipped

regionNode *currentRegion; currentRegion = regions; currentRegion->startline = 1; while(sentence_number <= total_sentences) { while(sourcefile.get(ch) && ch != '\n' && ch != '#') ++characters; lengths[sentence_number] = characters; characters = 0; if (ch == '#') { ++regions_counted;


46

currentRegion->endline = sentence_number - 1; regionNode *newRegion = new regionNode; currentRegion->next = newRegion; currentRegion = newRegion; currentRegion->startline = sentence_number + 1; while (sourcefile.get(ch) && ch != '\n') {} } ++sentence_number; } ++regions_counted; currentRegion->endline = sentence_number - 1; currentRegion->next = NULL; return(regions_counted); } double pNorm(double z) { double t,pd; t = 1/(1 + 0.2316419 * z); pd = 1 - 0.3989423 * exp(-z * z/2) * ((((1.330274429 * t - 1.821255978) * t + 1.781477937) * t - 0.356563782) * t + 0.319381530) * t; ///////////////////////////////////////////////////// // This function is from the Gale & Church // // implementation. It is based on an approximation // // by Abramowitz and Stegun: // // // // Abramowitz, M. en I. Stegun, // // "Handbook of Mathematical Functions", // // 1964, p.932, equation 26.2.17 // ///////////////////////////////////////////////////// return(pd); } float prob(int matchType) { if (matchType == 1) return(0.9456); if (matchType == 2) return(0.0026); if (matchType == 3) return(0.0026); if (matchType == 4) return(0.0207); if (matchType == 5) return(0.0259); return(0.0026); }

// // // // // //

substitution insertion deletion contraction expansion merge/swap

float distanceBetween(int l1, int l2, int matchType) { float delta; double probDelta; float c = 0.904, s2 = 4.7; delta = (l2 - l1*c) / sqrt(l1*s2); probDelta = 2 * (1 - pNorm((double)fabs(delta)));


47

if (probDelta > 0) return(-100 * log(probDelta * prob(matchType))); else return(MAXFLOAT); } float distance(int L1, int L2, int L12, int L22) { if (L12 == 0 && L22 == 0) { if (L1 == 0) return(distanceBetween(0,L2,2)); else if (L2 == 0) return(distanceBetween(L1,0,3)); else return(distanceBetween(L1,L2,1)); } else { if (L22 == 0) return(distanceBetween(L1+L12,L2,4)); else if (L12 == 0) return(distanceBetween(L1,L2+L22,5)); else return(distanceBetween(L1+L12,L2+L22,6)); } }

// insertion // deletion // substitution

// contraction // expansion // merge/swap

void show_alignment(operationNode *node) { string sen11,sen12, sen21,sen22; cout << endl; while (node) { switch (node->operation) { case 1: { getline(input_1,sen11); getline(input_2,sen21); cout << sen11 << endl << sen21 << endl; break; } case 2: { getline(input_2,sen21); cout << "..." << endl << sen21 << endl; break; } case 3: { getline(input_1,sen11); cout << sen11 << endl << break; } case 4: { getline(input_1,sen11); getline(input_1,sen12); getline(input_2,sen21); cout << sen11 << endl << << endl << sen21 <<


"---<sub>---" << endl <<

"------" << endl <<

"---<del>---" << endl <<

sen12 << endl << "------" endl;

48

break; } case 5: { getline(input_1,sen11); getline(input_2,sen21); getline(input_2,sen22); cout << sen11 << endl << "---<exp>---" << endl << sen21 << endl << sen22 << endl; break; } case 6: { getline(input_1,sen11); getline(input_1,sen12); getline(input_2,sen21); getline(input_2,sen22); cout << sen11 << endl << sen12 << endl << "---<mer>---" << endl << sen21 << endl << sen22 << endl; break; } case 7: { // skip separators (#) getline(input_1,sen11); getline(input_2,sen21); break; } } cout << "############################################################## ################" << endl; node = node->next; } } operationNode *align(int *L1, int *L2, regionNode *regions_1, regionNode *regions_2, int &opt_n) { // target text variables: L2,regions_2,add_2,j // // // // //

Note that opt_n is the optimalisation range. This range extends to the left AND to the right of the projected sentence location, so the actual number of sentences to be considered for each sentence in the source text is (opt_n * 2 + 1).

regionNode *currentRegion_1 = regions_1, *currentRegion_2 = regions_2; operationNode *startNode = 0, *lastNode = 0; while (currentRegion_1) { gridPosition **grid; int count1 = currentRegion_1->endline - currentRegion_1->startline + 1, count2 = currentRegion_2->endline - currentRegion_2->startline + 1, add_1 = currentRegion_1->startline - 1, add_2 = currentRegion_2->startline - 1; // Note that add_1 and add_2 compensate for the fact that an


49

// array does not start at 1, while a region does. grid = new gridPosition* [count1+1]; // extra row (0) for (int i=0; i<=count1 ; ++i) grid[i] = new gridPosition[count2+1]; // extra column (0) // prepare grid for optimalisation (Kruskal 1983) for (int i=0; i<=count1; ++i) for (int j=0; j<=count2; ++j) grid[i][j].D = MAXINT; // start with D = 0 on position (0,0): grid[0][0].D = 0; float D,D1,D2,D3,D4,D5,D6; int lower_bound, upper_bound; float factor = float(count2)/float(count1); for (int i=0 ; i<=count1 ; ++i) { if (opt_n == -1) { lower_bound = 0; upper_bound = count2; } else { float float_center = float(i) * factor; int center = int(ceil(float_center)); lower_bound = (center(count2-opt_n) ? count2 : center+opt_n); } for (int j=lower_bound ; j<=upper_bound ; ++j) { // compute D for each of these operations: ////////////////////// // 1 = substitution // // 2 = insertion // // 3 = deletion // // 4 = contraction // // 5 = expansion // // 6 = merge (swap) // ////////////////////// D1 = i>0 && j>0 ? grid[i-1][j-1].D : MAXINT; D2 = j>0 ? grid[i][j-1].D + : MAXINT; D3 = i>0 ? grid[i-1][j].D : MAXINT; D4 = i>(1) && j>0 ? grid[i-2][j-1].D

+ distance(L1[i+add_1],L2[j+add_2],0,0)

distance(0,L2[j+add_2],0,0)

+ distance(L1[i+add_1],0,0,0)

+ distance(L1[i-


50

1+add_1],L2[j+add_2],L1[i+add_1],0) : MAXINT; D5 = i>0 && j>1 ? grid[i-1][j-2].D + distance(L1[i+add_1],L2[j1+add_2],0,L2[j+add_2]) : MAXINT; D6 = i>1 && j>1 ? grid[i-2][j-2].D + distance(L1[i-1+add_1],L2[j1+add_2],L1[i+add_1],L2[j+add_2]) : MAXINT; // select smallest D D if if if if if

(D2
D D D D D

= = = = = =

D1; D2; D3; D4; D5; D6;

if (i == 0 && j == 0) D = 0; // store D and pointer grid[i][j].D = D; if (D == D1) { grid[i][j].x = grid[i][j].y = } else if (D == D2) { grid[i][j].x = grid[i][j].y = } else if (D == D3) { grid[i][j].x = grid[i][j].y = } else if (D == D4) { grid[i][j].x = grid[i][j].y = } else if (D == D5) { grid[i][j].x = grid[i][j].y = } else if (D == D6) { grid[i][j].x = grid[i][j].y = }

-1; -1;

-1; 0;

0; -1;

-1; -2;

-2; -1;

-2; -2;

} } operationNode *node = new operationNode, *storeLast; node->next = NULL; // store last node storeLast = node;


51

int i = count1,x, j = count2,y; // DO BACKTRACKING while (i > 0 || j > 0) { x = grid[i][j].x; y = grid[i][j].y; if (x == -1 && y == -1) node->operation = 1; else if (x == -1 && y == 0) node->operation = 2; else if (x == 0 && y == -1) node->operation = 3; else if (x == -1 && y == -2) node->operation = 4; else if (x == -2 && y == -1) node->operation = 5; else if (x == -2 && y == -2) node->operation = 6;

// substitution // insertion // deletion // contraction // expansion // merge

i += y; j += x; operationNode *previousNode = new operationNode; previousNode->next = node; node = previousNode; } if (!startNode) startNode = node->next; else { lastNode->next = node->next;

// skip 0,0

// skip 0,0

operationNode *skipNode = new operationNode; skipNode->operation = 7; skipNode->next = node->next; lastNode->next = skipNode; } lastNode = storeLast; delete[] grid; // next regions currentRegion_1 = currentRegion_1->next; currentRegion_2 = currentRegion_2->next; } // operaties retourneren return(startNode); } /////////////////////////////////////// // MAIN FUNCTION // /////////////////////////////////////// int main(int argc, char **argv)


52

{ // take note of current time (for measure time used) t1 = clock(); /////////// // USAGE // /////////// if(argc==1 || argc>4) { cout << "align usage: 'align <sourcefile1> <sourcefile2> [] [> ]" << endl; return(1); opt_n; if (argc == 4) { cout << endl << "optimalisation; left and right range " << argv[3] << endl; opt_n = atoi(argv[3]); } else { cout << endl << "no optimalisation." << endl; opt_n = -1; } cout << endl << "sourcefile1: " << argv[1] << endl; cout << "sourcefile2: " << argv[2] << endl; //////////////////////////////////////// // OPEN FILES FOR READING AND WRITING // //////////////////////////////////////// input_1.open(argv[1],ios::in); if(!input_1) { cout << "error opening sourcefile1" << endl; return(1); } input_2.open(argv[2],ios::in); if(!input_2) { cout << "error opening sourcefile2" << endl; return(1); } if(argc==4) { output.open(argv[3],ios::out); if(!output) { cout << "error creating output file" << endl; return(1); } } ///////////////////////////////////// // COUNT SENTENCES IN FILE 1 AND 2 // ///////////////////////////////////// int sentence_count_1, sentence_count_2; sentence_count_1 = count_sentences(input_1); sentence_count_2 = count_sentences(input_2);


53

cout << endl << "sentences text 1: " << sentence_count_1 << endl; cout << "sentences text 2: " << sentence_count_2 << endl; /////////////////////////////////// // RESET FILES FOR RE-READING... // /////////////////////////////////// input_1.close(); input_2.close(); input_1.open(argv[1],ios::in); input_2.open(argv[2],ios::in); ////////////////////////////////////////////////////////// // GET LENGTHS OF SENTENCES AND REGIONS IN FILE 1 AND 2 // ////////////////////////////////////////////////////////// int sentence_length_1[sentence_count_1+1], sentence_length_2[sentence_count_2+1], regions_counted_1, regions_counted_2; regionNode *regions_1 = new regionNode, *regions_2 = new regionNode; regions_counted_1 = get_lengths(input_1,sentence_length_1,sentence_count_1,regions_1); regions_counted_2 = get_lengths(input_2,sentence_length_2,sentence_count_2,regions_2); if (regions_counted_1 != regions_counted_2) { cout << endl << "error: files should contain same number of regions! (#)" << endl; return(1); } input_1.close(); input_2.close(); ////////////////// // DO ALIGNMENT // ////////////////// operationNode *operations = new operationNode; operations = align(sentence_length_1,sentence_length_2,regions_1,regions_2,opt_n); input_1.open(argv[1],ios::in); input_2.open(argv[2],ios::in); show_alignment(operations); input_1.close(); input_2.close(); cout << endl << "done." << endl; // end time t2 = clock(); cout << endl << "time: " << (t2-t1)/float(CLK_TCK) << "sec." << endl; return(0); }


54

Alignering van Tweetalige Corpora als Vertaalhulp

Recommend Documents