algorithm - 特定の数のグループからのレーベンシュタイン距離

Question

私の入力は3つの数字です-数字と範囲sの最初bと最後は。です。タスクは、範囲内のすべての数値間の最小レーベンシュタイン距離を見つけることです。距離を最小化する数を見つける必要はありません。最小距離で十分です。e0 <= s,b,e <= 10^1000s[b, e]

標準のC++型はそのような大きな数値を処理しないため、明らかに数値を文字列として読み取る必要があります。おそらく巨大な範囲内のすべての数値のレーベンシュタイン距離を計算することは現実的ではありません。

何か案は？

Answer 1

[2013年10月8日編集：DPアルゴリズムで考慮されるいくつかのケースは、実際には考慮する必要はありませんが、それらを考慮することは不正確さにはつながりません:)]

以下では、O（N ^ 2）時間を要するアルゴリズムについて説明します。ここで、Nは、b、e、またはsのいずれかの最大桁数です。これらの数値はすべて1000桁に制限されているため、これは最大で数百万の基本操作を意味し、最新のCPUでは数ミリ秒かかります。

sがn桁であるとします。以下では、「間」は「包括的」を意味します。「エンドポイントを除く」という意味の場合は、「厳密に間」と言います。インデックスは1ベースです。x [i]はxのi番目の桁を意味するため、たとえばx[1]はその最初の桁です。

問題を分割する

最初に行うことは、問題を一連のサブ問題に分割することです。このサブ問題では、各bとeの桁数が同じです。eの桁数がsよりk>=0多いと仮定します。問題を、k+1個のサブ問題に分割します。たとえば、b=5およびe=14032の場合、次のサブ問題を作成します。

• b = 5、e = 9
• b = 10、e = 99
• b = 100、e = 999
• b = 1000、e = 9999
• b = 10000、e = 14032

これらのサブ問題のそれぞれを解決し、最小限の解決策をとることができます。

簡単なケース：真ん中

簡単なケースは真ん中のケースです。eがbよりもk>=1桁多い場合は常に、k-1のサブ問題（上記の3など）が発生します。ここで、bは10の累乗であり、eは10の次の累乗から1を引いたものです。bが10^mであるとします。 。1から9までの任意の数字を選択し、続いて0から9までの任意のm桁を選択すると、b <= x<=eの範囲の数値xが生成されることに注意してください。さらに、この範囲でこの方法で生成できない数値はありません。s（または実際には0で始まらない任意の長さ-n桁の文字列）と任意の間の最小レーベンシュタイン距離10 ^ m <= x <= 10 ^（m + 1）-1の範囲の数値xは必然的にabs（m + 1-n）です。これは、m + 1> = nの場合、最初のn桁を単純に選択できるためです。 xをsと同じにし、余りを削除します。m+ 1 <nの場合は、最初のm + 1をsと同じにするように選択し、余りを挿入します。

実際、これらすべてのサブ問題を1回の定数時間演算で処理できます。最小の「簡単な」サブ問題のb = 10 ^ mで、最大の「簡単な」サブ問題のb = 10 ^ uの場合、 sおよびこれらの範囲のいずれかの数値は、n <mの場合はmn、n> uの場合はnu、それ以外の場合は0です。

ハードケース：終わり

難しいのは、bとeがそれぞれb = 10^mとe=10 ^（m + 1）-1の形式に制限されていない場合です。マスター問題は、次のように最大2つのサブ問題を生成する可能性があります。2つの「終了」（上部の例のように、bとeの桁数が異なるマスター問題の結果）または1つのサブ問題（つまり、マスター問題自体。bとeはすでに同じ桁数であるため、細分化する必要はまったくありませんでした）。以前の問題の分割により、サブ問題のbとeの桁数が同じであると想定できることに注意してください。これをmと呼びます。

スーパーレーベンシュタイン！

