Algorithm for Merging Two Text Edits

• git and others are doing it

  • It does a good job when incorporating branches
  • I think it’s probably a very simple algorithm, but I want to know more about it now (blu3mo)

• https://blog.jcoglan.com/2017/05/08/merging-with-diff3/

  • I see, once you can get the diff, the rest is easy

• https://gist.github.com/gurimusan/7e554eb12f9f59880053

  • To calculate the difference, calculate the following 3 things:
  • Edit distance (levenshtein distance)
    • A numerical representation of the difference between two elements
  • LCS (Longest Common Subsequence)
    • The longest common subsequence of two elements X and Y
      • A subsequence doesn’t have to be continuous
      • Indeed, there may be something inserted between those strings
  • SES (Shortest Edit Script)
    • The shortest procedure to convert element X to element Y
  • To calculate these, there are algorithms like:
    • DP (Dynamic Programming)
    • Myers’ O(ND) algorithm
    • GNU diffutils, Git, etc.
    • Wu’s O(NP) algorithm
    • subversion, etc.

• I know it’s self-promotion, but I have implemented a program to find differences in deno (takker)

  • https://github.com/takker99/onp
  • Since it is a single file, you can simply copy and paste it into a node environment and use it directly
  • [/takker/O(NP) algorithm](https://scrapbox.io/takker/O(NP) algorithm)
    • Is this it? (blu3mo)
    • Is this Wu’s O(NP) algorithm? (blu3mo)
      • What is P?

      • Wu’s algorithm is an algorithm with an average computational complexity of O(N+PD) and a worst-case complexity of O(NP), where N is the sum of the lengths of the two element sequences and P represents the total number of “deletions” in SES footnote 4.

      • To convert cosense to helpfeel, you need to add at least one character and insert & delete 0-7 characters (takker)
        • You can’t reduce the number of additional operations further, and you can’t narrow down the range of insert & delete operations
      • This 0-7 corresponds to P

• https://qiita.com/convto/items/e05d8147d9808a27b8ff

  • By using the edit graph, the problem of finding the shortest editing procedure can be rephrased as finding the shortest of several editing procedures passing through points (0,0) and (M,N) (SES).

    • Definitely (blu3mo)
  • I roughly understood the feeling of it

  • The edit distance D can be calculated as D = Δ + 2P

    • The case where the edit distance matches Δ is when the comparison is a perfect match with LCS.

    • Otherwise, you need to return by the amount you deviated from Δ

  • Let k be the line that moves diagonally in a straight line, defined as k = x - y.

    • Ah, k represents the diagonal line, not a value

  • At this time, the range of possible values for k is determined by P, and it falls within the color-coded range below.

    • Which diagonal lines it can pass through