技术问询：如何在文件中实现数据指向？附压缩技术相关疑惑

Hey there! Since you already have a solid grasp of pointers and their core principles, you’re halfway there—let’s connect that knowledge to how compression uses "data pointing" in files.

First: What "Data Pointing" Means in Compression #

Unlike memory pointers (which reference a specific memory address), compression uses relative references to duplicate data that’s already appeared earlier in the file. Instead of writing the same bytes again, you store a "pointer" that says: "Go back X bytes, and copy Y bytes from there". This is the core idea behind algorithms like LZ77 and LZ78 (the basis for ZIP, gzip, etc.).

How to Implement This in a File #

Let’s break down the practical steps with a simple example:
Suppose your raw data is: hello hello world

• The first hello is written as-is (since there’s nothing to reference yet).
• When we hit the second hello, instead of writing all 5 bytes, we store a pair like (6, 5):
  • 6 = offset (how far back to look from the current position—6 bytes back gets us to the start of the first hello)
  • 5 = length (how many bytes to copy from that offset)

To make this work in a file, you need two key components:

• A way to distinguish between literal bytes (raw data that can’t be referenced) and pointer pairs (the offset/length values). This is usually done with a flag bit or a header that tells the decompressor which type it’s reading.
• A sliding window (for LZ77-style algorithms): As you read/write the file, you keep track of a recent chunk of data (the window) so you can look for duplicates. When a duplicate is found, you write the pointer instead of the literal data.

Example of a Simplified Compression Process #

Let’s take raw data ababab:

1. Write a (literal)
2. Write b (literal)
3. Now we see ab again—instead of writing those bytes, write (2, 2) (offset 2 bytes back, copy 2 bytes)
4. Next ab is another duplicate—write (4, 2)

The compressed file would look something like: [literal:a][literal:b][pointer:2,2][pointer:4,2] (with actual encoding to save space, like using variable-length integers for offsets/lengths).

Recommended Resources #

If you want to dive deeper into the nitty-gritty:

• Books:
  • Data Compression: The Complete Reference by David Salomon (covers all major algorithms with implementation details)
  • Compression Algorithms for Real Programmers by Mark Nelson (practical, code-focused guide with examples in C)
• Articles:
  • Look for deep dives into LZ77/LZ78 implementation—many programming blogs walk through building a basic LZ77 compressor from scratch, which will clarify how pointers are stored and used in files.

内容的提问来源于stack exchange，提问作者BidoTeima