Diff Algorithms
flo.znkr.io
Diff Algorithms
1–10 of 64 posts
Re: Diff Algorithms
#2Mildly 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
Re: Diff Algorithms
#3Apart from source code versioning what are the other most important real world use cases of diff algorithms ?
Re: Diff Algorithms
#4Apart from source code versioning what are the other most important real world use cases of diff algorithms ?
- Backup and restore
- integrity checks from security perspective
- nlp, finding same tokens in text
Etc
Re: Diff Algorithms
#5Apart from source code versioning what are the other most important real world use cases of diff algorithms ?
I encountered one about 17 years ago. It was for diffing IP packets, TCP segments, and network event payloads. At the time I worked at RSA Security on a network forensics and security analytics product, written in a mix of C and C++. In one of the projects I worked on, we needed to let users diff the packets, segments, and payloads. Back then we were very conservative about adding third-party libraries to the product. I have written more about that culture here: https://news.ycombinator.com/item?id=39951673
Long story short, due to the conservative culture, most data structures and algorithms were implemented in house. The diff algorithm for packets/segments/payloads was written in house too and I was the one to write it.
My implementation was based on a straightforward dynamic programming solution to the longest common subsequence problem. If I recall correctly, it ran in O(mn) time and O(min(m, n)) space in the worst case, where m and n are the lengths of the two sequences. I knew there were more efficient algorithms, but this code was not performance critical. I chose to keep the implementation simple so anyone could understand it, learn it quickly, and fix bugs if they arose. It served us well for the next seven years until the product was replaced with a new one.
On a related note, I sometimes miss that older style of software development where we would dive deep into a problem domain, master it, and design solutions ourselves. I am not being naively nostalgic though. I am very well aware that modern development, with its reliance on well established libraries, usually delivers much greater productivity and reliability. Still, I think the slower and more deliberate approach of building things from the ground up had a certain charm.
Re: Diff Algorithms
#6There 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 newline at end of file" logic working.
For tree diffs, consider that for HTML something like `
x
y
` should be unmergeable, whereas `xy` should be mergeable.(Aside: the blind promotion of `` and `` did great harm to the notion of semantic HTML. Most things people use italics for (book titles, thoughts, foreign words) are explicitly things that `` should not be used for.)
Re: Diff Algorithms
#7Apart from source code versioning what are the other most important real world use cases of diff algorithms ?
We diff construction schedules! These tend to be massive Gantt charts (400-700 pages is common).
Re: Diff Algorithms
#8There 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).
Re: Diff Algorithms
#9Apart from source code versioning what are the other most important real world use cases of diff algorithms ?
There are a bunch of more (and less) specialised ones used for contract red-lining.
Also in the legal space, sorting through discovery can be incredibly tedious. There are lots of diff-based and diff-like solutions in this space; most are completely proprietary and undocumented.
Re: Diff Algorithms
#10A while ago I discovered the lesser known Tichy diff algorithm that seems to preserve more context and is better suited for big code refactors compared to Myers: https://www.researchgate.net/publication/220439403_The_Strin... via https://bryanpendleton.blogspot.com/2010/04/more-study-of-di...