• 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