Stringkorrekció a Damerau-Levenshtein távolság segítségével

Egymagos algoritmusok

Ebben a fejezetben négy lineáris térbeli, egymagos algoritmust dolgozunk ki a DL távolságot használó sztringkorrekcióra. Mind a négy O(mn) idő alatt fut. Az első kettő (LS_DL és Strip_DL) csak az optimális nyomvonal Hmn pontszámát számítja ki; a cache-hatékonyságukban különböznek. Az utolsó kettő (LSDL_TRACE és Strip_TRACE) egy optimális nyomvonalat számol.

A lineáris térbeli algoritmus L S_D L

Legyen s az ábécé mérete. A DL-ben használt H tömb helyett az LS_DL algoritmus egy egydimenziós U és egy kétdimenziós T tömböt használ. E két tömb helyigénye O((s+1)n) = O(n) konstans s esetén. Ha m<n, akkor felcserélhetjük A-t és B-t a memóriaigény csökkentése érdekében. Az A és B memóriaszükségletét összeadva a helybonyolultság O(s min{m,n}+m+n) = O(m+n), ha s konstans.

A DL algoritmushoz hasonlóan a Hij értékeket soronként számítjuk. Az egydimenziós U tömböt a DL algoritmus által kiszámított H értékek mentésére használjuk, amikor az i sor kiszámítása folyamatban van. Legyen H a c karakterhez utoljára kiszámított sor. Ekkor T a H w-1 sora. A 2. algoritmus az LS_DL pszeudokódját adja. Helyessége a DL algoritmus helyességéből következik. Vegyük észre, hogy a swap(T],U) O(1) időt vesz igénybe, mivel nem a tömbök tartalmát, hanem 2 egydimenziós tömbre mutatót cserélünk. Az LS_DL cache-hiányának száma megegyezik a DL-ével, ha n megfelelően nagy, mivel mindkettőnél ugyanaz az adathozzáférési minta érvényesül. Kisebb példányok esetén azonban az LS_DL sokkal jobb cache-viselkedést mutat. Például, mivel sokkal kevesebb memóriát használ, lehet, hogy az LLC cache-je elegendő az összes adat tárolására az LS_DL-ben, de a DL-ben nem (O(sn) vs. O(mn)).

A cache-hatékony lineáris térbeli algoritmus S t r i p_D L

Ha (s+1)n nagyobb, mint az LLC cache mérete, akkor az LS_DL algoritmushoz képest úgy csökkenthetjük a cache-kihagyásokat, hogy a Hij-t q szélességű csíkokkal számoljuk ki, valamilyen n-nél kisebb q-ra (az utolsó csík szélessége lehet q-nál kisebb). Ez a 3. ábrán látható. A sávok kiszámítása 0, 1,… sorrendben történik az LS_DL algoritmus segítségével. A T és U által az LS_DL-ben igényelt hely azonban (s+1)q-ra csökken, mivel a csík szélessége n helyett q. A q elég kicsire választásával biztosíthatjuk, hogy az LS_DL által használt T és U tömbök blokkjai nem kerülnek ki a gyorsítótárból, miután behoztuk őket. Tehát, ha a T és U minden egyes bejegyzése 1 szót vesz igénybe, akkor ha a gyorsítótár mérete lw, akkor q<lw/(s+1). Megjegyezzük, hogy a T és U mellett a gyorsítótárnak A, B és más tömbök részhalmazait is tárolnia kell, amelyek az adatok egyik sávból a másikba történő továbbításához szükségesek.

H számítása csíkok segítségével

Az adatok egyik csíkból a következőbe történő továbbításához egy további m méretű egydimenziós tömbcsíkot és egy kétdimenziós s∗m V tömböt használunk. A tömbszalag rögzíti a H-nak a szalag jobb szélső oszlopára kiszámított értékeit. V a H i sorának legjobb oldali j oszlopában lévő H értékét adja meg, amely (a) az éppen számítás alatt állótól balra lévő csíkban van, és (b) c=B.

A Strip_DL pszeudokódját a 3. algoritmus tartalmazza. Az egyértelműség kedvéért ez az álkód két csíktáblát (18. és 30. sor) és két V-táblát (24. és 32. sor) használ. A tömbök egyik csoportja az előző csíkhoz kiszámított adatok lekérésére szolgál, a másik csoport pedig a következő csíkra átadandó adatokra. A tényleges megvalósításban egyetlen strip tömböt és egyetlen V tömböt használunk, amely az előző stripből kapott értékeket felülírja a következő stripnek átadandó értékekkel.

