Oprava řetězců pomocí Damerau-Levenshteinovy vzdálenosti

Jednojádrové algoritmy

V této části vyvineme čtyři lineárně-prostorové jednojádrové algoritmy pro opravu řetězců pomocí vzdálenosti DL. Všechny čtyři běží v čase O(mn). První dva (LS_DL a Strip_DL) počítají pouze skóre Hmn optimální stopy; liší se svou efektivitou v mezipaměti. Poslední dva (LSDL_TRACE a Strip_TRACE) počítají optimální stopu.

Algoritmus lineárního prostoru L S_D L

Nechť s je velikost abecedy. Namísto pole H používaného v DL používá algoritmus LS_DL jednorozměrné pole U a dvourozměrné pole T. Tato dvě pole mají prostorové nároky O((s+1)n) = O(n) pro konstantní s. Při m<n lze prohodit A a B, aby se snížila potřebná paměť. Sečteme-li paměť potřebnou pro A a B, je prostorová složitost O(s min{m,n}+m+n) = O(m+n), když s je konstanta.

Stejně jako v algoritmu DL se hodnoty Hij počítají po řádcích. Jednorozměrné pole U slouží k uložení hodnot H vypočtených algoritmem DL, když se počítá řádek i. Nechť H je poslední řádek vypočtený pro znak c. Pak T je řádek w-1 H. Algoritmus 2 uvádí pseudokód pro LS_DL. Jeho správnost vyplývá ze správnosti algoritmu DL. Všimněte si, že swap(T],U) zabere O(1) času, protože se vyměňují ukazatele na 2 jednorozměrná pole, nikoliv obsah těchto polí. Počet chyb v mezipaměti pro LS_DL je při vhodně velkém n stejný jako pro DL, protože oba mají stejný vzor přístupu k datům. Pro menší instance však LS_DL bude vykazovat mnohem lepší chování při ukládání do mezipaměti. Například díky tomu, že využívá mnohem méně paměti, můžeme mít dostatek LLC cache pro uložení všech dat v LS_DL, ale ne v DL (O(sn) oproti O(mn)).

Lineárně prostorový algoritmus S t r i p_D L

Když je (s+1)n větší než velikost LLC cache, můžeme snížit počet chybění cache oproti algoritmu LS_DL výpočtem Hij po pásech o šířce q, pro nějaké q menší než n (poslední pás může mít šířku menší než q). To je znázorněno na obr. 3. Proužky se počítají v pořadí 0, 1,… pomocí algoritmu LS_DL. Prostor, který potřebují pole T a U v LS_DL, se však zmenší na (s+1)q, protože šířka proužku je q, a nikoli n. Volbou dostatečně malého q můžeme zajistit, že bloky polí T a U, které LS_DL používá, nebudou po zavedení z mezipaměti evikovány. Pokud tedy každá položka T a U zabere 1 slovo, pak při velikosti cache lw máme q<lw/(s+1). Všimněte si, že kromě T a U musí mezipaměť obsahovat i partiály polí A, B a dalších polí potřebných k předávání dat z jednoho pásu do druhého.

Výpočet H po pásech

Pro předávání dat z jednoho pásu do dalšího použijeme další jednorozměrné pole strip o velikosti m a dvourozměrné pole s∗m V. Pás pole zaznamenává hodnoty H vypočtené pro nejpravější sloupec v pásu. V udává hodnotu H v nejpravějším sloupci j řádku i pole H, který je (a) v pásu nalevo od právě počítaného a (b) c=B.

Pseudokód pro Strip_DL je uveden v algoritmu 3. Pro přehlednost používá tento pseudokód dvě pole strip (řádky 18 a 30) a dvě pole V (řádky 24 a 32). Jedna sada polí slouží k načtení dat vypočtených pro předchozí strip a druhá sada pro data, která mají být předána dalšímu stripu. Ve skutečné implementaci používáme jedno pole strip a jedno pole V, které přepisuje hodnoty získané z předchozího stripu hodnotami, které mají být předány dalšímu stripu.

