Home › Sorting, searching & vector search › Web crawling
algorithm low

URL normalization

Problem Programs that collect links from many places (crawlers, feed readers, analytics pipelines, link checkers) see one page under many spellings, and must decide whether two URL strings name the same resource before storing or fetching.

Rewrite a URL to one canonical key, in safe RFC 3986 steps plus lossy, site-dependent ones (tracking parameters, query order, fragments), and keep the original beside the key.

O(URL length) plus O(p log p) to sort p query parameters; about 0.7 us per URL in the toy below (measured)
urlcanonicalizationdedupecrawlingrfc-3986whatwg-url
Overview

HTTP://News.Example.com:80/a/./b/../story?utm_source=x&id=7#top and http://news.example.com/a/story?id=7 are one page. A string compare says two. Normalization maps every spelling to one key through a ladder of rewrites, ordered from provably safe (RFC 3986) to heuristic (drop tracking parameters, sort the query). Each rung removes more duplicates and risks merging distinct pages.

Key facts

Use when

  • Crawler and feed-reader "seen" sets, and the first dedupe layer before content fingerprints (simhash, minhash).
  • Analytics and attribution: group page views that differ only by campaign tags.
  • Cache and CDN keys, and bookmark or browser-history merging.
  • Security allow/deny lists and SSRF checks: compare the form the HTTP client will actually fetch.

Avoid when

  • The server treats query order, case or trailing slash as meaningful (some apps, signed URLs): use only the safe rungs.
  • You can ask the site: rel="canonical" or a redirect is better evidence than a guess.

Deep dive

How it works

In: one URL string and a rule set (tracking names, sort on/off) · Out: a canonical key string, or "cannot decide" · State: none (a key table, original to key, lives outside) · Cost: O(length) plus O(p log p) for p query parameters

  1. Split into scheme, authority (userinfo, host, port), path, query, fragment. Backslash is / for http(s) in browsers (WHATWG).
  2. Case (RFC 3986 6.2.2.1): lowercase scheme and host; upper-case hex digits in %xx. Path and query stay case-sensitive.
  3. Percent-encoding (6.2.2.2): decode %xx only for unreserved characters (letters, digits, -._~). Never decode reserved ones: %2F is not /. Encode raw spaces and non-ASCII bytes as UTF-8.
  4. Dot segments (6.2.2.3): apply the RFC 3986 section 5.2.4 algorithm; /a/b/../c/./d becomes /a/c/d.
  5. Scheme rules (6.2.3): drop :80 for http and :443 for https (and an empty :); an empty path becomes /.
  6. Hosts, the WHATWG way: IDN labels go through UTS #46 and Punycode (münchen.de becomes xn--mnchen-3ya.de, RFC 3492); IPv4 forms like 0x7f.1 become 127.0.0.1; IPv6 is compressed. Do this with a real parser (below).
  7. Lossy rungs (switchable): drop the fragment (never sent to the server); drop tracking parameters; sort remaining key=value pairs; drop an empty ?.
  8. Store both: key to dedupe on, original URL to fetch and display. Treat rel="canonical" and redirect targets as evidence that adds an alias, not as a rewrite rule.

Code

pub struct Opts { pub drop_exact: &'static [&'static str], pub drop_prefix: &'static [&'static str], pub sort_query: bool }
pub const TRACKING: Opts = Opts { drop_exact: &["fbclid", "gclid", "dclid", "msclkid", "yclid", "mc_eid", "mc_cid"],
                                  drop_prefix: &["utm_"], sort_query: true };
pub const RFC_ONLY: Opts = Opts { drop_exact: &[], drop_prefix: &[], sort_query: false };