A Strip_DL ideje és bonyolultsága O(mn), illetve O((s+1)m+(s+1)q+n) = O(sm+sq+n) = O(sm+n), mivel q egy konstans. Ha m>n, akkor A-t és B-t felcserélhetjük, hogy memóriát takarítsunk meg, és így a térkomplexitás O(s min{m,n}+m+n) = O(m+n) lesz konstans s esetén.

A cache miss elemzésénél megjegyezzük, hogy q-t úgy választjuk, hogy U és T beférjen a cache-be. Azt az ésszerű feltételezést tesszük, hogy az LRU csere szabálya nem okoz U vagy T blokk kilakoltatását a Strip_DL algoritmus futása során. Ennek eredményeképpen az U és T miatti gyorsítótár-kihagyások teljes száma független az m-től és az n-től, így az elemzés során figyelmen kívül hagyható. A Strip és a V inicializálása m/w, illetve (s+1)m/w olvasási hozzáférést eredményez. Az írási hozzáférések száma megközelítőleg megegyezik az olvasási hozzáférések számával. Az egyes szalagok számítása az index szerint növekvő sorrendben lép be a tömbszalagokba. Ez (megközelítőleg) ugyanannyi gyorsítótár-kihagyást eredményez, mint az inicializálási fázisban. Ennélfogva a csíkok miatti gyorsítótár-kihagyások teljes száma megközelítőleg (2m/w)(n/q+1). V esetében megjegyezzük, hogy az aktuális csíkozás kiszámításakor a V bármely sorában lévő elemekhez az index szerint nem csökkenő sorrendben (azaz balról jobbra) férünk hozzá, és hogy az ábécé minden egyes karakteréhez csak a legutóbb olvasott értéket kell a gyorsítótárban megtartanunk (azaz legfeljebb s értéket kell megtartanunk). Feltételezve, hogy egy V érték csak akkor kerül ki a gyorsítótárból, ha ugyanannak a karakternek az új értékéhez hozzáférünk, a V értékből egyetlen csík kiszámításakor az olvasási hibák teljes száma sm/w lesz. Az írási hibák száma megközelítőleg ugyanennyi. A V tehát (2sm/w)(n/q+1) értékkel járul hozzá. Ezért a Strip_DL algoritmus cache-kihagyásainak teljes száma ≈2(s+1)mn/(wq), ha m és n nagy.

Memlékezzünk arra, hogy a DL és LS_DL algoritmusok cache-kihagyásainak közelítő száma mn(1+3/w). Ez (wq+3q)/(2s+2)-szerese a Strip_DL-hez képest.

A lineáris térbeli nyomvonal algoritmus L S D L_T R A C E

Noha az LS_DL és Strip_DL algoritmusok meghatározzák az A-t B-be transzformáló optimális nyomvonal (és így az optimális szerkesztési szekvencia) pontszámát (költségét), ezek az algoritmusok nem mentenek elég információt az optimális nyomvonal tényleges meghatározásához. Az optimális nyomvonal lineáris teret használó meghatározásához egy oszd meg és uralkodj stratégiát alkalmazunk, hasonlóan ahhoz, amelyet Hirschberg használt az egyszerű karakterlánc-szerkesztési problémára (azaz, a transzpozíciók nem megengedettek), valamint Myers és Miller a szekvencia-illesztési problémára.

Azt mondjuk, hogy egy nyomvonalnak van egy középponti keresztezése, ha két olyan (u1,v1) és (u2,v2) vonalat tartalmaz, u1<u2, hogy v1>n/2 és v2≤n/2 (4. ábra).

DL nyomvonal felosztási lehetőségek. a Központkeresztezés nélkül b Központkeresztezéssel

Legyen T egy optimális nyomvonal, amely kielégíti a P2-P4 tulajdonságokat. Ha T nem tartalmaz középponti keresztezést, akkor vonalait TL és TR halmazokra lehet felosztani úgy, hogy TL tartalmazza az összes (u,v)∈T vonalat v≤n/2-vel, TR pedig a többi vonalat (4a. ábra). Mivel nincs középponti kereszteződés, a TR-ben lévő összes vonal u értéke nagyobb, mint a TL-ben lévő összes vonal u értéke. A P2-P4 tulajdonságokból következik, hogy van olyan i, 1≤i≤m, hogy T az A és B optimális nyomvonal és az A és B optimális nyomvonal uniója. Legyen H az előbbi optimális nyomvonal költsége, H′ pedig az utóbbi optimális nyomvonal költsége. Láthatjuk, hogy ha T-ben nincs középponti kereszteződés, akkor T költsége

