Automating Book Indexing with sed

Originally authored by Eric Pement (1997), with minor corrections in 2001.

In the world of book and magazine publishing, creating a comprehensive index after the typesetting phase is a critical task. I encountered a scenario where I needed to transform raw data into a polished, print-ready index.

The Workflow Process

The initial data collection was a manual, collaborative effort:

• Highlighting: Terms intended for the index were marked on hard-copy proof pages using a yellow highlighter.
• Data Entry: Volunteers typed these terms and their corresponding page numbers into a computer.
• Formatting: Each entry was separated by a semicolon (;).

The raw input was entered chronologically as pages were processed, resulting in a fragmented list like this:

Buddhism, Zen; 1 atheism; 1 dualism; 1 Solomon; 2 Lausanne Covenant; 4 Lewis, C.S.; 4 Lausanne Covenant; 5 Mormonism; 6 Latter-day Saints; 6 Trinity; 6 Lausanne, Switzerland; 8 Trinity; 8

---

Step 1: The Sorting Challenge

To organize this data, a sort utility was required. However, a standard ASCII sort is insufficient because it handles numbers literally (e.g., "19" comes before "3"). We needed a case-insensitive and numeric-aware sort.

Achieving this with the GNU sort tool was surprisingly tricky due to opaque documentation. The successful command is:

sort -t";" +0f -1 +1n input.file

Breakdown of Sort Switches

After sorting, the data looked like this:

Adam; 13
Adam; 21
Adam; 30-32
agnosticism; 9
agnosticism; 120
atheism; 1
atheism; 9
...

---

Step 2: Transforming Data with sed

The goal was to merge duplicate terms into a single line with a comma-separated list of pages.

Desired Transformation: $\text{Term}; \text{ Page A} \rightarrow \text{Term}; \text{ Page B} \implies \text{Term, Page A, Page B}$

While I previously used awk, I discovered that a sed script could achieve this more concisely.

The INDEXER.SED Script (v1.0)

# INDEXER.SED v1.0 - indexes sorted input file
{ 
    # On every line of the file...
    N; 
    # If not the last line, append the Next line to the buffer
    s/^\([^;]*;\) \(.*\)\n\1 \(.*\)/\1 \2, \3/ 
    # If substitution matched, merge and jump back to :loop
    t loop; 
    s/;/,/; 
    # Otherwise, replace semicolon with comma
    P; 
    # Print the first line of the buffer
    D; 
    # Delete the first line and restart the loop
}

Logic Flow Diagram

---

The "Fragility" Bug

While the script works on perfect data, a single formatting error—such as a missing semicolon—causes a catastrophic failure for the remainder of the file.

Comparison of Input Sets

The Result: In SET 2, the missing semicolon prevents the regex from matching. Because the script relies on a two-line buffer, the "bad" line stays in the buffer, shifting the alignment. Every subsequent line is then processed incorrectly, leading to a jumbled output where terms and page numbers are mismatched.

Technical Analysis of the Failure

The core of the issue lies in the search pattern: ^\([^;]*;\) \(.*\)\n\1 \(.*\)

Using LaTeX notation, the logic is: $\text{Match} = \underbrace{(\text{Non-semicolons} + \text{Semicolon})}_{\text{Group 1}} + \underbrace{(\text{Pages})}_{\text{Group 2}} + \text{Newline} + \underbrace{\text{Group 1}}_{\text{Repeat}} + \underbrace{(\text{Pages})}_{\text{Group 3}}$

1. The script checks if the current line and the next line start with the exact same string (up to the semicolon).
2. If they match, it deletes the newline and the redundant term, appending the page numbers.
3. If they do not match (or if a semicolon is missing), the t loop command is skipped.
4. The script then executes P (print) and D (delete).

When a line lacks a semicolon, it fails the regex. It then occupies the "second half" of the pattern buffer. Since the script only deletes the first line of the buffer (D), the malformed line persists, throwing off the synchronization for every following entry.