3784499248

wymieszane lub zamienione.

Następnie, niech p(x, y ,e ,f) będzie funkcją określającą prawdopodobieństwo dopasowania segmentów S_X,S_X+1,S_x+e_₁¹⁵ do segmentów t_y,t_y+1,... ,t_y+f_₁.

Niech P(x,y) będzie maksymalnym prawdopodobieństwem dopasowania segmentów S₁...S_X do segmentów t₁...t_y, P(x,y) jest obliczane rekurencyjnie poprzez maksymalizację po wszystkich kategoriach dopasowania.

Warunek początkowy:

P{ 0,0)=1

Definicja rekurencyj na gdy x>0vy>0 dla x>0,y>0,x<n, y <m :

P(x,y)= max    {P(x-e,y-f)p(x-e+l,y-f+l,e,f)}

(e-fleC:x-ezO,y-fzO

Prawdopodobieństwo szukanego, najlepszego dopasowania dla całych tekstów S i T wynosi P(n,m).

Żeby uzyskać samo urównoleglenie trzeba dodatkowo rekurencyjnie obliczać wartość Q(x ,y), określającą najbardziej prawdopodobną kategorię dopasowania na pozycji X, y :

0(0,0)=nieokreślony

Q(x,y)=    argmax    {P(x-e,y-f)p(x-e+l,y-f+l,e,f)}

{e-f)eC:x-ez0,y-f&0

Następnie za pomocą techniki zwanej backlracking można uzyskać szukaną listę dopasowań A = (a₁,a₂,a_u), czyli właściwe urównoleglenie. Najpierw definiuje się pomocniczą listę pozycji wtekstach D=(d₀,d₁,d₂,d_u) : d„=(n,m)

d„=(x-e,y-f), gdzie (x,y)=d_k_₁,(e-f)=Q(x,y)

Oblicza się d_k dopóki x-e>0vy-f>0 . Dla ostatniego k spełniającego ten waninek przyjmuje się, że U=k. Następnie oblicza się urównoleglenie:

3;=((S_X,S_X+1.....S_x+e_₁)_f(t_y,t_y+1,...,t_y+f_₁)),

gdzie (e-f)=0(x,y),a (x,y)=d_u__/+1, i=l,2,...u.

15 Gdy e = 0 to nic ma segmentów źródłowy cli w dopasowaniu; podobnie jest w pr/y padku segmentów docelowy ch gdy f = 0

18