Damerau-Levenshtein距離を用いた文字列補正

シングルコア・アルゴリズム

このセクションでは、DL距離を用いた文字列補正の線形空間のシングルコア・アルゴリズム4つを開発します。 4つともO(mn)時間で実行される。 最初の2つ（LS_DLとStrip_DL）は最適なトレースのスコアHmnのみを計算し、キャッシュ効率に違いがある。 最後の 2 つ (LSDL_TRACE および Strip_TRACE) は、最適なトレースを計算します。

線形空間アルゴリズム L S_D L

s をアルファベットのサイズとしましょう。 LS_DL アルゴリズムでは、DL で使用した配列 H の代わりに、1 次元配列 U と 2 次元配列 T を使用します。この 2 つの配列は、定数 s に対して O((s+1)n) = O(n) の容量を必要とします。 AとBに必要なメモリを加えると、sが定数のとき、空間複雑度はO(s min{m,n}+m+n) = O(m+n)

アルゴリズムDLと同様に、Hij値は行ごとに計算される。 1次元配列Uは、行iが計算されているときにアルゴリズムDLで計算されたHの値を保存するために使用されます。 文字cの最後の行をHとすると、TはHのw-1行目である。 LS_DLの正しさは、アルゴリズムDLの正しさから導かれる。 swap(T],U)は、2つの1次元配列の内容ではなく、そのポインタを交換するため、O(1)の時間がかかることに注意してください。 LS_DLのキャッシュミス数は、nが適当な大きさであれば、両者のデータアクセスパターンが同じであるため、DLのそれと同じになります。 しかし、より小さなインスタンスでは、LS_DLの方がはるかに優れたキャッシュ動作を示します。 例えば、LS_DLは使用するメモリが少ないため、DLではなくLS_DLの全データを格納するのに十分なLLCキャッシュを持つことができます（O(sn) vs O(mn))．

キャッシュ効率の良い線形空間アルゴリズム S t r i p_D L

(s+1)n が LLC キャッシュのサイズより大きい場合、n より小さいいくつかの q に対して、幅 q のストリップによって Hij を計算することにより、アルゴリズム LS_DL に対してキャッシュミスを削減できます (最後のストリップは q より小さい幅であってもかまいません)。 これを図 3 に示す。 アルゴリズムLS_DLを用いると、ストリップは0、1、…の順で計算される。 しかし、ストリップの幅が n ではなく q であるため、LS_DL で T と U が必要とする領域は (s+1)q に減少します。q を十分に小さく選ぶことで、LS_DL で使用する T と U の配列のブロックが、一度持ち込まれたキャッシュから退避しないようにすることができ ます。 つまり、TとUの各エントリーが1ワードで済むとすると、キャッシュサイズをlwとしたとき、q<lw/(s+1) となるわけです。 T と U に加えて、キャッシュは A、B、および 1 つのストリップから次のストリップにデータを渡すために必要なその他の配列の一部を保持する必要があることに注意してください。

ストリップによるHの計算

あるストリップから次にデータを渡すために、サイズmと2次元s＊m配列Vを追加の1次元配列ストリップを使用します。 配列stripは、strip内の右端の列について計算されたHの値を記録します。 V は、(a) 現在計算中のストリップの左側にあり、(b) c=B である H の行 i の右端の列 j の H 値を与える。

Strip_DLの疑似コードをアルゴリズム 3 に示す。 わかりやすくするために、この疑似コードは2つのストリップ配列（18行目と30行目）と2つのV配列（24行目と32行目）を使用しています。 一組の配列は前のストリップのために計算されたデータをフェッチするために使用され、もう一組は次のストリップに渡されるデータ用に使用される。

Strip_DLの時間と複雑さは、qが定数なので、それぞれ、O(mn) と O((s+1)m+(s+1)q+n) = O(sm+sq+n) = O(sm+n) となります。 m>n のとき、メモリを節約するために A と B を切り替えることができるので、空間の複雑さは定数 s に対して O(s min{m,n}+m+n) = O(m+n) になります。

