URL Normalization as a Set-Equality Problem

The crawler’s frontier stores URLs as opaque strings, and the same page arrives repeatedly under different strings. Uppercase in the host, a default port written explicitly, a trailing / on a path that has none, a query parameter order swapped, a fragment appended by a link, an entity encoded as / in one document and as %2F in another. Each of those strings can be a distinct frontier entry even though the server returns identical bytes for all of them. Deduplication is therefore not an optimization on top of the crawl; it is part of what makes the crawl terminate, and it sits on the critical path of the frontier rather than after it.

The trap is that the transformations which collapse duplicates are not all safe. Some are defined by a specification to preserve identity, some depend on server behaviour the crawler cannot observe, and some change meaning. A normalization function is a claim about which strings denote the same resource, and every aggressive rule in it is a bet that could merge two genuinely different pages into one frontier entry.

Two levels of sameness

It helps to separate two problems that are often conflated. Syntax normalization asks which strings are equivalent under the URI grammar. This is decided by RFC 3986’s rules for scheme-based normalization and is safe in the narrow sense that two strings equivalent under those rules denote the same URI. Semantic canonicalization asks which distinct URIs a particular site treats as the same page — ?id=5 and ?id=05, /page and /page/ — and this cannot be decided from the URL alone. It is a property of the server’s routing, discoverable only by asking.

A crawler needs both, but only the first can be applied unconditionally. The second must be bounded, because merging two URLs that the server treats differently destroys content that the crawl was meant to find, and the loss is silent: the frontier simply never fetches the second URL, and nothing reports a missing page.

The transformations the grammar licenses

RFC 3986 section 6.2.2 defines case normalization for the scheme and host: those components are compared case-insensitively, so HTTP and http, Example.COM and example.com are the same authority. The rest of the URI is case-sensitive by default, which means /About and /about are distinct paths and %3A and %3a are the same octet expressed two ways. Implementations that lowercase the whole URL break paths on servers that distinguish case, and this is a real class of bug rather than a theoretical one.

Percent-encoding normalization follows a separate rule. An octet that is unreserved in the grammar — letters, digits, -, ., _, ~ — must not be encoded, so %7E and ~ denote the same thing and decodable-unreserved encodings should be decoded. An octet that is reserved, such as / or ?, must not be decoded, because decoding changes the component structure: %2F inside a path segment is a literal slash that means something different from a separator, and turning it into / changes the resource identifier into a different one. Uppercase hexadecimal digits in the remaining escapes are canonical, so %2f and %2F are equivalent.

Dot-segment removal is required by the grammar: /a/./b, /a/b, and /a/c/../b all resolve to the same path. Removing them is safe because the resolution rule is part of the syntax. The same is not true of collapsing repeated slashes — //a and /a are different paths, and some servers route them differently — nor of adding or removing a trailing slash.

Default port removal is safe in one direction only. Given a scheme whose default port is known, https://host:443/ and https://host/ are the same origin. Given an unknown scheme, the default is unknown, and the port cannot be removed. The set of schemes a crawler handles is finite and small, so this rule is easy to implement correctly and easy to implement wrongly by treating any numeric port as suppressible.

A compact version of the safe subset:

import re
from urllib.parse import urlsplit, urlunsplit

UNRESERVED = set("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-._~")
DEFAULT_PORTS = {"http": "80", "https": "443"}
ESCAPE = re.compile(r"%([0-9A-Fa-f]{2})")

def unescape_unreserved(path):
    def fix(m):
        ch = chr(int(m.group(1), 16))
        return ch if ch in UNRESERVED else "%" + m.group(1).upper()
    return ESCAPE.sub(fix, path)

def remove_dot_segments(path):
    out = []
    for seg in path.split("/"):
        if seg == ".":
            continue
        if seg == "..":
            if len(out) > 1:      # never pop the leading empty segment
                out.pop()
            continue
        out.append(seg)
    return "/".join(out)

def normalize(url):
    parts = urlsplit(url)
    scheme = parts.scheme.lower()
    host = (parts.hostname or "").lower()
    port = parts.port
    if port is not None and str(port) == DEFAULT_PORTS.get(scheme):
        port = None
    path = unescape_unreserved(parts.path)
    path = remove_dot_segments(path) or "/"
    netloc = host if port is None else f"{host}:{port}"
    return urlunsplit((scheme, netloc, path, parts.query, ""))

