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

31–40 of 64 posts

Re: Diff Algorithms

#31

Post by travisjungroth »

HeyImAlex wrote: post #8
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…

Another thing I’ve encountered with tree/structured diffs is a concept of identity. diff([{id:1,name:foo}],[{id:2,name:foo}] should show object w/ id:1 removed and id:2 added, not id changed from 1 to 2. Tough because then your diffing algo needs to be aware of the object structure (imo using convention and saying “no objects can contain this key” is pretty tough when you accept any user generated data).

I love this. I think you could simplify it by generalizing. Something like immutability. These keys can’t be changed, only an object destroyed and another created. A case of that is a primary key (maybe that’s the only case).

You can always represent a change as a removal and an addition. It’s smart to actually consider when should you. “Never” and “whenever possible” don’t seem like the best answers.

Re: Diff Algorithms

#32

Post by jFriedensreich »

while work on pure algorithms is invaluable i always feel work on knowledge augmented algorithms has lots of untapped potential. two examples: recording key events like move and delete on a more fine grained timescale or directly from editors and then storing those as mutable metadata in commits that is only allowed to be used for diff generation. as its provable if diffs are technically correct these do not weaken the consistency guarantees while adding helpful context. they are also highly compressable and pruneable. another one is optimizing diffs for consumption by llms and let those generate for optimal human readability.

Re: Diff Algorithms

#33

Post by cokernel_hacker »

dekhn wrote: post #14

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.

It seems he is still active in the bioinformatics space: https://github.com/thegenemyers/FASTK

Re: Diff Algorithms

#34

Post by o11c »

karteum wrote: post #23

I wish that the diff/patch would be able to better take into account moved data (not only as deletion+add but with with a proper semantic indicating the moved block). This would both lead to smaller and more readable patches. I noticed that some peoble have worked on such an algorithm, e.g. https://en.wikipedia.org/wiki/User:Cacycle/diff

If you squint hard enough, that's also what `git` does at the file level, when it detects renames even if the file changed.

Re: Diff Algorithms

#35

Post by o11c »

rs186 wrote: post #21
ashu1461 wrote: post #17

Earlier quoted context omitted.

Interesting, didn’t think of it that way

There is this debate of virtual DOM vs no virtual DOM, and from time to time you see people on HN claim how great vanilla JS is. Won't get into the former debate, but for the latter, people who make such comments probably aren't aware how different it is to create a UI as complex as Outlook/reddit/Spotify vs their personal website or a simple demo. For complex sites with lots of widgets and data, being able to write…

As someone mostly familiar with non-web UIs - isn't the real question "why aren't you using MVC instead of a big lump of spaghetti?"

Re: Diff Algorithms

#36

Post by znkr »

fiddlerwoaroof wrote: post #22

I wonder about the importance of minimality: it itself seems like a heuristic for “interest” or some other thing that users of diffs actually care about. For example, a diff like: + x += 1 - x -= 1 Seems almost useless: it doesn’t provide any context about the meaning of x and, as a result, nearly every source review tool provides unchanged line in addition to highlighting the change. And, even then, by preventing co…

A minimal diff is one where the number of edits is minimal. The context around edited lines does not count as edits, because they are matching lines. That said, minimal is definitely only a proxy, that’s why is a good property to relax.

Re: Diff Algorithms

#37

Post by usr1106 »

yboris wrote: post #2

Mildly related: my favorite tool for viewing .git diffs diff2html - a CLI that with one command opens the diff in your browser https://diff2html.xyz/ -- https://github.com/rtfpessoa/diff2html

Mine is meld. (One my phone now, so cannot compare which one seems superior)

Re: Diff Algorithms

#38

Post by OliverGilan »

jFriedensreich wrote: post #32

while work on pure algorithms is invaluable i always feel work on knowledge augmented algorithms has lots of untapped potential. two examples: recording key events like move and delete on a more fine grained timescale or directly from editors and then storing those as mutable metadata in commits that is only allowed to be used for diff generation. as its provable if diffs are technically correct these do not weaken t…

Do you have examples of any of these ideas being implemented? In general I agree, there’s so much opportunity for these “knowledge augmented” algorithms

Re: Diff Algorithms

#39

Post by znkr »

ashu1461 wrote: post #3

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

One use case where I never want to miss it is in tests: Understanding what the differences between the expectation and the actual result are is invaluable.

Re: Diff Algorithms

#40

Post by JavierFlores09 »

yboris wrote: post #2

Mildly related: my favorite tool for viewing .git diffs diff2html - a CLI that with one command opens the diff in your browser https://diff2html.xyz/ -- https://github.com/rtfpessoa/diff2html

I like https://diffs.dev, it has a pretty sleek look and has an extension to make it the default diff view for github
Post reply on HN