computer science

LZFSE

LZFSE is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand LZFSE rather than just read about it. In short: LZFSE (Lempel–Ziv Finite State Entropy) is an open source lossless data compression algorithm created by Apple Inc. It was released with a simpler algorithm called LZVN.

Key takeaways

LZFSE belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect LZFSE to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of LZFSE from memory before moving on to harder problems.

Reference excerpt

LZFSE (Lempel–Ziv Finite State Entropy) is an open source lossless data compression algorithm created by Apple Inc. It was released with a simpler algorithm called LZVN.

Overview The name is an acronym for Lempel–Ziv and finite-state entropy (implementation of asymmetric numeral systems). LZFSE was introduced by Apple at its Worldwide Developer Conference 2015. It shipped with that year's iOS 9 and OS X 10.11 releases. Apple claims that LZFSE compresses with a ratio comparable to that of zlib (DEFLATE) and decompresses two to three times faster while using fewer resources, therefore offering higher energy efficiency than zlib. It was aimed for scenarios where decompression speed and rate should be prioritised equally. Part of this energy efficiency was achieved by optimising the algorithm for modern micro-architectures, specifically focusing on arm64. Third-party benchmarking confirms that LZFSE decompresses faster than zlib, but also suggests that many other modern compression algorithms may have more favorable compression algorithm performance characteristics such as density, compression speed and decompression speed by a significant margin. According to the Squash Benchmark, LZFSE is similar in speed to zstd (level 6), but has a slightly worse ratio. LZVN is similar in speed to LZ4 level 4, with a slightly worse ratio as well. Neither LZFSE nor LZVN is tunable at runtime, although a few constants can be tweaked at compile time for the usual speed-ratio trade-off.

Implementation A reference C library written by Eric Bainville was made available under the 3-clause BSD License after WWDC 2016. It includes an executable to compress and decompress LZFSE streams as well. There are no plans to expose an LZVN API. Apple's LZFSE implementation uses a simpler algorithm called LZVN when the input is smaller than LZFSE_ENCODE_LZVN_THRESHOLD (4096 bytes). This is a LZSS-type algorithm without entropy encoding but with three widths of REP (L,M,D) packets. In the open source reference implementation, Apple explains that LZFSE does not perform as well for small sizes, so LZVN is used instead. This algorithm in libfastCompression.a was discovered earlier as the default kernelcache compression method in Mac OS X Yosemite Developer Preview 1 (2014), replacing the legacy lzss compression from Haruhiko Okumura.

Usage AppleFSCompression.framework (AFSC), the mechanism for quasi-transparent compression in HFS Plus and Apple File System, supports LZFSE and LZVN since OS X 10.9. Apple's Disk Images framework has offered an LZFSE-based encoding called ULFO since Mac OS X 10.11, accessible via hdiutil(1) and some third-party image utilities. Apple introduced the Apple Archive format and its associated API in macOS High Sierra in 2017. The extension name is .aar (since macOS Big Sur, used to be .yaa). Encryption was introduced in macOS Monterey, when AA became the default Archive Utility format. Three command-line utilities are available in macOS to handle AA files. Of third-party programs, Keka is able to use the system APIs to handle AA files, but no independent implementations exist on other systems.

See also Zstandard – another combination of LZ77 and FSE, by Yann Collet, the FSE author LZ4 compression algorithm – a fast member of the LZ77 family, also available on Apple platforms

References

External links lzfse on GitHub Finite State Entropy by Yann Collet (Cyan4973), the source of the FSE implementation in LZFSE Discussion on Encode.su, from which the maintainer Eric Bainville has taken suggestions

Worked examples

Example 1 — a first encounter with LZFSE

Start with the simplest possible case. Write down what LZFSE claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to LZFSE before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about LZFSE ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of LZFSE

In research: LZFSE appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses LZFSE in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: LZFSE is common in secondary-school and first-year university syllabi. It links to neighbouring topics Data compression, Free computer libraries, Lossless compression algorithms, so understanding it makes those chapters shorter.
In everyday life: Look for LZFSE outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study LZFSE in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what LZFSE means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain LZFSE out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is LZFSE in simple terms?

LZFSE (Lempel–Ziv Finite State Entropy) is an open source lossless data compression algorithm created by Apple Inc. It was released with a simpler algorithm called LZVN.

Why does LZFSE matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study LZFSE?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on LZFSE.