/// Canonical key for an http(s) URL, or None when this toy cannot decide (other scheme, non-ASCII host, bad port).
pub fn normalize(url: &str, o: &Opts) -> Option<String> {
    let url = url.trim();
    let url = url.split('#').next()?; // fragment: never sent to the server
    let (scheme, rest) = url.split_once("://")?;
    let scheme = scheme.to_ascii_lowercase();
    let default_port = match scheme.as_str() { "http" => "80", "https" => "443", _ => return None };
    // WHATWG: for special schemes '\' means '/'
    let rest = rest.replace('\\', "/");
    let (before_q, query) = match rest.split_once('?') { Some((a, q)) => (a.to_string(), Some(q.to_string())), None => (rest, None) };
    let (auth, path) = match before_q.find('/') { Some(i) => (&before_q[..i], &before_q[i..]), None => (&before_q[..], "/") }; // empty path -> "/"
    let (userinfo, hostport) = match auth.rsplit_once('@') { Some((u, h)) => (Some(u), h), None => (None, auth) };
    let (host, port) = match hostport.find(']') { // IPv6 literal: "[::1]:80"
        Some(e) => (&hostport[..=e], hostport[e + 1..].trim_start_matches(':')),
        None => hostport.rsplit_once(':').unwrap_or((hostport, "")) };
    if host.is_empty() || !host.is_ascii() || !port.bytes().all(|b| b.is_ascii_digit()) { return None; }
    let mut out = format!("{scheme}://");
    if let Some(u) = userinfo { out += &pct(u); out.push('@'); }
    out += &host.to_ascii_lowercase();
    if !port.is_empty() && port != default_port { out.push(':'); out += port; } // ":" or ":80" dropped
    out += &remove_dot_segments(&pct(path));
    if let Some(q) = query {
        let mut pairs: Vec<String> = q.split('&').filter(|p| !p.is_empty()).map(pct).filter(|p| {
            let k = p.split('=').next().unwrap().to_ascii_lowercase();
            !(o.drop_exact.contains(&k.as_str()) || o.drop_prefix.iter().any(|x| k.starts_with(x)))
        }).collect();
        if o.sort_query { pairs.sort(); } // by bytes: key first, then value
        if !pairs.is_empty() { out.push('?'); out += &pairs.join("&"); }
    }
    Some(out)
}
/// RFC 3986 6.2.2.1-2: decode %XX of unreserved chars, upper-case other hex; encode raw non-ASCII/space bytes.
/// Never decodes reserved characters: "%2F" stays "%2F" ("/" and "%2F" name different resources).
fn pct(s: &str) -> String {
    let (b, mut o, mut i) = (s.as_bytes(), String::with_capacity(s.len()), 0);
    let hex = |c: u8| (c as char).to_digit(16);
    while i < b.len() {
        let c = b[i];
        if c == b'%' && i + 2 < b.len() && hex(b[i + 1]).is_some() && hex(b[i + 2]).is_some() {
            let v = (hex(b[i + 1]).unwrap() * 16 + hex(b[i + 2]).unwrap()) as u8;
            if v.is_ascii_alphanumeric() || b"-._~".contains(&v) { o.push(v as char) } else { o += &format!("%{v:02X}") }
            i += 3;
        } else if c >= 0x80 || c <= b' ' || c == 0x7f { o += &format!("%{c:02X}"); i += 1; }
        else { o.push(c as char); i += 1; }
    }
    o
}
/// RFC 3986 5.2.4 on an absolute path (starts with '/').
fn remove_dot_segments(p: &str) -> String {
    let segs: Vec<&str> = p.split('/').skip(1).collect();
    let mut out: Vec<&str> = Vec::new();
    for (i, s) in segs.iter().enumerate() {
        let last = i + 1 == segs.len();
        match *s {
            "." => if last { out.push("") },
            ".." => { out.pop(); if last { out.push("") } }
            s => out.push(s),
        }
    }
    format!("/{}", out.join("/"))
}
fn main() {
    let n = |u: &str| normalize(u, &RFC_ONLY).unwrap();
    // RFC 3986 6.2.2 and 6.2.3 examples (http instead of the unknown "example:" scheme)
    assert_eq!(n("HTTP://www.EXAMPLE.com/"), "http://www.example.com/");
    assert_eq!(n("http://a/./b/../b/%63/%7bfoo%7d"), "http://a/b/c/%7Bfoo%7D");
    for u in ["http://example.com", "http://example.com/", "http://example.com:/", "http://example.com:80/"] {
        assert_eq!(n(u), "http://example.com/");
    }
    assert_eq!(n("HTTP://www.Example.com:80/a/./b/../c/%7euser"), "http://www.example.com/a/c/~user");
    assert_eq!(n("http://a/b/c/./../../g"), "http://a/g"); // RFC 5.2.4 example
    assert_eq!(n("http://a/b/.."), "http://a/");
    assert_eq!(n("http://a\\b\\c"), "http://a/b/c");
    assert_eq!(n("http://[::1]:80/"), "http://[::1]/");
    assert_eq!(n("http://a/x%2fy%2Fz"), "http://a/x%2Fy%2Fz"); // reserved: NOT decoded, hex upper-cased
    assert_eq!(n("http://a/?"), "http://a/"); // lossy: RFC says "?" is significant
    // lossy step: tracking params and query order
    let t = |u: &str| normalize(u, &TRACKING).unwrap();
    assert_eq!(t("https://a.com/p?utm_source=x&b=2&fbclid=1&a=1#top"), "https://a.com/p?a=1&b=2");
    assert_eq!(t("https://a.com/p?UTM_Medium=m"), "https://a.com/p");
    assert_eq!(t("https://a.com/p?id=1&id=2"), t("https://a.com/p?id=2&id=1")); // repeated keys: sorted too
    // idempotence: normalise(normalise(u)) == normalise(u)
    for u in ["HTTP://www.Example.com:80/a/./b/../c/%7euser?z=1&utm_x=2&a=%7e", "http://a/x%252Fy", "http://a/%zz%25?&&a", "http://a/b c/é?q=ü"] {
        let (once, twice) = (t(u), t(&t(u)));
        assert_eq!(once, twice, "{u}");
    }
    let urls = ["HTTP://www.Example.com:80/a/./b/../c/%7euser?utm_source=x&b=2&a=1#f", "https://news.example.org/2026/10/story?id=7&fbclid=abc",
                "http://a.b/c/d/e/../../f?q=%c3%a9&gclid=1", "https://x.y:8443/p%2Fq/?s=1&r=2"];
    let t0 = std::time::Instant::now();
    let mut sink = 0usize;
    for i in 0..1_000_000 { sink += t(urls[i % 4]).len(); }
    let s = t0.elapsed().as_secs_f64();
    println!("{:.2} M URLs/s ({:.0} ns each, sink {sink})", 1.0 / s, s * 1e3);
}

