algorithm - テキストの追加と削除のリストを最適化する

Question

次のように、テキストの追加と削除の位置を含むリストがあります。

     Type   Position   Text/Length
1.   +      2          ab          // 'ab' was added at position 2
2.   +      1          cde         // 'cde' was added at position 1
3.   -      4          1           // a character was deleted at position 4

より明確にするために、これはこれらの操作が行うことです：

    1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
    ---------------------------------
    t | e | x | t |   |   |   |   |  
1.  t | a | b | e | x | t |   |   |  
2.  c | d | e | t | a | b | e | x | t
3.  c | d | e | a | b | e | x | t |

アクションの数は、次のように減らすことができます。

     Type   Position   Text/Length
1.   -      1          1           // 't' was deleted at position 1
2.   +      1          cdeab       // 'cdeab' was added at position 1

または：

     Type   Position   Text/Length
1.   +      1          cdeab       // 'cdeab' was added at position 1
2.   -      6          1           // 't' was deleted at position 6

これらのアクションはデータベースに保存され、これを最適化するには、同じ結果を得るために実行するアクションの数を減らすにはどうすればよいですか? O(n*n) より速い方法はありますか?

これらのアクションは時系列であることに注意してください。アクションの順序を変更すると、別の結果が得られます。

score 3 · Accepted Answer

解決策ではなく、いくつかの考えがあります：

ルール 1: 2 つの連続した操作で範囲が重複していない場合、それらを入れ替えることができます (位置は調整されます)。
ルール 2: 同じ位置での 2 つの連続した挿入または削除を結合できます
ルール 3: インサートの後に、インサートに完全に含まれる除去が続く場合、それらを結合することができます

最短のソリューションのための単純なアルゴリズムは見当たりません。ただし、ルール 1 + 2 を使用したヒューリスティックなアプローチは次のようになります。

操作を「上」に移動しない限り
- ルール 1 に違反します
- 削除する前にインサートを移動します
- その前任者よりも地位が低い
連続する挿入/削除を同じ位置で結合する

サンプルに適用すると、これは次のことを意味します。

 + 2 ab
 + 1 cde
 - 4 1

ルール 1 (2x):

+ 2 ab
- 1 1   // position adjusted by -3
+ 1 cde

.

- 1 1  
+ 1 ab  // position adjusted
+ 1 cde

ルール 2:

- 1 1
+ 1 cdeab // watch correct order!

プリミティブな実装は O(N*N) になります。基本的には、追加の停止条件を持つバブルソートです。位置を調整する必要があるため、標準のアルゴリズムはここでは役に立たないため、その複雑さを打ち負かすことについてはわかりません。

ただし、特に改善できる可能性があります-たとえば、「完全な並べ替え」は必要ありません

score 2 · Accepted Answer

すべての変更を適用する前後のドキュメントを表すバイナリツリーを作成します。各ノードは、元のテキストまたは挿入/削除されたテキストのいずれかを表します。後者の種類のノードには、削除する元のテキストの量 (おそらく 0) と挿入するテキストの文字列 (おそらく空) の両方が含まれます。

最初、ツリーには「0 to end: original text」というノードが 1 つだけあります。すべての変更を適用して、可能な限り変更をマージします。次に、ツリーを最初から最後までたどって、最終的な編集セットを発行します。これにより、最適な結果が得られることが保証されます。

インサートの適用: ツリー内の適切なポイントを見つけます。挿入されたテキストの途中または隣接している場合は、そのノードの text-to-insert 文字列を変更するだけです。それ以外の場合は、ノードを追加します。
削除の適用: ツリー内の開始点と終了点を見つけます。挿入とは異なり、削除は既存のノードの範囲全体をカバーする場合があります。それに応じて開始ノードと終了ノードを変更し、その間のすべてのノードを強制終了します。完了したら、隣接する「挿入/削除されたテキスト」ノードがあるかどうかを確認します。もしそうなら、それらに参加してください。

