3784499247

2.1.1.2.3.    Niewielkie wymagania pamięciowe

Algorytmy bazujące na długościach segmentów zużywają także niewielką ilość pamięci - w pamięci wystarczy przechowywać długości segmentów, nie trzeba przechowywać ich treści.

2.1.1.3.    Wady algorytmów bazujących na długościach segmentów

2.1.1.3.1.    Niska dokładność urównoleglenia dla trudnych tekstów

Wadą algorytmów bazujących na długościach segmentów jest niska dokładność dopasowania dla „trudnych tekstów”, np. jeśli tłumaczenie jest swobodne, jeśli w tekstach następują po sobie segmenty podobnej długości albo jeśli w którymś z tekstów występują pominięcia dużych fragmentów tekstu. Niska dokładność wynika z faktu, że do znalezienia urównoleglenia używana jest tylko niewielka część informacji leksykalnej zawartej w segmentach.

2.1.2. Sposób działania algorytmu

2.1.2.1.    Szkielet algorytmu urównoleglania

Wyszukiwane jest urównoleglenie, które jako całość, ma największe prawdopodobieństwo, czyli którego iloczyn prawdopodobieństw kolejnych dopasowań jest najwyższy¹². Algorytm opiera się na programowaniu dynamicznym¹¹, a sposób jego działania można opisać za pomocą równania rekurencyjnego¹⁴.

Niech S będzie tekstem źródłowym, a T tekstem docelowym. Niech S₁,S₂,...,S_n będą segmentami tekstu źródłowego, a t_lr t₂,..., t_m segmentami tekstu docelowego.

Niech C=(C₁,C₂, ...,C_rj będzie zbiorem kategorii dopasowań, gdzie C, = (e,-f,) jest kategorią dopasowania dopasowującą e, segmentów źródłowych do f, segmentów docelowych. Przykładowo w przypadku mojej implementacji rozważane są domyślnie następujące kategorie dopasowań: C={(l-0),(0—1),(1-1),(2 — l),(l-2),(2—2)}, co oznacza na przykład, że jednemu segmentowi źródłowemu może odpowiadać zero (1-0), jeden (1-1) lub dwa (1-2) segmenty docelowe. Występuje też dopasowanie (2-2), kiedy kolejne zdania są wzajemnie

12    Można tu znaleźć analogię do algorytmu Viterbiego związanego z niejawnymi modelami Markowa, ale analogia ta wykracza poza zakres niniejszej pracy. Więcej informacji dotyczących niejawnych modeli Markowa można znaleźć w [Rabiner. 1989],

13    Programow anie dynamiczne jest strategią projektow ania algory tmów polegającą, podobnie jak w strategii „dziel i zwyciężaj”, na podziale rozwiązywanego problemu na podproblemy. Poprzez odpowiednie złożenie rozwiązań podproblemów uzyskuje się rozw iązanie głównego problemu. Programów anie dynamiczne stosuje się. gdy podproblemy nie są niezależne, tza gdy podproblemy mają wspólne podproblemy. W programowaniu dynamicznym zapamiętuje się wszystkie potrzebne rozw iązania podproblemów. by nie musieć ich rozwiązywać ponownie. Patrz [Cormen i in., 2001]. rozdział 16.

14    Poniższe oznaczenia różnią się od używanych w arty kule [Gale. Church, 1991] i stanow ią ich uogólnienie, tak żeby lepiej pasow ały do dalszej części pracy w szczególności do opisu algory tmu Moore'a.

17