キャッシュミスを分析するとき、U と T がキャッシュに合うように q を選択することに注意します。 LRU 置換規則により、アルゴリズム Strip_DL の実行中に U または T のブロックが退避されることはないという妥当な仮定を立てます。 その結果、U および T に起因するキャッシュ・ミスの総数 は m および n に依存しないため、解析では無視することができま す。 stripとVの初期化により、それぞれm/wと(s+1)m/wの読み出しアクセスが発生する。 書き込みアクセス数は、読み出しアクセス数とほぼ同じである。 各Stripの計算では，配列Stripをインデックスの昇順でアクセスします． このため、キャッシュミスの回数は初期化時と（ほぼ）同じになります。 したがって、ストリップによるキャッシュミスの総数は約（2m/w）（n/q+1）である。 Vについては、現在のストリップを計算するとき、Vの任意の行の要素はインデックスの非減少順序で（すなわち、左から右へ）アクセスされ、アルファベットの各文字について、最も最近読み取られた値のみをキャッシュに保持する必要がある（すなわち、最大s個の値を保持する必要がある）ことに留意する必要がある。 同じ文字に対する新しい値がアクセスされたときのみ、Vの値がキャッシュから追い出されると仮定すると、1つのストリップを計算するときのVからのリードミスの総数はsm/wである。 ライトミスの回数もほぼ同じである。 つまり、Vの寄与は（2sm/w）（n/q+1）である。 したがって、アルゴリズム Strip_DL のキャッシュ ミスの総数は、m および n が大きい場合、≈2(s+1)mn/(wq) です。

アルゴリズム DL および LS_DL の近似キャッシュ ミス数は mn(1+3/w) であることを思い出してください。 これは、Strip_DL の場合の (wq+3q)/(2s+2) 倍です。

The linear-space trace algorithm L S D L_T R A C E

アルゴリズム LS_DL と Strip_DL は、A から B へ変換する最適トレースのスコア (従って、最適編集シーケンスのコスト) を決定しますが、これらのアルゴリズムは実際に最適トレースを決定するのに十分な情報を保存していません。 線形空間を用いた最適トレースを決定するために、Hirschbergが単純な文字列編集問題で用いたものと同様の分割統治戦略（すなわち

トレースが 2 つの線 (u1,v1) と (u2,v2) を含み、u1<u2 が v1>n/2 および v2≤n/2 であれば中心交差があると言う (図 4)。

DL trace splitting opportunities. a 中央交差なし b 中央交差あり

性質P2～P4を満たす最適トレースをTとする。 Tが中心交差を含まない場合、その線は、TLがv≦n/2の線（u,v）∈Tをすべて含み、TRが残りの線を含むように、集合TLとTRに分割される（図4a）。 中心交差がないため、TRのすべての線はTLのすべての線のu値より大きいu値を持つ。 前者の最適トレースのコストをH、後者の最適トレースのコストをH′とすると、特性P2〜P4から、TがAとBの最適トレースの和となるようなi，1≦i≦mが存在することがわかる。 Tに中心交差がないとき、Tのコストは

Tに中心交差があるとき、その線は図4bのようにTL、TM、TRという3組に分割されることが分かる。 (u1,v1)と(u2,v2)を中央の交差を定義する線とする。 TLはTの線のうちv<v2 のものをすべて含み、TRはv>v1 のものをすべて含み、TM={ (u1,v1),(u2,v2)} となることに注意されたい。 また、TLの全ての線はu<u1 を持ち、TRの全ての線はu>u2 を持つことに注意されたい。 さらに、(u1,v1)と(u2,v2)は平衡線なので、TMのコストは(u2-u1-1)+1+(v1-v2-1)となる。 また、そうでない場合のA≠Aとして、中心交差線を(u1,v2)と(u2,v1)に置き換えると、より低コストのトレースとなる。 特性P4から、 \(u_{1} = lastAphantom {dot {i} }} と \(v_{2} = lastBphantom {dot {i} }} が得られることが分かる。 AとBの最適トレースのコストをHとすると、H′はAとBの最適トレースのコストである。 したがって、Tが中心交差を持つ場合のコストは

ここで、min{}については、1≦u1<m を試し、そのようなu1それぞれについて、v1を、 \(b_{i} = a_{u_{1}}phantom {dot {i}} n/2 の最小値としています！)が成り立つ。}\). 各u1について、アルファベットのうち \(\phantom {\dot {i}!}a_{u_{1}}) 以外の文字を全て調べます。 そのような文字cごとに、bj=cとなる最大のj≦n/2をv2とし、ai=cとなる最小のi>u1 をu2 とする。