Čas a složitost Strip_DL jsou O(mn), respektive O((s+1)m+(s+1)q+n) = O(sm+sq+n) = O(sm+n), protože q je konstanta. Když m>n, můžeme A a B prohodit, abychom ušetřili paměť, a tak se prostorová složitost stává O(s min{m,n}+m+n) = O(m+n) pro konstantní s.

Při analýze chybění cache si všimneme, že q je zvoleno tak, aby se U a T vešly do cache. Vycházíme z rozumného předpokladu, že pravidlo nahrazování LRU nezpůsobí, že by během běhu algoritmu Strip_DL došlo k evikci některého bloku U nebo T. V důsledku toho je celkový počet zmeškání mezipaměti způsobených U a T nezávislý na m a n, a proto jej lze v analýze ignorovat. Inicializace strip a V má za následek m/w a (s+1)m/w přístupů ke čtení. Počet přístupů pro zápis je přibližně stejný jako počet přístupů pro čtení. Výpočet pro každý pás přistupuje k pásu pole ve vzestupném pořadí podle indexu. Výsledkem je (přibližně) stejný počet zmeškání mezipaměti, jaký byl proveden během inicializační fáze. Proto je celkový počet zmeškání mezipaměti kvůli proužku přibližně (2m/w)(n/q+1). Pro V si uvědomíme, že při výpočtu aktuálního proužku se k prvkům v libovolném řádku V přistupuje v neklesajícím pořadí indexu (tj. zleva doprava) a že pro každý znak abecedy potřebujeme v mezipaměti uchovat pouze naposledy přečtenou hodnotu (tj. je třeba uchovat nejvýše s hodnot). Za předpokladu, že hodnota V je z cache evokována pouze při přístupu k nové hodnotě téhož znaku, je celkový počet zmeškaných čtení z V při výpočtu jednoho proužku sm/w. Počet zmeškaných zápisů je přibližně stejný. V tedy přispívá (2sm/w)(n/q+1). Proto je celkový počet chybění mezipaměti pro algoritmus Strip_DL ≈2(s+1)mn/(wq), když jsou m a n velké.

Připomeňme, že přibližný počet chybění mezipaměti pro algoritmy DL a LS_DL je mn(1+3/w). To je (wq+3q)/(2s+2) krát více než pro Strip_DL.

Algoritmus lineárního prostorového trasování L S D L_T R A C E

Ačkoli algoritmy LS_DL a Strip_DL určují skóre (náklady) optimálního trasování (a tedy optimální editační posloupnosti), které transformuje A do B, tyto algoritmy neukládají dostatek informací pro skutečné určení optimálního trasování. Pro určení optimální stopy pomocí lineárního prostoru přijmeme strategii rozděl a panuj podobnou té, kterou použil Hirschberg pro jednoduchý problém editace řetězců (tj, transpozice nejsou povoleny) a Myers a Miller pro problém zarovnání sekvencí.

Řekneme, že stopa má středový průsečík, jestliže obsahuje dva řádky (u1,v1) a (u2,v2), u1<u2 takové, že v1>n/2 a v2≤n/2 (obr. 4).

Možnosti rozdělení stopy DL. a Bez středového křížení b Se středovým křížením

Nechť T je optimální stopa, která splňuje vlastnosti P2-P4. Pokud T neobsahuje žádný středový průsečík, pak lze jeho linie rozdělit na množiny TL a TR tak, že TL obsahuje všechny linie (u,v)∈T s v≤n/2 a TR obsahuje zbývající linie (obr. 4a). Protože neexistuje žádný středový kříž, mají všechny čáry v TR hodnotu u větší než hodnota u každé čáry v TL. Z vlastností P2-P4 vyplývá, že existuje i, 1≤i≤m takové, že T je sjednocením optimální stopy pro A a B a té pro A a B. Nechť H jsou náklady první optimální stopy a H′ náklady druhé optimální stopy. Vidíme, že když T neobsahuje žádný středový průsečík, jsou náklady T