唯一の注意点は、変更を加えるたびにツリー全体を更新せずに、ツリー内のポイントを確実に見つけられるようにすることです。これは、各ノードで、そのサブツリーによって表されるテキストの合計量をキャッシュすることによって行われます。その後、変更を加えると、変更したノードのすぐ上のノードでこれらのキャッシュされた値を更新するだけで済みます。

これは、バランスの取れたツリーを実装し、挿入されたテキストにロープを使用することを気にする場合、すべての入力に対して厳密に O(n log n) に見えます。ツリー全体のアイデアを捨ててベクトルと文字列を使用すると、O(n ² ) になりますが、実際には問題なく動作する可能性があります。

作業例。このアルゴリズムがあなたの例にどのように適用されるかを、段階的に示します。複雑なアスキーアートを行う代わりに、ツリーを横向きにして、ノードを順番に表示し、インデントによってツリー構造を表示します。私はそれが明確であることを願っています。

初期状態：

*: orig

上で、各サブツリーにある量のテキストをキャッシュすると言いました。ここでは、バイト数に * を付けただけです。このノードにはドキュメント全体が含まれており、その長さがわからないからです。0x4000000000000000L など、十分に大きな数値を使用できます。

2 番目の位置に「ab」を挿入した後:

    2: orig, 2 bytes
*: insert "ab", delete nothing
    *: orig, all the rest

位置 1 に「cde」を挿入した後:

        1: orig, 1 byte
    5: insert "cde", delete nothing
        1: orig, 1 byte
*: insert "ab", delete nothing
    *: orig, all the rest

次のステップは、位置 4 の文字を削除することです。ここで一時停止して、ツリー内の位置 4 を見つける方法を確認します。

ルートから始めます。最初の子ノードを見てください。そのサブツリーには 5 文字が含まれています。したがって、位置 4 はそこにある必要があります。そのノードに移動します。最初の子ノードを見てください。今回は1キャラのみです。そこにはありません。この編集には 3 文字が含まれているため、ここにもありません。その直後です。2 番目の子ノードに移動します。(このアルゴリズムは約 12 行のコードです。)

4 番目の文字を 1 文字削除すると、次のようになります。

    4: orig, 1 byte
        3: insert "cde", delete nothing
*: insert "ab", delete nothing
    *: orig, all the rest

...そして、隣接する 2 つの挿入ノードに気付き、それらをマージします。(2 つの隣接するノードが与えられた場合、一方は常にツリー階層内で他方の上にあることに注意してください。データをその上位ノードにマージしてから、下位ノードを削除し、その間にキャッシュされたサブツリーのサイズを更新します。)

    1: orig, 1 byte
*: insert "cdeab", delete nothing
    *: orig, all the rest

score 1 · Accepted Answer

ソースコード管理システムで使用される「差分」ツールは、あるソースコードを別のソースコードに変換するために必要な最小限の編集を生成するアルゴリズムを使用します。それらを調査する価値があるかもしれません。それらのほとんどは（最終的には）このアルゴリズムに基づいていると思いますが、私がこの主題について読んでからしばらく経ちます。

score 1 · Accepted Answer

これは、平均してO(n²) よりもかなり高速に実行できると思います(高速な分析ができないように入力を設計できる可能性があります)。連続した追加または削除をセットと見なすことができます。一度に 1 つの操作を分析できますが、いくつかの条件付き変換を行う必要があります。

追加が追加または一連の追加に続く場合、
- (1 つまたは複数の) 前の追加に触れる: 次に、これらの追加を統合できます。
- 触れないでください：注文できます（位置を調整する必要があります）
追加または一連の追加の後に削除が続く場合、
- アディションから文字のみを削除: その後、アディションを変更できます (アディションが分割されない限り)。
- 追加のセットからではない文字のみを削除します。その後、削除を追加のセットの前の位置に移動し、おそらく追加を結合できます。その後、現在の追加セットの前の削除のセットを、その前の追加に適用する必要がある場合があります。
- 両方を行う: 次に、最初にそれを 2 つ (またはそれ以上) の削除に分割し、それぞれの方法を適用できます。
削除が削除または一連の削除に続く場合、次のことができます。
- (1 つまたは複数の) 前の削除に触れる: 次に、これらの削除を統合できます。
- 触れないでください：注文できます（位置を調整する必要があります
- いずれにせよ、以前の追加で新しく形成された削除の分析を適用する必要があります
追加が削除の後に続く場合、この時点で変換は必要ありません

