4 ms·
1. Lempel-Ziv compression algorithms (both LZ77 and LZ78). They are practical, even if one code their basic versions will get good compression ratio. Moreover,
by wmu 10y ago
1. Lempel-Ziv compression algorithms (both LZ77 and LZ78). They are practical, even if one code their basic versions will get good compression ratio. Moreover, they opened the whole big chapter of data compression (LZW, LZSS and more).
2. The algorithm behind rsync. Nice one.
3. Jarvis algorithm for finding convex hull.
4. Speaking of data structures I like xor-linked list, it's neat.
[1] https://en.wikipedia.org/wiki/LZ77_and_LZ78 https://en.wikipedia.org/wiki/LZ77_and_LZ78
[2] https://en.wikipedia.org/wiki/Rsync#Algorithm https://en.wikipedia.org/wiki/Rsync#Algorithm
[3] https://en.wikipedia.org/wiki/Gift_wrapping_algorithm https://en.wikipedia.org/wiki/Gift_wrapping_algorithm
[4] https://en.wikipedia.org/wiki/XOR_linked_list https://en.wikipedia.org/wiki/XOR_linked_list
- majewsky 10y ago> 2. The algorithm behind rsync. Do you mean the rolling checksum part?
- wmu 10y agoAll parts, I like how the simple parts were composed to built pretty complicated algorithm.
- The_Hoff 10y agoYeah, I assume majewsky is wondering if you mean just the rolling checksum part because that's the most complex part. Rsync, as a whole, is certainly one of my favorites and the algorithm(s) it uses are some of the ones I most often call explicitly.
- andreareina 10y agoI'm a big fan of Huffman coding myself, but Lempel-Ziv definitely gets points for being simple and intuitive.