天天看點
傳回

Myers‘Diff之貪婪算法

Myers’Diff

Myers‘Diff之貪婪算法

前言

寫這篇文章已經拖了很久了，因為一直在準備後續的 ​​Myers‘Diff之線性空間細化​​​ 。最初不知道是什麼時候發現 ​

​DiffUtil​

​​ 對比清單 ​

​item​

​​ 資料進行局部重新整理，​

​git​

​ 檔案對比都用到了這個算法。上個月剛好再一次看到了就想深入了解一下。但發現發現國内的部落格和文章，對這個算法的講述内容比較少，每篇文章都講述了作者自己認為重要的内容，是以有一個點搞不懂的話沒法整體性的進行了解。剛開始我自己就有一個點沒想清楚想了好幾天，我覺得程式員不能怕算法，書讀百遍其義自現，閱讀算法代碼也是如此，平時多思考偶爾的一點靈光出現會減少你死磕算法浪費的時間。

文章目錄

  • ​​Myers'Diff​​
  • ​​前言​​
  • ​​Myer差分算法​​
  • ​​定義​​
  • ​​示例​​
  • ​​貪婪算法​​
  • ​​外循環次數​​
  • ​​内循環的次數​​
  • ​​舉例說明（d=3）​​
  • ​​算法實作​​

Myer差分算法

舉一個最常見的例子，我們使用 ​

​git​

​​ 進行送出時，通常會檢視這次送出做了哪些改動，這裡我們先簡單定義一下什麼是 ​

​diff​

​​ ：​

​diff​

​​ 就是目标文本和源文本之間的差別，也就是将源文本變成目标文本所需要的操作。​

​Myers算法​

​​ 由 ​

​Eugene W.Myers​

​​ 在 ​

​1986​

​​ 年發表在 ​

​《 Algorithmica》​

​​ 雜志上。的一篇​​論文​​中提出，是一個能在大部分情況産生最短的直覺的diff 的一個算法。

Myers‘Diff之貪婪算法

尋找最短的直覺的diff 是一個非常模糊的問題，首先，我們需要把這個問題抽象為一個具體的數學問題，然後再來尋找算法解決。

定義

  • File A and File B
The diff algorithm takes two files as input. The first, usually older, one is file A, and the second one is file B. The algorithm generates instructions to turn file A into file B.(diff算法将兩個檔案作為輸入。第一個通常是較舊的檔案是檔案A，第二個是檔案B。算法生成指令以将檔案A轉換為檔案B。)
  • Shortest Edit Script ( SES )
The algorithm finds the Shortest Edit Script that converts file A into file B. The SES contains only two types of commands: deletions from file A and insertions in file B.(該算法找到将檔案A轉換為檔案B的最短編輯腳本。SES僅包含兩種類型的指令：從檔案A删除和在檔案B中插入。)
  • Longest Common Subsequence ( LCS )
Finding the SES is equivalent to finding the Longest Common Subsequence of the two files. The LCS is the longest list of characters that can be generated from both files by removing some characters. The LCS is distinct from the Longest Common Substring, which has to be contiguous.(查找SES等同于找到兩個檔案的最長公共子序列。 LCS是可以通過删除某些字元從兩個檔案生成的最長字元清單。 LCS與最長公共子字元串不同，後者必須是連續的。)

示例

本文使用與本文相同的示例。檔案​

​A​

​​包含 ​

​ABCABBA​

​​，檔案​

​B​

​​包含​

​CBABAC​

​​。這些被表示為兩個字元數組：​

​A []​

​​和​

​B []​

​​。

​​

​A []​

​​的長度為​

​N​

​​，​

​B []​

​​的長度為​

​M​

​。

我們就可以求解從​

​A數組​

​​變成​

​B數組​

​​的問題，轉換成為求解從​

​A字元串​

​​變成​

​B字元串​

​的問題（将抽象問題具現）。

Myers‘Diff之貪婪算法