私たちが行うことは、与えられた数字列とb <= x<=eの範囲内の任意の数xとの間の最小レーベンシュタイン距離を計算するレーベンシュタインDP行列のバリエーションを設計することです。この追加された「パワー」にもかかわらず、アルゴリズムはO（n ^ 2）時間で実行されます:)

まず、bとeの桁数が同じで、b！= eの場合、左側にある同じ桁の数q> = 0と、それに続く大きい桁で構成されている必要があることに注意してください。 bよりもeで。ここで、ランダムな数字列xを生成するための次の手順を検討してください。

1. xをbの最初のq桁に設定します。
2. b[i]とe[i]の間にランダムに選択された数字dをxに追加します。
3. d == b [i]の場合、下限を「ハグ」します。
   • q + 1からmまでのiの場合：
     • b [i] == 9の場合、b[i]を追加します。 [2013年10月8日編集：e[i]がb[i]より大きくなるようにqを選択し、9より大きい数字がないため、実際にはこれは発生しません！]
     • それ以外の場合は、コインを裏返します。
       • ヘッド：b[i]を追加します。
       • テール：ランダムに選択された数字d> b [i]を追加してから、6に進みます。
   • 止まる。
4. それ以外の場合、d == e [i]の場合、上限を「ハグ」します。
   • q + 1からmまでのiの場合：
     • e [i] == 0の場合、e[i]を追加します。 [2013年10月8日編集：b[i]がe[i]よりも小さくなるようにqを選択し、0よりも小さい桁がないため、実際にはこれは発生しません！]
     • それ以外の場合は、コインを裏返します。
       • ヘッド：e[i]を追加します。
       • テール：ランダムに選択された数字d <e [i]を追加してから、6に進みます。
   • 止まる。
5. それ以外の場合（dが厳密にb[i]とe[i]の間にある場合）、ステップ6に進みます。
6. ランダムに選択された数字をm桁になるまでxに追加し続けます。

基本的な考え方は、含める必要のあるすべての数字を含めた後、下限の数字を好きなだけ「抱きしめる」か、上限の数字を好きなだけ「抱きしめる」ことができるということです。 「ハグ」をやめることにしたときは、その後、任意の数字を選択できます。適切なランダムな選択の場合、この手順では、b <= x<=eとなるすべての数xのみが生成されます。

それぞれ長さnとmの2つの文字列sとxの間の「通常の」レーベンシュタイン距離計算では、（0、0）から（n、m）までの長方形のグリッドがあり、各グリッドポイント（i、j）に接頭辞s[1..i]と接頭辞x[1..j]の間のレーベンシュタイン距離を記録します。（i、j）のスコアは、ボトムアップ動的計画法を使用して、（i-1、j）、（i、j-1）、および（i-1、j-1）のスコアから計算されます。これを適応させて、xを可能な文字列のセットの1つとして扱う（具体的には、bとeの間の数字に対応する数字列）特定の文字列の代わりに、グリッドポイントごとに1つではなく2つのスコアを記録する必要があります。位置jは下限をハグするために選択され、位置jは上限をハグするために選択されたと想定しています。3番目の可能性（上記のステップ5）は、実際にはDP行列にスペースを必要としません。これは、「簡単」の場合と非常によく似た、残りの入力文字列全体の最小レーベンシュタイン距離をすぐに計算できるためです。 "最初のセクションのサブ問題。

スーパーレーベンシュタインDP再帰

グリッドポイント（i、j）v（i、j）で全体的な最小スコアを呼び出します。文字aとbが異なる場合はdiff（a、b）= 1とし、それ以外の場合は0とします。文字aがb..cの範囲内にある場合はinrange（a、b..c）を1とし、それ以外の場合は0とします。計算は次のとおりです。

# The best Lev distance overall between s[1..i] and x[1..j]
v(i, j) = min(hb(i, j), he(i, j))

# The best Lev distance between s[1..i] and x[1..j] obtainable by
# continuing to hug the lower bound
hb(i, j) = min(hb(i-1, j)+1, hb(i, j-1)+1, hb(i-1, j-1)+diff(s[i], b[j]))