Když T obsahuje středový průsečík, lze jeho linie rozdělit na 3 množiny, TL, TM a TR, jak ukazuje obr. 4b. Nechť (u1,v1) a (u2,v2) jsou přímky vymezující středový kříž. Všimněte si, že TL obsahuje všechny čáry T s v<v2, TR obsahuje všechny čáry s v>v1 a TM={(u1,v1),(u2,v2)}. Všimněte si také, že všechny řádky v TL mají u<u1 a všechny v TR mají u>u2. Z vlastnosti P1 vyplývá, že TL je optimální stopa pro A a B a TR je optimální stopa pro A a B. Dále, protože (u1,v1) a (u2,v2) jsou vyvážené linie, náklady TM jsou (u2-u1-1)+1+(v1-v2-1). Také A≠A jako jinak, nahrazení středových křížících se přímek (u1,v2) a (u2,v1) vede k nižší nákladové stopě. Z vlastnosti P4 víme, že \(u_{1} = lastA\phantom {\dot {i}\!}\) a \(v_{2} = lastB\phantom {\dot {i}\!}\). Nechť H jsou náklady na optimální stopu pro A a B a nechť H′ jsou náklady na optimální stopu pro A a B. Když tedy T má středový průsečík, jeho náklady jsou

kde pro min{} zkusíme 1≤u1<m a pro každé takové u1 stanovíme v1 jako nejmenší i>n/2, pro které \(b_{i} = a_{u_{1}}\phantom {\dot {i}\!}\). Pro každé u1 zkoumáme všechny jiné znaky než \(\phantom {\dot {i}\!}a_{u_{1}}) v abecedě. Pro každý takový znak c je v2 nastaveno na největší j≤n/2, pro které bj=c, a u2 je nejmenší i>u1, pro které ai=c. Min se tedy bere přes (s-1)m členů.

Nechť Utop a Ttop jsou výsledná pole U a T vypočtená pomocí LS_DL se vstupy B a A a Ubot a Tbot jsou tato pole, když jsou vstupy opačné než B a A. Z těchto polí můžeme snadno určit hodnoty H a H′ potřebné k vyhodnocení rovnic 3 a 4. V případě, že jsou vstupy opačné než vstupy B a A, můžeme z těchto polí snadno určit hodnoty H a H′. Algoritmus LSDL_TRACE (algoritmus 4) poskytuje pseudokód pro náš výpočet optimální stopy v lineárním prostoru. Předpokládá, že LS_DL byl upraven tak, aby vracel obě pole U a T.

Pro časovou složitost vidíme, že na nejvyšší úrovni rekurze voláme LS_DL dvakrát s řetězci A a B o velikosti m, respektive n/2. V případě, že se jedná o rekurzi, je LS_DL volán dvakrát. To trvá nejvýše amn času pro nějakou konstantu a. Čas potřebný k výpočtu rovnic 3 a 4 je O(sn) a může být absorbován do amn použitím vhodně velké konstanty a. Na další úrovni rekurze je LS_DL vyvolán čtyřikrát. Součet délek řetězců A při těchto 4 voláních je nejvýše 2m a řetězec B má délku nejvýše n/4. Čas těchto čtyř volání je tedy nejvýše amn/2. Po zobecnění na zbývající úrovně rekurze vidíme, že algoritmu LSDL_TRACE trvá amn(1+1/2+1/4+1/8+…)<2amn=O(mn) času. Potřebný prostor je stejný jako pro LS_DL (všimněte si, že parametry tohoto algoritmu byly prohozeny). Z časové analýzy vyplývá, že počet ztrát mezipaměti je přibližně dvojnásobný než u LS_DL, je-li vyvolán s řetězci o velikosti m a n. Přibližný počet ztrát mezipaměti pro LSDL_TRACE je tedy 2mn(1+3/w).

Poznamenáváme, že určitého snížení skutečného času běhu lze dosáhnout přepnutím A a B, když je A kratší než B, čímž se zajistí, že kratší řetězec bude rozdělen na každé úrovni rekurze. To nám umožňuje dosáhnout rychlejšího ukončení rekurze.

Algoritmus Strip_TRACE S t r i p_T R A C E

Tento algoritmus se od LSDL_TRACE liší tím, že používá upravenou verzi Strip_DL, nikoliv upravenou verzi LS_DL. Upravená verze Strip_DL vrací pole strip a V vypočtená pomocí Strip_DL. V souladu s tím Strip_TRACE používá Vtop a Vbot místo Ttop a Tbot. Asymptotická časová složitost Strip_TRACE je rovněž O(mn) a zabírá stejné množství místa jako Strip_DL (všimněte si, že parametry Strip_DL jsou prohozeny oproti parametrům Strip_TRACE). Počet ztrát mezipaměti je přibližně dvojnásobný než u Strip_DL.