Ha T-ben van középponti kereszteződés, akkor a vonalai 3 halmazra, TL, TM és TR-re oszthatók, ahogy a 4b. ábrán látható. Legyenek (u1,v1) és (u2,v2) a középponti kereszteződést meghatározó vonalak. Vegyük észre, hogy a TL tartalmazza a T összes olyan vonalát, amelynek v<v2, a TR tartalmazza az összes olyan vonalat, amelynek v>v1, és a TM={(u1,v1),(u2,v2)}. Vegyük észre azt is, hogy a TL-ben minden sor u<u1, a TR-ben pedig minden sor u>u2. A P1 tulajdonságból következik, hogy a TL egy optimális nyomvonal A és B számára, a TR pedig egy optimális nyomvonal A és B számára. Továbbá, mivel (u1,v1) és (u2,v2) kiegyensúlyozott vonalak, a TM költsége (u2-u1-1)+1+(v1-v2-1). Továbbá, A≠A mint egyébként, a középpontot keresztező vonalak (u1,v2) és (u2,v1) helyettesítése alacsonyabb költségű nyomvonalat eredményez. A P4 tulajdonságból tudjuk, hogy \(u_{1} = lastA\phantom {\dot {i}\!}\) és \(v_{2} = lastB\phantom {\dot {i}\!}\). Legyen H az A és B optimális nyomvonalának költsége, és legyen H′ az A és B optimális nyomvonalának költsége. Tehát, ha T-nek van egy középponti keresztezése, akkor a költsége

ahol a min{} esetében 1≤u1<m próbálkozunk, és minden ilyen u1 esetében v1-et a legkisebb i>n/2-re állítjuk, amelyre \(b_{i} = a_{u_{1}}\phantom {\dot {i}\!}\). Minden u1 esetében megvizsgáljuk az \(\phantom {\dot {i}\!}a_{u_{1}}}\) ábécén kívüli összes karaktert. Minden ilyen c karakterhez v2 az a legnagyobb j≤n/2, amelyre bj=c, és u2 a legkisebb i>u1, amelyre ai=c. A min tehát az (s-1)m kifejezésekre vonatkozik.

Legyen Utop és Ttop az LS_DL által B és A bemenet esetén kiszámított végső U és T tömb, Ubot és Tbot pedig ezek a tömbök, ha a bemenet B és A fordítottja. Ezekből a tömbökből könnyen meghatározhatjuk a 3. és 4. egyenlet kiértékeléséhez szükséges H és H′ értékeket. Az LSDL_TRACE algoritmus (4. algoritmus) adja meg az optimális nyomvonal lineáris térbeli kiszámításának pszeudokódját. Feltételezi, hogy az LS_DL-t úgy módosítottuk, hogy az U és T tömböket is visszaadja.

Az időbonyolultságot tekintve azt látjuk, hogy a rekurzió legfelső szintjén kétszer hívjuk meg az LS_DL-t m és n/2 méretű A és B karakterláncokkal. Ez legfeljebb amn időt vesz igénybe valamilyen a konstans esetén. A 3. és 4. egyenlet kiszámításához szükséges idő O(sn), és egy megfelelően nagy a konstans használatával elnyelhető amn-ben. A rekurzió következő szintjén az LS_DL-t 4-szer hívjuk meg. Az A karakterláncok hosszának összege ezen 4 meghívás során legfeljebb 2m, a B karakterlánc hossza pedig legfeljebb n/4 lehet. Tehát ennek a négy meghívásnak az ideje legfeljebb amn/2. A rekurzió többi szintjére általánosítva azt látjuk, hogy az LSDL_TRACE algoritmus amn(1+1/2+1/4+1/8+…)<2amn=O(mn) időt vesz igénybe. A helyigény ugyanaz, mint az LS_DL esetében (megjegyzendő, hogy ennek az algoritmusnak a paraméterei kicserélődtek). Az időelemzésből következik, hogy a cache-kihagyások száma körülbelül kétszerese az LS_DL-ének, ha m és n méretű karakterláncokkal hívjuk meg. Így az LSDL_TRACE közelítő cache-kihagyásainak száma 2mn(1+3/w).

Megjegyezzük, hogy a tényleges futási idő némileg csökkenthető, ha A és B felcseréljük, ha A rövidebb, mint B, így biztosítva, hogy a rövidebb karakterláncot minden rekurziós szinten felezzük. Ez lehetővé teszi, hogy a rekurzió gyorsabban befejeződjön.

A Strip Trace algoritmus S t r i p_T R A C E

