Korekcja ciągów za pomocą odległości Damerau-Levenshtein

Możliwości podziału śladuDL. a Bez przejścia przez środek b Z przejściem przez środek

Niech T będzie optymalnym śladem spełniającym własności P2-P4. Jeśli T nie zawiera przejścia przez środek, to jego linie można podzielić na zbiory TL i TR takie, że TL zawiera wszystkie linie (u,v)∈T z v≤n/2, a TR zawiera pozostałe linie (Rys. 4a). Ponieważ nie ma przejścia przez środek, wszystkie linie w TR mają wartość u większą niż wartość u każdej linii w TL. Z własności P2-P4 wynika, że istnieje i, 1≤i≤m takie, że T jest unią optymalnego śladu dla A i B oraz tego dla A i B. Niech H będzie kosztem pierwszego optymalnego śladu, a H′ kosztem drugiego optymalnego śladu. Widzimy, że gdy T nie ma przejścia przez środek, koszt T wynosi

Gdy T zawiera przejście przez środek, jego linie mogą być podzielone na 3 zbiory, TL, TM i TR, jak pokazano na Rys. 4b. Niech (u1,v1) i (u2,v2) będą liniami definiującymi środkowe skrzyżowanie. Zauważmy, że TL zawiera wszystkie linie T z v<v2, TR zawiera wszystkie linie z v>v1, a TM={(u1,v1),(u2,v2)}. Zauważmy też, że wszystkie linie w TL mają u<u1, a wszystkie w TR mają u>u2. Z własności P1 wynika, że TL jest optymalnym śladem dla A i B, a TR jest optymalnym śladem dla A i B. Dalej, ponieważ (u1,v1) i (u2,v2) są liniami zrównoważonymi, koszt TM wynosi (u2-u1-1)+1+(v1-v2-1). Ponadto, A≠A jakżeby inaczej, zastępując linie przecinające środek przez (u1,v2) i (u2,v1) otrzymujemy ślad o niższym koszcie. Z własności P4 wiemy, że \u_{1} = lastA\u_{1}) oraz \u_{2} = lastB\u_{2} = lastB\u_{1}). Niech H będzie kosztem optymalnego śladu dla A i B oraz niech H′ będzie kosztem optymalnego śladu dla A i B. Zatem, gdy T ma środkowe przejście, jego koszt wynosi

m).}\). Dla każdego u1 badamy wszystkie znaki w alfabecie inne niż a_{u_{1}}. Dla każdego takiego znaku c, v2 jest ustawione na największe j≤n/2, dla którego bj=c, a u2 jest najmniejszym i>u1, dla którego ai=c. Zatem min jest brane z (s-1)m terminów.

Niech Utop i Ttop będą końcowymi tablicami U i T obliczonymi przez LS_DL przy wejściach B i A, a Ubot i Tbot będą tymi tablicami, gdy wejścia są odwrotne do B i A. Z tych tablic możemy łatwo wyznaczyć wartości H i H′ potrzebne do obliczenia równań 3 i 4. Algorytm LSDL_TRACE (Algorytm 4) dostarcza pseudokodu dla naszych obliczeń optymalnego śladu w przestrzeni liniowej. Zakłada on, że LS_DL został zmodyfikowany, aby zwrócić obie tablice U i T.

Jeśli chodzi o złożoność czasową, widzimy, że na najwyższym poziomie rekurencji wywołujemy LS_DL dwa razy z ciągami A i B o rozmiarach odpowiednio m i n/2. Zajmuje to co najwyżej amn czasu dla pewnej stałej a. Czas potrzebny na obliczenie równań 3 i 4 jest O(sn) i może być wchłonięty do amn przez użycie odpowiednio dużej stałej a. Na następnym poziomie rekurencji LS_DL jest wywoływany 4 razy. Suma długości łańcuchów A w tych 4 wywołaniach wynosi co najwyżej 2m, a łańcuch B ma długość co najwyżej n/4. Zatem czas dla tych czterech wywołań wynosi co najwyżej amn/2. Generalizując do pozostałych poziomów rekurencji, widzimy, że algorytm LSDL_TRACE zajmuje amn(1+1/2+1/4+1/8+…)<2amn=O(mn) czasu. Potrzebna przestrzeń jest taka sama jak dla LS_DL (zauważ, że parametry do tego algorytmu zostały zamienione). Z analizy czasu wynika, że liczba chybień pamięci podręcznej jest w przybliżeniu dwa razy większa niż dla LS_DL, gdy wywoływany jest z ciągami o rozmiarach m i n. Stąd przybliżona liczba chybień pamięci podręcznej dla LSDL_TRACE wynosi 2mn(1+3/w).

Zauważamy, że pewne skrócenie rzeczywistego czasu działania można osiągnąć przez przełączanie A i B, gdy A jest krótsze niż B, zapewniając w ten sposób, że krótszy ciąg jest dzielony na każdym poziomie rekurencji. To pozwala nam uzyskać szybsze zakończenie rekurencji.