​

​數組A​

​​沿​

​x軸​

​​放在頂部。​

​數組B​

​​沿​

​y軸​

​向下放置。

PS:文章中的圖都是由​​DiffTutorial​​軟體制作而成，該應用程式是一種學習輔助工具。它顯示算法各個階段的圖形表示。

解決方案：從​

​左上角（0，0）​

​​到​

​右下角（7，6）​

​​的最短路徑。 您始終可以水準或垂直移動一個字元。水準​

​（右）​

​​移動表示從​

​檔案A​

​​中删除，垂直​

​（向下）​

​​移動表示在​

​檔案B​

​​中插入。如果存在比對的字元，則還可以對角移動，以比對結束。 解決方案是包含最多對角線的迹線。 ​

​LCS​

​​是軌迹中的對角線，​

​SES​

​​是軌迹中的水準和垂直移動。例如，​

​LCS​

​​的長度為4個字元，​

​SES​

​的長度為5個差異。

snake: 一條snake代表走一步。例如從(0,0)->(0,1) / (0,0)->(1,0) / (0,1)->(0,2)->(2,4) 這分别為三條snake，走對角線不計入步數。

k line: k lines表示長的對角線，其中每個k = x - y。假設一個點m(m,n),那麼它所在的k line值為m - n。

d contour: 每條有效路徑(能從(0,0)到(m,n)的路徑都稱為有效路徑)的步數。形象點，一條path有多個snake組成，這裡d contours表示snake的個數。

貪婪算法

該算法是疊代的。它計算連續 ​

​d​

​​ 的每條 ​

​k​

​ 線上最遠的到達路徑。當路徑到達右下角時，将找到解決方案。

這裡面有很重要的幾點：
  1. 路徑的終點必然在​

    ​k​

     ​​線上。疊代進行，是以​

    ​k​

     ​​線的上一步操作是​

    ​k+1​

     ​​向下移動或者​

    ​k-1​

     ​向右移動；
  2. 計算連續的​

    ​d​

     ​​每條​

    ​k​

     ​​線上最遠的到達路徑（偶數​

    ​d​

     ​​的端點在偶數​

    ​k​

     ​線，奇數類似）；
  3. 路徑到達右下角結束；
其中1和2都是在論文中進行了證明~！
Myers‘Diff之貪婪算法
  • ​

    ​k line​

     ​：棕色線是k的奇數值的k條線。黃線是k的偶數值的k線。
  • ​

    ​snake​

     ​：深藍色的線條是蛇。紅蛇顯示溶液痕迹。
  • ​

    ​d contours​

     ​：淡藍色的線是差異輪廓。例如，标記為“ 2”的直線上的三個端點全部具有2個水準或垂直移動。

外循環次數

從（x、y）組成的矩形​

​左上角​

​​，到​

​右下角​

​​。最長的路徑莫過于所有對角線都不經過。也就是隻走​

​X​

​​和​

​Y​

​​的長度即​

​最大長度=N+M​

​​。

​​

​for ( int d = 0 ; d <= N + M ; d++ )​

​

内循環的次數

在此循環内，我們必須為每條​

​k線​

​​找到最遠的到達路徑。對于給定的​

​d​

​​，隻能到達的​

​k線​

​​位于​

​[-d .. + d]​

​​範圍内。當所有移動都向下時，​

​k = -d​

​​ 是可能的；當所有移動都在右側時，​

​k = + d​

​​ 是可能的。

​​

​for ( int k = -d ; k <= d ; k += 2 )​

​​ 看到這裡也許就有人産生疑問，為什麼是​

​k+=2​

​。

這塊有一個優化，文章前面說過​

​偶數​

 ​​d​

​的端點在偶數​

 ​​k​

​線，奇數類似​

​​。

解釋：移動奇數步長（前進或者後退都行）最終位置一定在奇數的​​

​k線​

 ​​上，偶數步長的最終位置一定在偶數的​

