それは主に、テキスト変更の使用に依存します。シーケンスに挿入と削除の両方が含まれる場合、挿入されたシンボルの一部が後で削除されている可能性があるため、各挿入の詳細を知ることは理論的に不可能です。したがって、本当に必要な結果を選択する必要があります。
- 目的によっては、挿入された記号の一部を「?」のままにしておく必要がある場合でも、変更の正確な順序を知る必要があります。
- 他の目的のために、変更が行われた正確な順序ではなく、新しいテキストが古いテキストとどのように異なるかを正確に知る必要があります。
これらの結果のそれぞれを達成するためのテクニックを紹介します。過去に両方の手法を使用したことがあるので、効果的であることはわかっています。
正確な順序を取得するには
これは、履歴または元に戻すログを実装している場合、または特定のアクションを検索している場合に適しています。
これらの用途については、説明したプロセスがおそらく最適ですが、可能な変更が1つあります。「未知のシンボルと実際のシンボルの間のマッピングを見つける」代わりに、スキャンを順方向に実行して各「削除」のテキストを見つけてから実行します各「挿入」のテキストを見つけるために後方に。
言い換えると：
最初のテキストから始めて、順番に変更を処理します。挿入ごとに、「?」を挿入します。シンボル。削除ごとに、指定された数の記号を削除し、削除されたテキストとして記録します。
最終的なテキストから始めて、逆の順序で変更を処理します。deleteごとに、「?」を挿入します。シンボル。insertごとに、指定された数の記号を削除し、挿入されたテキストとして記録します。
これが完了すると、すべての「挿入」および「削除」の変更エントリには、私たちの知る限り、関連付けられたテキストが含まれ、挿入されてすぐに削除されたテキストはすべて「?」になります。シンボル。
違いを得るには
これは、リビジョンのマーキングまたはバージョンの比較に適しています。
これらの用途では、単純にテキスト変更情報を使用して、変更が見つかる可能性のある一連の整数範囲を計算し、次に標準の diff アルゴリズムを使用して実際の変更を見つけます。これは、増分変更の処理において非常に効率的である傾向がありますが、それでも最良の更新が得られます。
これは、元の段落とほぼ同じ置換段落を貼り付ける場合に特に便利です。テキスト変更情報を使用すると、段落全体が新しいことを示しますが、diff (つまり、この手法) を使用すると、実際に変更されたシンボル ランのみがマークされます。違う。
変更範囲を計算するコードは単純です。変更を 4 つの整数 (oldstart、oldend、newstart、newend) で表します。各変更を実行します。
- changestart が newstart の前にある場合、newstart を changestart に減らし、oldstart を同じ量だけ減らします。
- changeend が newend の後にある場合、newend を changeend に増やし、oldend を同じ量だけ増やします。
これが完了したら、古いドキュメントから範囲 [oldstart, oldend] を抽出し、新しいドキュメントから範囲 [newstart, newend] を抽出し、標準の diff アルゴリズムを使用してそれらを比較します。