Algorytm strip trace S t r i p_T R A C E

Algorytm ten różni się od LSDL_TRACE tym, że używa zmodyfikowanej wersji Strip_DL zamiast zmodyfikowanej wersji LS_DL. Zmodyfikowana wersja Strip_DL zwraca tablice strip i V obliczone przez Strip_DL. Odpowiednio, Strip_TRACE używa Vtop i Vbot zamiast Ttop i Tbot. Asymptotyczna złożoność czasowa Strip_TRACE również wynosi O(mn) i zajmuje tyle samo miejsca co Strip_DL (zauważ, że parametry do Strip_DL są zamienione względem tych do Strip_TRACE). Liczba pominięć pamięci podręcznej jest w przybliżeniu dwukrotnie większa niż dla Strip_DL.

Algorytmy wielordzeniowe

W tej sekcji opisujemy nasze paralelizacje algorytmu DL i czterech algorytmów jednordzeniowych z poprzedniej sekcji. Paralelizacje te zakładają, że liczba procesorów jest mała w stosunku do długości ciągu. Przyjęta przez nas konwencja nazewnicza dla wersji równoległych polega na dodaniu PP_ jako przedrostka do nazwy algorytmu jednordzeniowego.

Algorytm P P_D L

Nasza równoległa wersja algorytmu DL, PP_DL, oblicza elementy w tej samej kolejności co DL. Rozpoczyna on jednak obliczanie wiersza, zanim zakończy się obliczanie poprzedniego wiersza. Każdy procesor otrzymuje unikalny wiersz do obliczenia i oblicza ten wiersz od lewej do prawej. Niech p będzie liczbą procesorów. Procesor z jest początkowo przydzielony do wykonywania obliczeń pętli zewnętrznej dla i=z, 1≤i≤p. Procesor z startuje z odpowiednim opóźnieniem w stosunku do startu procesora z-1, tak aby dane potrzebne do jego obliczeń zostały już obliczone przez procesor z-1. W naszym kodzie opóźnienie między startem obliczeń dwóch kolejnych wierszy jest równe czasowi potrzebnemu na obliczenie n/p elementów. Po zakończeniu obliczeń w iteracji i, procesor przechodzi do iteracji i+p pętli zewnętrznej. Złożoność czasowa PP_DL wynosi O(mn/p).

Algorytm P P_L S_D L

Pomimo, że ogólna strategia paralelizacji dla PP_LS_DL jest taka sama jak ta użyta w PP_DL, potrzebna jest dodatkowa uwaga, aby zapewnić identyczne obliczenia jak w LS_DL. Rozbieżność wyników jest możliwa, gdy dwa lub więcej procesorów jednocześnie oblicza różne rzędy H korzystając z tej samej pamięci. Dzieje się tak na przykład wtedy, gdy A=aaabc⋯ i p≥3. Zaczynamy od procesora i przypisanego do obliczania wiersza i w H, 1≤i≤p. Załóżmy, że początkowo U=x i T=y (zauważmy, że x i y są adresami w pamięci). Z powodu instrukcji swap(T],U) w LS_DL, procesor 1 zaczyna obliczać wiersz 1 H korzystając z pamięci zaczynającej się pod adresem y. Jeśli procesor 2 zacznie z odpowiednim opóźnieniem, jak w PP_DL, to będzie obliczał wiersz 2 H korzystając z pamięci zaczynającej się pod adresem x. Z kolejnym opóźnieniem, procesor 3 zacznie obliczać wiersz 3 H ponownie używając pamięci zaczynającej się pod adresem y. Teraz oba procesory 1 i 3 używają tej samej pamięci do obliczania różnych wierszy H, a więc ryzykujemy nadpisanie wartości H, które mogą być potrzebne do kolejnych obliczeń. Jako inny przykład, rozważmy A=ababa⋯ i p≥4. Załóżmy, że U=x i T= początkowo. Procesor 1 zaczyna obliczać wiersz 1 korzystając z pamięci y, następnie, z opóźnieniem, procesor 2 zaczyna obliczać wiersz 2 korzystając z pamięci z, następnie procesor 3 zaczyna obliczać wiersz 3 korzystając z pamięci x. Następnie procesor 4 zaczyna obliczać wiersz 4 korzystając z pamięci y. W tym czasie procesor 1 oblicza wiersz 1 z A=a, a procesor 4 oblicza wiersz 4 z A=b i oba procesory używają tej samej pamięci wiersza y.