入力BとAでLS_DLが計算した最終的なUとTの配列をUtopとTtop、入力がBとAの逆の場合のこれらの配列をUbotとTbotとします。これらの配列から、式3と4の評価に必要なHとH′値を容易に決定することができます。 アルゴリズムLSDL_TRACE (Algorithm 4)は、最適トレースの線形空間計算のための擬似コードである。 LS_DL が配列 U と T の両方を返すように変更されたと仮定します。

時間の複雑さについては、再帰のトップ レベルで、それぞれサイズ m と n/2 の文字列 A および B で LS_DL を 2 回呼び出すことがわかります。 式3、4の計算時間はO(sn)であり、適切に大きな定数aを用いることでamnに吸収される可能性があります。 この4回の呼び出しにおけるA文字列の長さの和は最大2mであり、B文字列の長さは最大n/4である。 したがって、これら4回の呼び出しにかかる時間は最大でamn/2である。 再帰の残りのレベルに一般化すると、アルゴリズム LSDL_TRACE は amn(1+1/2+1/4+1/8+…)<2amn=O(mn) 時間を要することがわかります。 必要な空間はLS_DLと同じです（このアルゴリズムのパラメータが入れ替わっていることに注意してください）。 時間分析から、サイズ m と n の文字列で呼び出された場合、キャッシュ ミス数は LS_DL の場合の約 2 倍であることがわかります。したがって、LSDL_TRACE のキャッシュ ミス数は 2mn(1+3/w) です。

実際の実行時間は、AがBより短いときにAとBを切り替えることにより、短い文字列が再帰の各レベルで確実に分割されていることがわかります。

The strip trace algorithm S t r i p_T R A C E

このアルゴリズムは LSDL_TRACE と異なり、LS_DL の修正バージョンではなく、Strip_DL の修正バージョンを使用する点である。 修正版のStrip_DLは、Strip_DLによって計算された配列stripとVを返します。 これに対応して、Strip_TRACEはTtopとTbotの代わりにVtopとVbotを使用します。 Strip_TRACEの漸近的時間複雑性もO(mn)で、Strip_DLと同量のスペースを必要とします（Strip_DLのパラメータがStrip_TRACEのパラメータと相対的に入れ替わっていることに注意してください）。

マルチコア アルゴリズム

このセクションでは、アルゴリズム DL と前セクションの 4 つのシングルコア アルゴリズムの並列化について説明します。 これらの並列化は、プロセッサの数が文字列の長さに対して少ないと仮定している。

アルゴリズム P P_D L

私たちのアルゴリズム DL の並列バージョン PP_DL は、DL と同じ順序で要素を計算します。 しかし、直前の行の計算が完了する前に、その行の計算を開始します。 各プロセッサには、計算する一意の行が割り当てられ、この行を左から右へ計算する。 プロセッサの数をpとする。 プロセッサzは最初i=z, 1≦i≦pの外周ループ計算を行うように割り当てられる。 プロセッサzはプロセッサz-1の開始に対して適当な時間差をおいて開始し、計算に必要なデータはすでにプロセッサz-1によって計算されているようにする。 このコードでは、連続する2行の計算開始のタイムラグは、n/p個の要素を計算するために必要な時間です。 繰り返しi回の計算が終了すると、プロセッサは外側ループの繰り返しi+p回に進みます。 PP_DL の時間複雑度は O(mn/p) です。

アルゴリズム P P_L S_D L

一般的な PP_LS_DL の並列化戦略は PP_DL と同じですが、LS_DL と同一の計算を保証するために特別な注意が必要です。 2つ以上のプロセッサが同じメモリを使用してHの異なる行を同時に計算する場合、結果に差異が生じる可能性があります。 例えば、A=aaabc⋯とp≥3があるとき、この現象が起こります。 Hの行iを計算するプロセッサiを1≤i≤pとするところから始めます。 最初はU=x, T=yであるとします(x, yはメモリ上のアドレスであることに注意)． LS_DLのswap(T],U)文により、プロセッサ1は、アドレスyから始まる メモリを使ってHの1行目の計算を始めます。プロセッサ2がPP_DLのように適当な時間差で開始すると、 アドレスxから始まるメモリを使ってHの2行目の計算を行うことになります。 このとき、プロセッサ1とプロセッサ3の両方が同じメモリを使用してHの異なる行を計算するため、後続の計算で必要となる可能性のあるHの値が上書きされる危険性があります。 別の例として、A=ababa⋯とp≥4を考えてみましょう。 最初はU=x,T=であったとします． プロセッサ1はメモリyを用いて行1の計算を始め、遅れてプロセッサ2が メモリzを用いて行2の計算を始め、プロセッサ3がメモリxを用いて行3の計 算を始めます。