​k線​

​​上。

PS：這裡讓我糾結了好長時間，最後一下幾點思考讓我想的更加清楚：

  1. 從​

    ​零​

     ​​開始一步一步在​

    ​k線​

     ​​上進行移動，一定是從​

    ​零​

     ​開始。
  2. 這裡的計算不是偶數加偶數得到的還是偶數，奇數加奇數得到的數是奇數或者偶數（這裡是計算多個​

    ​+1或-1​

     ​）。
  3. 無論偶數還是奇數​

    ​+1或-1​

     ​​之後都會改變自己的奇偶性，是以​

    ​d​

     ​​次操作之後的奇偶性由​

    ​d​

     ​​的奇偶進行決定。由因為起點為偶數​

    ​零​

     ​​，是以說​

    ​偶數​

     ​​d​

    ​的端點在偶數​

     ​​k​

    ​線，奇數類似​

     ​。

舉例說明（d=3）

從​

​d = 3​

​​的示例進行研究，這意味着​

​k​

​​的取值範圍是​

​[-3，-1，1，3]​

​​。為了幫助您，我将示例中的​

​snake​

​的端點轉錄到下表中：

Myers‘Diff之貪婪算法

k = -3：這種情況下，隻有當k = -2，d = 2時，向下移動一步(k = -4, d = 2這種情況不存在)。是以，我們可以這麼來走，從(2,4)點開始向下走到(2,5),由于(2,5)和(3,6)之間存在一個對角線，可以走到(3,6)。是以着整個snake是：(2,4) -> (2,5) -> (3,6)。

k = -1：當k = -1時，有兩種情況需要來讨論：分别是k = 0，d = 2向下走；k = -2 ，d = 2向右走。

  • 當k = 0，d = 2時，是(2,2)點。是以當從(2,2)點向下走一步，到達(2,3),由于(2,3)沒有對角線連接配接，是以整個snake是：(2,2) -> (2,3)。
  • 當k = -2 ，d = 2時，是(2,4)點。是以當從(2,4)點向右走一步，到達(3,4)，由于(3,4)與(4,5)存在對角線，是以整個snake是：(2,4) -> (3,4) -> (4,5)。

在整個過程中，存在兩條snake，我們選擇是沿着k line走的最遠的snake，是以選擇第二條snake。

k = 1：當k = 1時，存在兩種可能性，分别是從k = 0向右走一步，或者k = 2向下走一步，我們分别來讨論一下。

  • 當k = 0，d = 2時，是(2,2)點。是以當從(2,2)向右走一步，到達(3,2),由于(3,2)與(5,4)存在對角線，是以整個snake是：(2,2) ->(3,2) ->(5,4)。
  • 當k = 2，d = 2時，是(3,1)點。是以當從(3,1)向下走一步，到達(3,2)。是以這個snake是：(3,1) ->(3,2) ->(5,4)。

在整個過程中，存在兩條snake，我們選擇起點x值較大的snake，是以是：(3,1) ->(3,2) ->(5,4)。

k = 3：這種情況下，(k = 4， d = 2)是不可能的，是以我們必須在(k = 2，d = 2)時向右移動一步。當k = 2, d = 2時， 是(3,1)點。是以從(3,1)點向右移動一步是(4,1)點。是以整個snake是：(3,1) -> (4,1) -> (5,2).

算法實作

我們有兩個循環，我們需要一個資料結構。

請注意，​​

​d（n）​

​​的解僅取決于​

​d（n-1）​

​​的解。還請記住，對于​

​d​

​​的偶數值，我們在偶數​

​k行​

​​上找到端點，而這些端點僅取決于全部在奇數k行上的先前端點。對于​

​d​

​​的奇數值也是如此。

我們使用稱為​​

​V​

​​的數組，其中​

​k​

​​為索引，終點的​

​x​

​​位置為值。我們不需要存儲​

​y​

​​位置，因為我們可以根據​

​x​