# The best Lev distance between s[1..i] and x[1..j] obtainable by
# continuing to hug the upper bound
he(i, j) = min(he(i-1, j)+1, he(i, j-1)+1, he(i-1, j-1)+diff(s[i], e[j]))

v（i、j）が計算されている時点で、「ハグをやめる」ことを選択した結果、つまりb[j]とe[jの間に厳密にある数字を選択した結果のレーベンシュタイン距離も計算します。 ]（j == qの場合）または（j！= qの場合）はb[j]より上またはe[j]より下のいずれかであり、その後、xの接尾辞がsの接尾辞とできるだけ一致するように数字を自由に選択します：

# The best Lev distance possible between the ENTIRE STRINGS s and x, given that
# we choose to stop hugging at the jth digit of x, and have optimally aligned
# the first i digits of s to these j digits
sh(i, j) = if j >= q then shc(i, j)+abs(n-i-m+j)
           else infinity

shc(i, j) = if j == q then
              min(hb(i, j-1)+1, hb(i-1, j-1)+inrange(s[i], (b[j]+1)..(e[j]-1)))
            else
              min(hb(i, j-1)+1, hb(i-1, j-1)+inrange(s[i], (b[j]+1)..9),
                  he(i, j-1)+1, he(i-1, j-1)+inrange(s[i], (0..(e[j]-1)))

shc（i、j）の式では、「下向き」の動きを考慮する必要はありません。このような動きには、xの数字の選択が含まれないためです。

全体的な最小レーベンシュタイン距離は、すべての0 <= i<=nおよび0<=j <= mについて、v（n、m）およびsh（i、j）の最小値です。

複雑

Nを、s、b、またはeのいずれかの最大桁数とします。元の問題は、線形時間で最大1セットの簡単な問題に分割できます。これらの問題はまとめて解決にO（1）時間を要し、2つの難しいサブ問題はそれぞれスーパーレーベンシュタインアルゴリズムを使用して解決にO（N ^ 2）時間を要します。したがって、全体として、問題はO（N ^ 2）時間、つまり桁数の2乗に比例する時間で解決できます。

Answer 2

計算を高速化するための最初のアイデア（|e-b|大きすぎない場合は機能します）：

• 質問：と比較した後、と比較sした場合、レーベンシュタイン距離はどのくらい変化しますか？nn+1

• 回答：多すぎないでください！

s = 12007と2つの連続した動的計画法の表を見てみましょうn

n = 12296

0 1 2 3 4 5 
1 0 1 2 3 4 
2 1 0 1 2 3 
3 2 1 1 2 3 
4 3 2 2 2 3 
5 4 3 3 3 3 

と

n = 12297

0 1 2 3 4 5 
1 0 1 2 3 4 
2 1 0 1 2 3 
3 2 1 1 2 3 
4 3 2 2 2 3 
5 4 3 3 3 2 

ご覧のとおり、最後の列を除いて同じ桁であるため、最後の列のみが変更されます。nn+1

との編集距離の動的計画法テーブルがs = 12001ありn = 12296、すでにのテーブルがn = 12297ある場合は、最後の列を更新する必要があります。

明らかに、その場合n = 12299、n+1 = 12300前のテーブルの最後の3列を更新する必要があります。ただし、これは100回の反復ごとに1回だけ発生します。

一般的に、あなたはしなければなりません

• 反復ごとに最後の列を更新します（つまり、セルの長さ）
• 10回の反復ごとに1回、最後から2番目も更新します
• 100回の反復ごとに1回、最後から3番目も更新します

だからみましょうL = length(s)とD = e-b。sまず、との間の編集距離を計算しますb。[b,e]次に、区間内のすべての整数をループする際の最小レーベンシュタイン距離を見つけることができます。それらがいくつDかあるので、実行時間は約です：

今から

アルゴリズムがあります