Decoding the PBF String Table and Tag Indices Jump to heading#

No string appears twice in a PBF file’s data. Every key and every value is an index into a table that belongs to one block, and understanding that indirection explains both why the format is so compact and why an index carried across a block boundary is meaningless.

Prerequisites Jump to heading#

• Python 3.10+ with compiled OSM protobuf definitions, or osmium if you only want to verify results.
• The block structure from PBF File Structure Deep Dive.
• Familiarity with dense node encoding, from Reading Dense Nodes and Delta-Encoded Coordinates.
• A regional PBF file to read.
• Patience with the one genuinely unusual encoding in the format.

Conceptual minimum Jump to heading#

Each PrimitiveBlock contains a StringTable: a repeated field of byte strings. Every key and value in that block is stored as an integer index into it. Index 0 is always the empty string and is reserved as a delimiter, which matters enormously for dense nodes.

Two different tag encodings exist in the same format.

Ways and relations use parallel arrays. Each element carries a keys list and a vals list of equal length, and the tags are the pairwise zip of the two. This is straightforward.

Dense nodes use one interleaved stream. All the nodes in a group share a single keys_vals array, in which each node’s tags appear as alternating key and value indices, terminated by a zero. A node with no tags contributes just the zero. Walking that stream is the only way to know which tags belong to which node, and it must be walked in step with the node array rather than indexed into.

Runnable solution Jump to heading#

from __future__ import annotations

import logging
from collections.abc import Iterator

logging.basicConfig(level=logging.INFO, format="%(levelname)s: %(message)s")
logger = logging.getLogger("osm.pbf.stringtable")


class StringTable:
    """A block's string table. Indices are meaningless outside their block."""

    def __init__(self, entries: list[bytes]) -> None:
        self._entries = entries
        if not entries or entries[0] != b"":
            # Index 0 must be the empty string: dense nodes use it as a
            # terminator, so a table without it cannot be walked.
            raise ValueError("string table index 0 is not the empty string")

    def __len__(self) -> int:
        return len(self._entries)

    def get(self, index: int) -> str:
        if not 0 <= index < len(self._entries):
            raise IndexError(f"string index {index} outside a table of "
                             f"{len(self._entries)} entries")
        # OSM strings are UTF-8; a decode error means a corrupt block.
        return self._entries[index].decode("utf-8")


def tags_from_parallel(table: StringTable, keys: list[int],
                       vals: list[int]) -> dict[str, str]:
    """Ways and relations: two equal-length arrays, zipped."""
    if len(keys) != len(vals):
        raise ValueError(f"keys/vals length mismatch: {len(keys)} vs {len(vals)}")
    return {table.get(k): table.get(v) for k, v in zip(keys, vals)}


def tags_from_dense(table: StringTable, keys_vals: list[int],
                    node_count: int) -> Iterator[dict[str, str]]:
    """Dense nodes: ONE interleaved array for the whole group.

    Walked strictly sequentially. A zero ends the current node's tags; a
    node with no tags contributes a single zero and nothing else.
    """
    position = 0
    emitted = 0
    length = len(keys_vals)

    while emitted < node_count:
        tags: dict[str, str] = {}
        while position < length and keys_vals[position] != 0:
            if position + 1 >= length:
                raise ValueError("keys_vals ended mid-pair; block is truncated")
            key = table.get(keys_vals[position])
            value = table.get(keys_vals[position + 1])
            tags[key] = value
            position += 2
        position += 1          # step over the zero terminator
        emitted += 1
        yield tags

    if position < length:
        # Leftover data means the walk and the node count disagree.
        logger.warning("%d unconsumed keys_vals entr(ies) after %d node(s)",
                       length - position, node_count)


def table_stats(table: StringTable, keys_vals: list[int]) -> dict[str, float]:
    """How much the table is actually saving on this block."""
    used = {i for i in keys_vals if i != 0}
    referenced_bytes = sum(len(table.get(i).encode()) for i in keys_vals if i)
    stored_bytes = sum(len(table.get(i).encode()) for i in range(len(table)))
    ratio = referenced_bytes / stored_bytes if stored_bytes else 0.0
    logger.info("table holds %d entr(ies), %d used, %.1fx expansion if inlined",
                len(table), len(used), ratio)
    return {"entries": len(table), "used": len(used), "expansion": ratio}


if __name__ == "__main__":
    table = StringTable([b"", b"highway", b"residential", b"name", b"High St"])
    stream = [1, 2, 3, 4, 0,      # node 1: two tags
              0,                   # node 2: none
              1, 2, 0]             # node 3: one tag
    for tags in tags_from_dense(table, stream, node_count=3):
        logger.info("%s", tags)

Step-by-step walkthrough Jump to heading#

1. Assert index zero is empty. A table whose first entry is not the empty string cannot be walked, because the terminator would collide with a real key.
2. Bound-check every index. An out-of-range index means a corrupt block or a mismatched table, and a clear error beats a confusing one from the decoder.
3. Zip parallel arrays only after checking lengths. A length mismatch silently truncates under a plain zip, losing tags without any signal.
4. Walk the dense stream, never index into it. There is no offset table; a node’s tags begin wherever the previous node’s terminator left off, and that position is only knowable by walking.
5. Handle the untagged node explicitly. A lone zero is a complete node contribution, and a reader that expects at least one pair per node desynchronises on the first untagged node — which in OSM is most of them.
6. Detect a truncated stream. An odd number of entries before a terminator means the block is damaged, and failing there is better than emitting a half-read tag.
7. Check for leftovers. Unconsumed entries after the expected node count mean the walk and the node array disagree, which is the signature of a desynchronisation earlier in the block.

Verification Jump to heading#

• Tag counts match a reference. Compare total tags per block against osmium fileinfo or a known-good reader.
• Untagged nodes appear. A block should yield some nodes with empty tag dictionaries; if none do, the terminator handling is wrong.
• The stream is fully consumed. After emitting the expected node count, no entries should remain.
• A known feature decodes correctly. Pick a node whose tags you can check independently and confirm they match.
• Indices do not cross blocks. Decode two blocks and confirm the same index resolves to different strings, which proves the scoping is being respected.

Common errors and fixes Jump to heading#

Specification reference Jump to heading#

A PrimitiveBlock contains a StringTable whose first entry is always the empty string, reserved for use as a delimiter. Ways and relations encode tags as parallel keys and vals arrays of string-table indices. Dense nodes encode all tags for a group in a single keys_vals array of alternating key and value indices, with each node’s tags terminated by a zero. See the PBF format documentation for the message definitions and the delimiter convention.

Frequently Asked Questions Jump to heading#

Related Jump to heading#

• PBF File Structure Deep Dive — the parent topic and the block framing.
• Reading Dense Nodes and Delta-Encoded Coordinates — the coordinate half of the same encoding.
• Writing a Valid OSM PBF File from Python — building a string table rather than reading one.
• How to Decode OSM PBF Headers in Python — the header that precedes these blocks.
• Memory-Efficient Chunk Processing — why block scoping helps a streaming reader.

Up one level: PBF File Structure Deep Dive.