​​和​

​k​

​​來計算它：​

​y = x-k​

​​。同樣，對于給定的​

​d​

​​，​

​k​

​​在​

​[-d .. d]​

​範圍内。

​

​bool down = ( k == -d || ( k != d && V[ k - 1 ] < V[ k + 1 ] ) );​

​

如果​

​k = -d​

​​，我們一定是向下移動了；如果​

​k = d​

​​，我們一定是向右移動了。

對于正常的中間情況，我們選擇從​​

​x​

​​值較大的任何相鄰行開始。這保證了我們到達​

​k​

​線上盡可能遠的點。

V[ 1 ] = 0;
for ( int d = 0 ; d <= N + M ; d++ )//外循環，進行多少次代表有多少個snake和V數組
{
  for ( int k = -d ; k <= d ; k += 2 )//内循環
  {
    // down or right?
    bool down = ( k == -d || ( k != d && V[ k - 1 ] < V[ k + 1 ] ) );
    int kPrev = down ? k + 1 : k - 1;//如果向下，那麼上一步應該是k+1
    // start point，上一個點
    int xStart = V[ kPrev ];//v[k]=x
    int yStart = xStart - kPrev;//y=x-k
    // mid point，下一個點
    int xMid = down ? xStart : xStart + 1;
    int yMid = xMid - k;
    // end point
    int xEnd = xMid;
    int yEnd = yMid;
    // follow diagonal
    int snake = 0;//是否有對角線繼續往重點走
    while ( xEnd < N && yEnd < M && A[ xEnd ] == B[ yEnd ] ) 
    { 
      xEnd++; yEnd++; snake++; 
    }
    // save end point
    V[ k ] = xEnd;
    // check for solution
    if ( xEnd >= N && yEnd >= M ) /* solution has been found */
  }
}

上面的代碼尋找一條到達終點的​

​snake​

​​。因為​

​V數組​

​​裡面存儲的是在​

​k line​

​​最新端點的坐标，是以為了尋找到所有的​

​snake​

​​，我們在​

​d​

​​的每次循環完畢之後，從​

​d(Solution)周遊到0​

​。如下：

IList<V> Vs; // saved V's indexed on d
IList<Snake> snakes; // list to hold solution
//從後往前推，最後一條snake是到達終點必須經過的路線。
POINT p = new POINT( N, M ); // start at the end
for ( int d = vs.Count - 1 ; p.X > 0 || p.Y > 0 ; d-- )
{
  var V = Vs[ d ];//内循環産生的資料
  int k = p.X - p.Y;//本次循環的起點的k線
  // end point is in V
  int xEnd = V[ k ];
  int yEnd = x - k;
  // down or right?
  bool down = ( k == -d || ( k != d && V[ k - 1 ] < V[ k + 1 ] ) );
  int kPrev = down ? k + 1 : k - 1;//上一個snake的k線
  // start point
  int xStart = V[ kPrev ];
  int yStart = xStart - kPrev;
  // mid point
  int xMid = down ? xStart : xStart + 1;//中間點
  int yMid = xMid - k;
  snakes.Insert( 0, new Snake( /* start, mid and end points */ ) );
  p.X = xStart;
  p.Y = yStart;
}

時間複雜度: 期望為​

​O(M+N+D^2)​

​​，最壞情況為為​

​O((M+N)D)​

​ 。

有興趣的可以繼續閱讀下一篇文章 ​​Myers‘Diff之線性空間細化​​ 。

算法實踐：​​DiffUtil和它的差量算法​​

參考連結：

​​​代碼:diff-match-patch​​​​diff2論文​​​​Myers diff alogrithm:part 1​​​​Myers diff alogrithm:part 2​​

文章到這裡就全部講述完啦，若有其他需要交流的可以留言哦！！

myers diff 算法 數組 解決方案
上一篇: 手寫diff算法
下一篇: java時間輪定時器_時間輪定時器

繼續閱讀