Vícejádrové algoritmy

V této části popíšeme naše paralelizace algoritmu DL a čtyř jednojádrových algoritmů z předchozí části. Tyto paralelizace předpokládají, že počet procesorů je malý vzhledem k délce řetězce. Pojmenovací konvence, kterou jsme pro paralelní verze přijali, spočívá v přidání předpony PP_ k názvu jednojádrového algoritmu.

Algoritmus P P_D L

Naše paralelní verze algoritmu DL, PP_DL, počítá prvky ve stejném pořadí jako DL. Zahajuje však výpočet řádku dříve, než je dokončen výpočet jeho předchozího řádku. Každému procesoru je přiřazen jedinečný řádek k výpočtu a tento řádek počítá zleva doprava. Nechť p je počet procesorů. Procesor z je zpočátku přiřazen k provádění výpočtu vnější smyčky pro i=z, 1≤i≤p. Procesor z začíná s vhodným časovým zpožděním oproti začátku procesoru z-1, takže data, která potřebuje pro svůj výpočet, již byla vypočtena procesorem z-1. V našem kódu je časová prodleva mezi začátkem výpočtu dvou po sobě jdoucích řádků rovna času potřebnému k výpočtu n/p prvků. Po dokončení svého výpočtu iterace i procesor přejde k iteraci i+p vnější smyčky. Časová složitost PP_DL je O(mn/p).

Algoritmus P P_L S_D L

Ačkoli obecná strategie paralelizace pro PP_LS_DL je stejná jako strategie použitá v PP_DL, je třeba věnovat zvláštní péči zajištění výpočtu shodného s výpočtem LS_DL. Rozdíly ve výsledcích jsou možné, pokud dva nebo více procesorů současně počítá různé řádky H s využitím stejné paměti. K tomu dochází například tehdy, když A=aaabc⋯ a p≥3. Začneme s procesorem i, kterému je přiřazen výpočet řádku i z H, 1≤i≤p. Předpokládejme, že na počátku je U=x a T=y (všimněte si, že x a y jsou adresy v paměti). Vzhledem k příkazu swap(T],U) v LS_DL začne procesor 1 počítat řádek 1 H s využitím paměti začínající na adrese y. Pokud procesor 2 začne s vhodným časovým zpožděním jako v PP_DL, bude počítat řádek 2 H s využitím paměti začínající na adrese x. S dalším zpožděním začne procesor 3 počítat řádek 3 H opět s použitím paměti začínající na adrese y. Nyní oba procesory 1 a 3 používají stejnou paměť pro výpočet různých řádků H, a tak se vystavujeme riziku přepsání hodnot H, které mohou být potřebné pro následné výpočty. Jako další příklad uvažujme A=ababa⋯ a p≥4. Předpokládejme, že U=x a T= na začátku. Procesor 1 začne počítat řádek 1 s využitím paměti y, pak se zpožděním začne procesor 2 počítat řádek 2 s využitím paměti z, pak procesor 3 začne počítat řádek 3 s využitím paměti x. Dále procesor 4 začne počítat řádek 4 s využitím paměti y. V tomto okamžiku procesor 1 počítá řádek 1 s A=a a procesor 4 počítá řádek 4 s A=b a oba procesory používají stejnou paměť y.

Nechť p1 a p2 jsou dva procesory, které používají stejnou paměť k výpočtu řádků r1<r2 z H a že žádný procesor nepoužívá tuto paměť k výpočtu řádku mezi r1 a r2. Ze schématu přiřazení swappingu použitého v LS_DL vyplývá, že p1 počítá řádek \(r_{1} = lastA-1\phantom {\dot {i}\!}\). Hodnoty H v tomto řádku jsou potřebné k výpočtu řádků r1+1 až r2 jako \(\phantom {\dot {i}\!}r_{1} = lastA r_{1} < i \le r_{2}\). Tyto hodnoty nejsou potřeba pro řádky i>r2, protože pro tyto řádky \(\phantom {\dot {i}\!}lastA = r_{2} > r_{1} + 1 = lastA\). Nechť j1 je takové, že \(\phantom {\dot {i}\!}b_{j} = a_{r_{2}} = a_{r_{1} + 1}\). Pak pro j>j1 platí \(\phantom {\dot {i}\!}lastB \ge j_{1}\). Proto pro j>j1 nejsou sloupce 1 až j1-2 řádku r1 potřebné k výpočtu H v řádcích mezi r1 a r2.

