Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Diff Algorithms

flo.znkr.io

Post reply on HN
Print view View original

11–20 of 64 posts

Re: Diff Algorithms

#11

Post by aatd86 »

ashu1461 wrote: post #3

Apart from source code versioning what are the other most important real world use cases of diff algorithms ?

Minimizing DOM mutation operations. In react for instance. But not only.

Re: Diff Algorithms

#13

Post by mpyne »

ashu1461 wrote: post #3

Apart from source code versioning what are the other most important real world use cases of diff algorithms ?

Aside from the others already mentioned, it's very useful in infrastructure-as-code context like Kubernetes.

I also used diff at work today to compare the output of two different 'docker history' outputs to look for what a high-level overview of changes made by a contractor tasked with hardening a base image.

Re: Diff Algorithms

#14

Post by dekhn »

The creator of the Myers algorithm is Gene Myers. He also helped create the BLAST algorithm, one of the fastest and most important DNA and protein search algorithms, and also implemented most of the original human genome assembly done by Celera. he also helped invent and publish the suffix array.

Re: Diff Algorithms

#15

Post by dekhn »

o11c wrote: post #6

There are at least 3 fundamentally different kinds of diff: * Single-dimensional. Diffs of text lines are just this. * Multi-dimensional. Diffs of words or characters are usually going to be this since lines still matter, but there are multiple approaches (line-first? weighted tokens?). * Tree-based. Unfortunately, these are woefully scarce and poorly documented. For text diffs, it's nontrivial to get the "missing ne…

I've also worked with probabilistic diff- like tree-based, but tolerant of parsing errors.

Re: Diff Algorithms

#16

Post by MrJohz »

o11c wrote: post #6

There are at least 3 fundamentally different kinds of diff: * Single-dimensional. Diffs of text lines are just this. * Multi-dimensional. Diffs of words or characters are usually going to be this since lines still matter, but there are multiple approaches (line-first? weighted tokens?). * Tree-based. Unfortunately, these are woefully scarce and poorly documented. For text diffs, it's nontrivial to get the "missing ne…

Can you explain why the `p` example is unmergeable whereas the `b` one isn't? I can't see any difference between the two examples other than the tag used.

Re: Diff Algorithms

#18

Post by e12e »

MrJohz wrote: post #16
o11c wrote: post #6

There are at least 3 fundamentally different kinds of diff: * Single-dimensional. Diffs of text lines are just this. * Multi-dimensional. Diffs of words or characters are usually going to be this since lines still matter, but there are multiple approaches (line-first? weighted tokens?). * Tree-based. Unfortunately, these are woefully scarce and poorly documented. For text diffs, it's nontrivial to get the "missing ne…

Can you explain why the `p` example is unmergeable whereas the `b` one isn't? I can't see any difference between the two examples other than the tag used.

The first is:

    One paragraph.

    Followed by another.
The second is two bold letters, one after another in a single word.

However if the html is "an application" more than it is "a document" - a b-tag with two letters, might be meaningfully different from two b-tags in sequence (for example with css:)

   b { display: block }
So, I'd say as a fragment two bold tags might be mergable - but not in the general case?

Ed: ie if diffing input from a html input field (rich editor) merging bold tags would probably be what you want - when the first edit bolds first letter, and second edit bolds second letter.

Re: Diff Algorithms

#19

Post by gritzko »

o11c wrote: post #6

There are at least 3 fundamentally different kinds of diff: * Single-dimensional. Diffs of text lines are just this. * Multi-dimensional. Diffs of words or characters are usually going to be this since lines still matter, but there are multiple approaches (line-first? weighted tokens?). * Tree-based. Unfortunately, these are woefully scarce and poorly documented. For text diffs, it's nontrivial to get the "missing ne…

I implemented tree based diff for a JSON superset https://github.com/gritzko/go-rdx It boils down to single dimensional, very much like JSON or DOM tree is represented as a linear text.

Re: Diff Algorithms

#20

Post by rs186 »

Great work. I was just recently dealing with creating diff in Go and faced the same problem of finding a good library. Some diffmatchpatch APIs expect/return escaped texts, and I was screaming why would you do that??? Why doesn't the library just return raw strings? I ended up using diffmatchpatch to get patch objects and then produced unified diffs with some vibecoding. I'll definitely try this out when I revisit this.

PS regarding readability, I think VSCode put a lot of effort into creating nice-to-read diffs (e.g. https://code.visualstudio.com/updates/v1_81#_diff-editor), some of which is done in the algorithm itself (https://code.visualstudio.com/updates/v1_78#_diff-algorithm-...). But apparently that's in TypeScript, and not all heuristics done there for an editor is suitable to be in a generic diff algorithm. Still, there might be something worth exploring.

Post reply on HN