Pozwólmy p1 i p2 być dwoma procesorami, które używają tej samej pamięci do obliczenia wierszy r1<r2 H i że żaden procesor nie używa tej pamięci do obliczenia wiersza pomiędzy r1 i r2. Ze schematu przydziału zamiany używanego w LS_DL wynika, że p1 oblicza rząd \(r_{1} = lastA-1phantom {\i0}}). Wartości H w tym rzędzie są potrzebne do obliczenia rzędów od r1+1 do r2 jako \(r_{1} = lastA-1}phantom {\i}}).}r_{1} = lastA r_{1} < i > r_{2}). Wartości te nie są potrzebne dla wierszy i>r2, ponieważ dla tych wierszy \(\\\}lastA = r_{2} > r_{1} + 1 = lastA). Niech j1 będzie takie, że \u00}(\u00}b_{j} = a_{r_{2}} = a_{r_{1} + 1}}). Wtedy dla j>j1, \(\antom {\i0}}lastB \i0} = a_{r_{1}}). Stąd dla j>j1 kolumny od 1 do j1-2 z wiersza r1 nie są potrzebne do obliczenia H w wierszach pomiędzy r1 i r2.

Nasz kod równoległy wykorzystuje schemat synchronizacji, który opiera się na obserwacjach z poprzedniego akapitu, aby opóźnić nadpisywanie wartości, które są potrzebne do późniejszych obliczeń i zapewnić poprawne obliczenie odległości DL. Nasz schemat synchronizacji wykorzystuje kolejną tablicę W, która jest inicjalizowana na 1. Załóżmy, że jeden z procesorów oblicza wiersz i w H i że A=a. Gdy procesor ten po raz pierwszy napotka a w B, powiedzmy na pozycji j1, inkrementuje W. Gdy napotka kolejne a, powiedzmy na pozycji j2, inkrementuje W o 1. Gdy procesor zakończy obliczanie wiersza i, pozostałe pozycje W są inkrementowane o 1. Procesor wyznaczony do obliczania wiersza q w H może obliczać U iff W=q. Z naszych wcześniejszych obserwacji wynika, że gdy W=q, stare wartości na pozycjach pamięci U mogą zostać nadpisane, gdyż nie są one potrzebne do przyszłych obliczeń.

Złożoność czasowa tego p-procesorowego algorytmu PP_LS_DL zależy od zbiorów danych, gdyż opóźnienie synchronizacji jest zależne od danych. Spodziewamy się jednak, że gdy znaki w B są w przybliżeniu równomiernie rozłożone, czas działania wyniesie około O(mn/p).

Algorytm P P_S t r i p_D L

W równoległej wersji PP_Strip_DL algorytmu Strip_DL, procesor i jest początkowo przydzielony do obliczania paska i, 1≤i≤p. Po zakończeniu aktualnie przydzielonego paska j, procesor ten przystępuje do obliczania paska j+p. Do celów synchronizacji wykorzystywany jest sygnał tablicowy. Podczas obliczania wiersza r w przydzielonym mu pasku s, procesor musi czekać aż signal=s. signal jest ustawiany na s przez procesor pracujący nad paskiem s-1, gdy wartości na lewo od paska s potrzebne do obliczenia wiersza r paska s zostały obliczone i nie ma ryzyka, że obliczenia dla wiersza r paska s nadpiszą wartości V potrzebne innym procesorom. signal działa bardzo podobnie jak W w PP_LS_DL.

Zauważmy, że gdy pracujemy na p paskach, potrzebujemy p kopii tablic U i T używanych przez Strip_DL.

Złożoność czasowa PP_Strip_DL zależy od opóźnienia synchronizacji i oczekuje się, że będzie przybliżona do O(mn/p).

Algorytm P P_D L_T R A C E

Algorytm ten najpierw używa PP_DL do obliczenia H. Następnie pojedynczy procesor wykonuje traceback w celu skonstruowania optymalnego śladu. Dla rozsądnych wartości p, czas działania jest zdominowany przez PP_DL, a więc złożoność PP_DL_TRACE również wynosi O(mn/p).

Algorytmy P P_L S D L_T R A C E i P P_S t r i p_T R A C E

W LSDL_TRACE (Strip_TRACE), wielokrotnie dzielimy problem na dwie części i do każdej z nich stosujemy LS_DL (Strip_DL). Wersja równoległa PP_LSDL_TRACE (PP_Strip_TRACE) wykorzystuje następującą strategię paralelizacji:

• Każdy podproblem jest rozwiązywany za pomocą PP_LS_DL (PP_Strip_DL), gdy liczba niezależnych podproblemów jest mała; wszystkie p procesorów są przydzielone do równoległego rozwiązania pojedynczego podproblemu. Tzn. podproblemy są rozwiązywane sekwencyjnie.

• Podproblemy są rozwiązywane równolegle przy użyciu LS_DL (Strip_DL), aby rozwiązać każdy podproblem szeregowo, gdy liczba niezależnych podproblemów jest duża,

Złożoność czasowa PP_LSDL_TRACE i PP_Strip_TRACE wynosi O(mn/p).