これは最初のラフ案にすぎません。たとえば、すべての削除を常に適用する方が簡単または効率的であり、その結果、常に 1 セットの削除の後に 1 セットの追加が続くようになります。

score 0 · Accepted Answer

簡単にするために、文字azだけがテキストに表示されると仮定しましょう。

リストAを値a[i]= i for i = 1からNで初期化します（Nの大きさを自分で理解できます）。

Aですべての操作を実行（シミュレート）します。この後、Aを分析して、必要な操作を見つけます。

最初に、Aで欠落している番号を見つけて、必要な削除操作を見つけます（これらは連続した値のグループを形成し、1つのグループは1つの削除操作を表します）。

この後、連続する文字のシーケンスを見つけることにより、必要な挿入操作を見つけることができます（1つのシーケンスは1つの挿入操作です）。

あなたの例では：

init A：

1 2 3 4 5 6 7 8 9 10

ステップ1（+：2：ab）：

1 ab 2 3 4 5 6 7 8 9 10

ステップ2（+：1：cde）：

cde 1 ab 2 3 4 5 6 7 8 9 10

ステップ3（-：4：1）：

cdeab 2 3 4 5 6 7 8 9 10

次に、欠落している番号を検索して削除を見つけます。この例では、1つの番号（つまり番号1）のみが欠落しているため、1つの削除のみが必要であるため、1つの削除操作があります。削除操作。たとえば、1、2、3、5、6、10がすべて欠落している番号の場合、3つの削除操作があります：-：1：3、-：2：2、-：5：1。すべての削除操作ですべてのインデックスが減少します。現在の削除操作のインデックスを計算するには、以前の削除操作の合計を保存する必要があります。）

次に、文字シーケンスを検索して挿入操作を見つけます。この例では、シーケンスは1つだけです。インデックス1にcdeabがあるため、挿入操作は1つです：+：1：cdeab

これが十分に明確であることを願っています。

score 0 · Accepted Answer

アクションの数を減らす方法: アルゴリズムのアプローチにより、アクションの並べ替えを試みることができます。私は、ソートした後だと思います：

（スヴァンテとピーターチェンが示した方法で）隣接する行動が参加できる可能性が高まります。
これにより、実行する必要のあるアクションの数が最小限になる可能性がありますか?

次の「position-number」は、テキストの挿入または削除位置を表します。

隣接する 2 つのアクションを交換できると仮定すると (この 2 つのアクションの位置番号とテキスト/長さのプロパティを調整することで)、アクションリストを好きな順序にすることができます。昇順の位置番号を使用して、削除アクションをアクションリストの先頭に配置することをお勧めします。削除アクションの後、追加アクションは昇順の位置番号でソートされます。

次の例は、隣接するアクションを交換できると考える理由を示しているはずです。

次のアクションを交換します。

  1. + 2 aaa -> taaaext
  2. - 3 1   -> taaext

1 つのアクションに譲ります:

  1. + 2 aa  -> taaext

次のアクションを交換します。

  1. + 3 aaa -> teaaaxt
  2. + 1 bb  -> bbteaaaxt

次のようになります:

  1. + 1 bb  -> bbtext
  2. + 5 aaa -> bbteaaaxt

次のアクションを交換します。

  1. + 1 bb  -> bbtext
  2. - 2 2   -> bext

次のようになります:

  1. - 1 1   -> ext
  2. + 1 b   -> bext

最初の例が示すように、スワップによって削除が削除される場合があります。これは有益な副作用です。これは、すべての削除を前に移動することをお勧めする理由でもあります。

何かを忘れず、あらゆる状況を考慮したことを願っています。

algorithm - テキストの追加と削除のリストを最適化する

6 に答える 6

Related

Reference