Náš paralelní kód používá synchronizační schéma, které je založeno na pozorování z předchozího odstavce, aby se zpozdilo přepisování hodnot, které jsou potřebné pro pozdější výpočty, a zajistil se správný výpočet vzdálenosti DL. Naše synchronizační schéma využívá další pole W, které je inicializováno na hodnotu 1. Předpokládejme, že procesor počítá řádek i z H a že A=a. Když tento procesor poprvé narazí na a v B, řekněme na pozici j1, inkrementuje W. Když narazí na další a, řekněme na pozici j2, inkrementuje W o 1. Když procesor dokončí výpočet řádku i, zbývající pozice W se inkrementují o 1. Procesor přiřazený k výpočtu řádku q H může vypočítat U, pokud W=q. Z našich předchozích pozorování vyplývá, že když W=q, staré hodnoty v paměťových pozicích U mohou být přepsány, protože nejsou potřeba pro budoucí výpočty.

Časová složitost tohoto p-procesorového algoritmu PP_LS_DL závisí na datových sadách, protože zpoždění synchronizace závisí na datech. Očekáváme však, že při zhruba rovnoměrném rozložení znaků v B bude časová náročnost běhu přibližně O(mn/p).

Algoritmus P P_S t r i p_D L

V paralelní verzi PP_Strip_DL Strip_DL je procesoru i zpočátku přiřazen výpočet proužku i, 1≤i≤p. V paralelní verzi PP_Strip_DL je procesor i přiřazen k výpočtu proužku i, 1≤i≤p. Po dokončení aktuálně přiděleného proužku j přejde procesor k výpočtu proužku j+p. Pro účely synchronizace se používá signál pole. Při výpočtu řádku r v jemu přiděleném pásu s musí procesor počkat, dokud signál=s. Signál je nastaven na s procesorem pracujícím na pásu s-1, když byly vypočteny hodnoty nalevo od pásu s potřebné pro výpočet řádku r pásu s a nehrozí, že by výpočty pro řádek r pásu s přepsaly hodnoty V potřebné pro jiné procesory. signál funguje velmi podobně jako W v PP_LS_DL.

Všimněte si, že pokud pracujeme s p proužky, potřebujeme p kopií polí U a T, které používá Strip_DL.

Časová složitost PP_Strip_DL závisí na zpoždění synchronizace a očekává se, že se bude blížit O(mn/p).

Algoritmus P P_D L_T R A C E

Tento algoritmus nejprve použije PP_DL k výpočtu H. Poté jeden procesor provede zpětný výpočet, aby zkonstruoval optimální stopu. Pro rozumné hodnoty p je čas běhu ovládán PP_DL, a proto je složitost PP_DL_TRACE také O(mn/p).

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

V algoritmu LSDL_TRACE (Strip_TRACE) opakovaně rozdělíme problém na dva oddíly a na každý z nich použijeme buď LS_DL (Strip_DL). Paralelní verze PP_LSDL_TRACE (PP_Strip_TRACE) využívá následující strategii paralelizace:

• Každý dílčí problém se řeší pomocí PP_LS_DL (PP_Strip_DL), pokud je počet nezávislých dílčích problémů malý; všech p procesorů je přiřazeno paralelnímu řešení jednoho dílčího problému. Tj. dílčí problémy se řeší postupně.

• p dílčích problémů se řeší paralelně pomocí LS_DL (Strip_DL) k sériovému řešení každého dílčího problému, když je počet nezávislých dílčích problémů velký,

Časová složitost PP_LSDL_TRACE a PP_Strip_TRACE je O(mn/p).