Ez az algoritmus abban különbözik az LSDL_TRACE-től, hogy az LS_DL módosított változata helyett a Strip_DL módosított változatát használja. A Strip_DL módosított változata a Strip_DL által kiszámított strip és V tömböket adja vissza. Ennek megfelelően a Strip_TRACE a Ttop és Tbot helyett a Vtop és Vbot értékeket használja. A Strip_TRACE aszimptotikus időbonyolultsága szintén O(mn), és ugyanannyi helyet foglal, mint a Strip_DL (megjegyzendő, hogy a Strip_DL paraméterei a Strip_TRACE paramétereihez képest fel vannak cserélve). A cache-kihagyások száma körülbelül kétszerese a Strip_DL-nek.

Multi-core algoritmusok

Ebben a szakaszban a DL algoritmus és az előző szakasz négy egymagos algoritmusának párhuzamosításait ismertetjük. Ezek a párhuzamosítások feltételezik, hogy a processzorok száma kicsi a karakterlánc hosszához képest. A párhuzamos változatok elnevezési konvenciója az, hogy az egymagos algoritmus nevéhez előtagként hozzáadjuk a PP_ szót.

A P P_D L algoritmus

A DL algoritmus párhuzamos változata, a PP_DL, ugyanabban a sorrendben számítja ki az elemeket, mint a DL. Azonban egy sor számítását azelőtt kezdi meg, hogy az azt megelőző sor számítása befejeződött volna. Minden processzor egy egyedi sort kap számításra, és ezt a sort balról jobbra haladva számítja ki. Legyen p a processzorok száma. A z processzor kezdetben a külső hurok számításának elvégzésére van kijelölve i=z, 1≤i≤p időtartamra. A z processzor a z-1 processzor indulásához képest megfelelő időeltolódással kezd, hogy a számításhoz szükséges adatokat a z-1 processzor már kiszámította. A kódunkban a két egymást követő sor számításának kezdete közötti időeltolódás az n/p elem kiszámításához szükséges idő. Az i. iterációs számítás befejeztével a processzor a külső ciklus i+p. iterációjára lép. A PP_DL időbonyolultsága O(mn/p).

A P P_L S_D L algoritmus

Míg a PP_LS_DL általános párhuzamosítási stratégiája megegyezik a PP_DL esetében alkalmazottal, az LS_DL-ével azonos számítás biztosításához további gondosságra van szükség. Az eredmények eltérése akkor lehetséges, ha két vagy több processzor egyidejűleg a H különböző sorait számítja ki ugyanazt a memóriát használva. Ez történik például, ha A=aaabc⋯ és p≥3. Kezdjük az i processzorral, amely a H i sorának kiszámítására van kijelölve, 1≤i≤p. Tegyük fel, hogy kezdetben U=x és T=y (megjegyezzük, hogy x és y címek a memóriában). Az LS_DL-ben szereplő swap(T],U) utasítás miatt az 1. processzor a H 1. sorának kiszámítását az y címen kezdődő memóriából kezdi. Ha a 2. processzor megfelelő időeltolódással kezd, mint a PP_DL-ben, akkor a H 2. sorát az x címen kezdődő memóriából fogja kiszámítani. További késleltetéssel a 3. processzor elkezdi kiszámítani a H 3. sorát, ismét az y címen kezdődő memóriát használva. Most mind az 1., mind a 3. processzor ugyanazt a memóriát használja a H különböző sorainak kiszámítására, és így fennáll a veszélye annak, hogy a későbbi számításokhoz szükséges H értékeket felülírjuk. Egy másik példaként tekintsük A=ababa⋯ és p≥4. Tegyük fel, hogy U=x és T= kezdetben. Az 1. processzor elkezdi kiszámítani az 1. sort az y memória segítségével, majd késleltetve a 2. processzor elkezdi kiszámítani a 2. sort a z memória segítségével, majd a 3. processzor elkezdi kiszámítani a 3. sort az x memória segítségével. Ezután a 4. processzor elkezdi kiszámítani a 4. sort az y memória segítségével. Ekkor az 1. processzor az 1. sort A=a, a 4. processzor pedig a 4. sort A=b értékkel számítja, és mindkét processzor ugyanazt a sormemóriát y használja.