Compiled and run (Rust stable, aarch64-apple-darwin): asserts pass, including the RFC 3986 6.2.2/6.2.3 examples, the section 5.2.4 example, %2F kept, and idempotence. It is a toy, not a WHATWG parser: it handles http(s) only, ASCII hosts only, does not decode +, leading-zero ports or IP-literal forms, and returns None instead of guessing. Use the crates below for real input.

Complexity and constants

  • One pass over the string, a few allocations; sorting p parameters is O(p log p), p is usually under 10.
  • Measured on this Mac (Apple M4 Pro), release build, one thread, 4 mixed URLs of 40-70 bytes, 1M calls, 3 runs: 650-830 ns per URL (1.2-1.5 M URLs/s). url::Url::parse 2.5.8 alone (no tracking drop or sort): about 235 ns on the same URLs.
  • Cost drivers: String allocations in the toy, the query-pair Vec, UTS #46 for non-ASCII hosts.

Efficiency

  • Cost: about 0.7 us and a few allocations per URL for the toy (measured above); a key is 40-100 bytes as a string, 16 bytes as a 128-bit hash. Bound: CPU and allocator, never I/O; far below one HTTP fetch.
  • Levers:
    • normalize once at ingest, store the key — avoids repeating work at every dedupe check (no figure) — always
    • hash the key (64-128 bit) in the seen-set, optionally behind a Bloom filter — fixed bytes per URL instead of the string (arithmetic, no benchmark) — billions of URLs
    • skip work on already-canonical input (ASCII, lowercase host, no %, . or #) — avoids every allocation in the toy (not measured) — feeds that emit clean URLs
    • cache the per-host verdict "this parameter changes content or not" — one probe per host instead of per URL — large sites with unknown parameters
  • Naive → standard → state of the art:
    • raw string equality · cheap, misses most duplicates
    • RFC syntax and scheme rules, tracking list, sorted query · about 1 us per URL
    • plus per-host learned parameter rules, canonical/redirect evidence, content fingerprints (simhash) · extra fetches, far fewer false merges

Implementation notes

  • Normalize after resolving relative links against the page's base URL (<base href> included), not before.
  • Order: percent-normalize, then remove dot segments (WHATWG treats .%2e, %2e. and %2e%2e as ..).
  • Keep a rule table per host: parameters to drop, www. equivalence, forced https. Learn it from data: two URLs differing in one parameter whose fetched bodies match (fingerprint) are candidates.
  • News and feed harvesters: key the story on feed GUID first, then URL key, then content fingerprint. The same article arrives via tracking tags, amp./m. hosts and http/https; map those with rel="canonical" evidence from the fetched page, not with host-prefix guessing.
  • Check robots rules and feed the frontier with the normalized form.

Pitfalls

  • Sorting or dropping parameters where order or the name matters (?page=2, ?id=, signed URLs, q). Whitelist drops; never drop "everything unknown".
  • Removing a trailing slash or www.: on many servers /a and /a/ differ (RFC 3986 6.2.4 only licenses it after the server redirects between them).
  • Decoding %2F, %3F, %23, %26, %3D: changes the meaning. Decode only unreserved characters.
  • http to https merging without checking that both serve the same body; same for mobile or AMP hosts.
  • A browser does not behave like RFC 3986: the url crate (WHATWG) leaves %7e and lowercase %2f as written, while RFC 3986 asks for ~ and %2F. Security checks must use the parser your fetcher uses; a checker and a fetcher that disagree can open SSRF bypasses.
  • Session ids in paths (;jsessionid=) and index.html-style defaults: site-specific, needs per-host rules.
  • Not idempotent: decoding twice (%252F must stay %252F) or a rule that fires only on the second pass. Test norm(norm(u)) == norm(u) on a corpus.
  • Python's urllib.parse.urlsplit/urlunsplit round trip normalizes only the scheme case in my check (host case, :80, dot segments and %7e stayed); it is a splitter, not a normalizer.

Variants and alternatives

Safe-only RFC 3986 normalizationwhen wrong merges are worse than missed duplicates (security, caches).
Canonical link / redirect followingsite-declared truth; Google ranks redirects and rel="canonical" as strong signals, sitemaps as weak, for choosing the canonical URL. Costs a fetch.
Content fingerprints (simhash, winnowing)catch what URL rules cannot: the same article on two domains.Record linkagededupe by metadata (title, date, author) instead of address.

In production

Browsers' URL parsers (WHATWG), Scrapy (w3lib canonicalize_url for request fingerprints), search crawlers (Google documents its canonical signals), ClearURLs and browser tracking-protection lists for parameter names, HTTP caches.

Implementations

namelangrepoinstallverdictlicencehealthas_ofnotes
urlRustservo/rust-urlcargo add url————WHATWG parser; parse, then normalize and strip params yourself
idnaRustservo/rust-urlcargo add idna————UTS #46 and Punycode; used by url
w3libPythonscrapy/w3libpip install w3lib————canonicalize_url: lowercase host, sort query, drop fragment, resolve dot segments (2.5.0 docs)
url-normalizePythonniksite/url-normalizepip install url-normalize————RFC-style normalization, IDN, parameter allowlists
ClearURLs rulesJSONClearURLs/Rulescurl -O https://raw.githubusercontent.com/ClearURLs/Rules/master/data.min.json————community list of tracking parameter patterns (utm_*, fbclid, gclid, msclkid, mc_eid, ...)

Sources

  • Berners-Lee, Fielding, Masinter, Uniform Resource Identifier (URI): Generic Syntax, RFC 3986 (STD 66), 2005, section 6. rfc
  • WHATWG, URL Standard (living standard). spec
  • Costello, Punycode, RFC 3492, 2003. rfc · Unicode, UTS #46: IDNA Compatibility Processing. report
  • Ohye, Kupke, The Canonical Link Relation, RFC 6596, 2012. rfc
  • Google Search Central, How to specify a canonical URL with rel="canonical" and other methods. docs
  • Lee, Kim, Hong, On URL Normalization, ICCSA 2005, LNCS 3481, pp. 1076-1085. doi
  • Google Analytics Help, Collect campaign data with custom URLs (the utm_* parameters). docs
  • scrapy/w3lib, canonicalize_url documentation. docs

Used by

same origin policy · plannedOrigin model, CORS, cookies SameSite and site isolation boundaries in browsers
url frontier · plannedPrioritised per-host queues with politeness delays for crawling
vulnerability advisory matching · plannedMatching package versions against advisory databases (OSV, NVD, distro feeds) with ecosystem-specific rules

Systems (9):

web crawlerweb archivesse gatewayurl reputationaffiliate trackingsales intelligencesocial media managementseo platformurl shortener

Alternatives and related

Robots exclusion protocolOperators of automated clients (search indexers, feed aggregators, web archivers, price monitors, link checkers) must decide, before each request, whether a site's owner permits their program to fetch that URL.SimHashA system that ingests many text documents (web pages, feed items, tickets, listings) must spot copies that differ only in small edits, in constant space and time per document, without comparing every pair.Near-duplicate detection with MinHash LSHTeams holding a huge collection of documents, web pages or sequences must find and remove near-identical items, which repeat content and bias what is learned or indexed, without comparing every pair.
winnowing fingerprints · plannedK-gram winnowing fingerprints (MOSS) for plagiarism detection
record linkage · plannedProbabilistic record matching (Fellegi-Sunter) with blocking for patient or entity indexes
HTTP caching semanticsA client, proxy or edge server holds a copy of a fetched resource and must decide, for each new request, whether it may reuse the copy, must ask the origin whether it changed, or must refetch it.Bloom filterSystems waste disk reads or lookups on keys that are not present (LSM-tree tables, joins, caches). This answers "definitely absent" cheaply in a tiny amount of memory.