ここで、p1 と p2 を、H の行 r1<r2 を計算するために同じメモリを使用し、r1 と r2 の間の行を計算するためにこのメモリを使っているプロセッサがない 2 つのプロセッサとしましょう。 LS_DLで使用されているスワッピング割り当て方式から、p1は行୧⃛(๑⃙⃘◡̈๑⃙⃘)୨⃛を計算中であることが分かる。 この行のH値は、行r1+1～r2を計算するのに必要な値で、 \(㊞Pantom {Threshold {i}dot {I} !}r_{1} = lastA r_{1} とする。 < i \le r_{2}\). i>r2 の行については、これらの値は必要ありません。 > r_{1}の場合。 + 1 = lastA) である。 j1をsufficientとすると、 \dot {i}}b_{j} = a_{r_{2}} = a_{r_{1} + 1}} が成立します。 すると、j>j1 に対して、 \({phantom {dot {i}}!}lastB \ge j_{1}}) が得られます。 したがって、j>j1 については、r1 と r2 の間の行の H を計算するために行 r1 の列 1 から j1-2 は必要ありません。

この並列コードでは、前項の考察に基づいて、後の計算に必要な値の上書きを遅らせ、正しい DL 距離計算を保証する同期方式が使用されています。 この同期方式では、1に初期化された別の配列Wを用いる。あるプロセッサがHの行iを計算しており、A=aであるとする。 プロセッサが行iの計算を終了すると、Wの残りの位置が1ずつ増加する。Hの行qの計算に割り当てられたプロセッサは、W=qの場合、Uを計算することができる。

この p-プロセッサ・アルゴリズム PP_LS_DL の時間複雑性は、同期遅延がデータ依存であるため、データセットに依存します。

アルゴリズム P P_S t r i p_D L

Strip_DLの並列バージョン PP_Strip_DL では、プロセッサ i は最初にストリップ i, 1≤i≤p を計算するように割り当てられます。 現在割り当てられているストリップjが終了すると、そのプロセッサはストリップj+pの計算に進む。 同期をとるために、アレイ信号が使用されます。 signalは、strip sのr行の計算に必要なstrip sの左側の値が計算され、strip sのr行の計算が他のプロセッサが必要とするV値を上書きする恐れがないとき、strip s-1で動作するプロセッサによってsに設定されます。

p個のストリップで作業する場合、Strip_DLで使用される配列UとTのp個のコピーが必要なことに注意してください。

PP_Strip_DLの時間複雑度は同期遅延に依存し、近似O（mn/p）であると予想されます。

アルゴリズム P P_D L_T R A C E

このアルゴリズムは最初にHを計算するのにPP_DLを使用し、次に、最適トレースを構築するのに単一プロセッサがトレーサックを実行するのです。 p の妥当な値では、実行時間は PP_DL によって支配されるので、PP_DL_TRACE の複雑性も O(mn/p) です。

アルゴリズム P P_L S D L_T R A C E と P P_S t r i p_T R A C E

LSDL_TRACE（Strip_TRACE）で、問題を 2 分割してそれぞれの分割に対し LS_DL (Strip_DL) を適用するのを繰り返すのですが、このとき、LSDL_DL は 2 分割のままです。 並列版PP_LSDL_TRACE（PP_Strip_TRACE）では、以下のような並列化戦略を採用しています。

• 独立した副問題の数が少ない場合、各副問題はPP_LS_DL (PP_Strip_DL) を用いて解きます。p個のプロセッサはすべて、単一の副問題の並列解に割り当てられます。

• 独立したサブ問題の数が多い場合、LS_DL（Strip_DL）を用いて各サブ問題をシリアルに解き、PP_LSDL_TRACEおよびPP_Strip_TRACEの時間計算量はO（mn/p）です。