Legyen p1 és p2 két processzor, amelyek ugyanazt a memóriát használják H r1<r2 sorainak kiszámítására, és egyik processzor sem használja ezt a memóriát az r1 és r2 közötti sor kiszámítására. Az LS_DL-ben használt swapping hozzárendelési sémából következik, hogy p1 a \(r_{1} = lastA-1\phantom {\dot {i}\!}\) sort számítja. Az ebben a sorban lévő H értékek szükségesek az r1+1-től r2-ig terjedő sorok kiszámításához, mint \(\phantom {\dot {i}\!}r_{1} = lastA r_{1} < i \le r_{2}\). Ezekre az értékekre nincs szükség az i>r2 sorok esetében, mivel ezeknél a soroknál \(\phantom {\dot {\dot {i}\!}lastA = r_{2} > r_{1} + 1 = lastA\). Legyen j1 olyan, hogy \(\fantom {\dot {i}\!}b_{j} = a_{r_{2}} = a_{r_{1} + 1}\). Akkor j>j1 esetén \(\phantom {\dot {i}\!}lastB \ge j_{1}\). Ezért j>j1 esetében az r1 sor 1-től j1-2-ig terjedő oszlopai nem szükségesek az r1 és r2 közötti sorok H-jának kiszámításához.

Párhuzamos kódunk az előző bekezdés megfigyeléseire épülő szinkronizációs sémát használ, hogy késleltesse a későbbi számításokhoz szükséges értékek felülírását és biztosítsa a DL távolság helyes kiszámítását. Szinkronizációs sémánk egy másik W tömböt használ, amelyet 1-re inicializálunk. Tegyük fel, hogy egy processzor a H i sorát számítja, és hogy A=a. Amikor ez a processzor először találkozik egy a-val a B-ben, mondjuk a j1 pozícióban, növeli a W-t. Amikor a következő a-val találkozik, mondjuk a j2 pozícióban, növeli a W-t 1-gyel. Amikor a processzor befejezi az i sor számítását, a W többi pozícióját növeljük 1-gyel. A H q sorának kiszámítására kijelölt processzor kiszámíthatja U-t, ha W=q. Korábbi megfigyeléseinkből következik, hogy ha W=q, akkor az U memóriapozíciókban lévő régi értékeket felül lehet írni, mivel ezekre nincs szükség a későbbi számításokhoz.

Ez a p-processzoros PP_LS_DL algoritmus időbonyolultsága az adathalmazoktól függ, mivel a szinkronizációs késleltetés adatfüggő. Mi azonban megközelítőleg O(mn/p) futási idejű teljesítményt várunk, ha a B karakterek nagyjából egyenletes eloszlásúak.

A P P P_S t r i p_D L

A Strip_DL PP_Strip_DL párhuzamos változatában az i processzor kezdetben az i csík kiszámítására van kijelölve, 1≤i≤p. Az aktuálisan kijelölt j szalag befejezése után a processzor folytatja a j+p szalag kiszámítását. A szinkronizáláshoz egy tömbjelzést használunk. Az s-1 csíkon dolgozó processzor akkor állítja a signal-t s-re, ha az s csík r sorának kiszámításához szükséges, az s csíktól balra lévő értékek már kiszámításra kerültek, és nem áll fenn annak a veszélye, hogy az s csík r sorának számításai felülírják a többi processzor által szükséges V értékeket. signal nagyon hasonlóan működik, mint a W a PP_LS_DL-ben.

Megjegyezzük, hogy ha p csíkon dolgozunk, akkor a Strip_DL által használt U és T tömbök p példányára van szükségünk.

A PP_Strip_DL időbonyolultsága a szinkronizációs késleltetéstől függ, és várhatóan megközelíti az O(mn/p) értéket.

A P P_D L_T R A C E

Az algoritmus először a PP_DL segítségével kiszámítja H-t. Ezután egyetlen processzor visszavezetést végez az optimális nyomvonal felépítéséhez. A p ésszerű értékei esetén a futási időt a PP_DL uralja, így a PP_DL_TRACE komplexitása is O(mn/p).

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

Az LSDL_TRACE (Strip_TRACE) algoritmusokban a problémát ismételten kettéosztjuk, és minden partícióra vagy LS_DL-t (Strip_DL) alkalmazunk. A PP_LSDL_TRACE (PP_Strip_TRACE) párhuzamos változata a következő párhuzamosítási stratégiát alkalmazza:

• Minden részproblémát a PP_LS_DL (PP_Strip_DL) segítségével oldunk meg, ha a független részproblémák száma kicsi; minden p processzort egyetlen részprobléma párhuzamos megoldására rendelünk. Vagyis a részproblémák megoldása sorban történik.

• p részproblémát oldunk meg párhuzamosan LS_DL (Strip_DL) használatával, hogy minden részproblémát sorban oldjunk meg, ha a független részproblémák száma nagy,

A PP_LSDL_TRACE és a PP_Strip_TRACE időbonyolultsága O(mn/p).