Dropping the fragment is unconditional and correct for crawling. The fragment is never sent to the server; a request for page#section is a request for page. Two frontier entries differing only in fragment are the same fetch, and the crawler discovers no new bytes by keeping both. Keeping the fragment in the frontier also corrupts any later comparison, because the same page reached through two different anchors appears as two nodes.

What cannot be normalized from the string alone

Everything below the authority is the server’s business.

Trailing slashes are the most common case. A server may issue a redirect from /docs to /docs/, or serve the same content at both, or treat the second as a different resource. The crawler can learn the pattern per site by observing redirects, but it cannot assume it. Adding a slash to every path merges pages on servers where /docs and /docs/ differ; removing it from every path breaks servers that require the slash to route.

Query parameters are worse. Their order is not significant to most frameworks but is significant to some, and the specification offers no rule either way. Repeated parameters may be collapsed, ordered, or meaningful in sequence depending on the application. Parameters that carry session identifiers or tracking tokens produce URL spaces that are effectively infinite for a single page, and every distinct value is a distinct frontier entry. A crawler that strips known tracking parameters by name is making a heuristic bet; one that strips all query strings discards the identifying part of URLs on any site that serves content through parameters, which is most of them.

Host canonicalization beyond case has a similar character. Removing a leading www. is a guess: some sites serve different content at the bare and www names, and the redirect that would reveal the truth is only observable by fetching. Resolving through DNS is not sufficient either, since two names can share an address and still route differently by Host header.

Percent-encoding of characters outside ASCII is where the grammar and the web diverge most. The URI grammar admits non-ASCII only as percent-encoded octets, so a path containing a literal é is not a valid URI, yet browsers and links routinely produce one. The practical resolution is to encode it as UTF-8 octets, which is what browsers do and what servers decode. Internationalized domain names take the same shape through Punycode: the ASCII-compatible form is what goes on the wire and is what should be stored.

Over-normalization is a silent failure

Every merge rule reduces the frontier and speeds the crawl, and the cost of a wrong merge is invisible during operation. Consider a site that serves /item?id=7 and /item?id=07 as different products, or one where /news/2024/05 and /news/2024/05/ are a monthly archive and a daily index. A normalizer that strips leading zeros or forces a trailing slash silently drops one of each pair, and no error is raised at any layer. The only symptom is that the index later lacks content, which surfaces as a recall gap rather than a crawl error.

The mitigation is to separate the two decisions. The safe subset is applied before the URL enters the frontier, so the frontier never holds two entries that the grammar says are identical. Semantic merges are applied at index time, after the document has been fetched and parsed, using evidence from the response: the final URL after redirects, a declared canonical link where the site provides one, and a content digest to recognize byte-identical bodies served from different URLs. Merging at that point is reversible in the sense that both URLs were fetched, so nothing is lost if the merge was wrong.

There is a cost in doing it that way. Semantic duplicates are fetched before they are recognized, which spends politeness budget and bandwidth on bytes already held. For a site that generates an unbounded parameter space, the crawl may never finish discovering before it finishes fetching. That is why the frontier also needs a bound on how many URLs a single host may contribute and a way to recognize the shape of a URL space that is generating without limit — the same mechanism that keeps the frontier from growing without bound when a site mints new URLs faster than they can be fetched.

Normalization as a versioned policy

Because the rules are a series of bets, they belong in configuration with an explicit version rather than buried in a parser. A frontier keyed by normalized URLs is a persistent structure; changing the normalization rules after the crawl has begun means some stored keys are in the old vocabulary and some in the new, and the intersection of the two is a set of pairs that should have merged but did not. Either the policy is fixed for the lifetime of a frontier, or the frontier is rebuilt when the policy changes.

The transformations that are safe to apply also compound in a specific order. Percent-encoding must be normalized before paths are compared, dot-segments must be removed before the path is compared, and case folding of the host must happen before the origin is used as a key. Applying them in the wrong order produces intermediate strings that are not equivalent to any canonical form, and any deduplication keyed on those intermediates inherits the error. The ordering is fixed by the grammar, so it does not need to be discovered, only respected.