Skip to content

An open source design system that's fully customizable and agent ready

TypeScript
4.3 KB
Raw Blame
// Copyright (c) Meta Platforms, Inc. and affiliates.

/**
 * @file Similar-page ranking for the docsite 404 experience.
 * @input The missing pathname and canonical sitemap paths and page titles
 * @output Up to three high-confidence pages ordered by similarity
 * @position Pure matching logic behind the DidYouMean component
 */

const MAX_INPUT_LENGTH = 128;
const MAX_NORMALIZED_DISTANCE = 0.34;

export interface PageCandidate {
  path: string;
  title: string;
}

interface NormalizedPath {
  full: string;
  leaf: string;
}

interface Comparison {
  distance: number;
  ratio: number;
  length: number;
}

interface RankedPage {
  page: PageCandidate;
  matchTier: number;
  comparison: Comparison;
}

function decodePath(path: string): string {
  try {
    return decodeURIComponent(path);
  } catch {
    return path;
  }
}

function normalizeSegment(segment: string): string {
  return segment.toLowerCase().replace(/[^a-z0-9]/g, '');
}

function normalizeWords(value: string): string[] {
  return value
    .toLowerCase()
    .replace(/[’']/g, '')
    .split(/[^a-z0-9]+/)
    .filter(Boolean);
}

function normalizePath(path: string): NormalizedPath {
  const pathname = decodePath(path).split(/[?#]/, 1)[0];
  const segments = pathname
    .split('/')
    .filter(Boolean)
    .map(normalizeSegment)
    .filter(Boolean);

  return {
    full: segments.join('/'),
    leaf: segments.at(-1) ?? '',
  };
}

function levenshteinDistance(a: string, b: string): number {
  if (a === b) {
    return 0;
  }
  if (a.length === 0) {
    return b.length;
  }
  if (b.length === 0) {
    return a.length;
  }

  let previous = Array.from({length: b.length + 1}, (_, index) => index);

  for (let i = 1; i <= a.length; i++) {
    const current = [i];
    for (let j = 1; j <= b.length; j++) {
      current[j] = Math.min(
        current[j - 1] + 1,
        previous[j] + 1,
        previous[j - 1] + (a[i - 1] === b[j - 1] ? 0 : 1),
      );
    }
    previous = current;
  }

  return previous[b.length];
}

function compare(a: string, b: string): Comparison {
  const length = Math.max(a.length, b.length);
  if (length === 0) {
    return {distance: Number.POSITIVE_INFINITY, ratio: 1, length};
  }

  const distance = levenshteinDistance(a, b);
  return {distance, ratio: distance / length, length};
}

function isHighConfidence(comparison: Comparison): boolean {
  const maxDistance = Math.max(1, Math.floor(comparison.length * 0.34));
  return (
    comparison.distance <= maxDistance &&
    comparison.ratio <= MAX_NORMALIZED_DISTANCE
  );
}

export function findSimilarPages(
  pathname: string,
  pages: readonly PageCandidate[],
  limit = 3,
): PageCandidate[] {
  if (pathname.length > MAX_INPUT_LENGTH || limit <= 0) {
    return [];
  }

  const requested = normalizePath(pathname);
  if (!requested.leaf) {
    return [];
  }

  const seen = new Set<string>();
  const ranked: RankedPage[] = [];

  for (const page of pages) {
    if (seen.has(page.path)) {
      continue;
    }
    seen.add(page.path);

    const candidate = normalizePath(page.path);
    if (!candidate.leaf || page.path === pathname) {
      continue;
    }

    const terms = [
      candidate.leaf,
      normalizeSegment(page.title),
      ...normalizeWords(page.title),
    ].filter(Boolean);
    const termComparisons = terms.map(term => compare(requested.leaf, term));
    const fullComparison = compare(requested.full, candidate.full);
    const comparison = [...termComparisons, fullComparison].sort(
      (a, b) => a.ratio - b.ratio || a.distance - b.distance,
    )[0];
    const exactTerm = termComparisons.some(result => result.distance === 0);
    const partialTerm = terms.some(
      term =>
        requested.leaf.length >= 4 &&
        term.length >= 4 &&
        (term.includes(requested.leaf) || requested.leaf.includes(term)),
    );
    const matchTier = exactTerm ? 0 : partialTerm ? 1 : 2;

    if (matchTier === 2 && !isHighConfidence(comparison)) {
      continue;
    }

    ranked.push({page, matchTier, comparison});
  }

  return ranked
    .sort((a, b) => {
      return (
        a.matchTier - b.matchTier ||
        a.comparison.ratio - b.comparison.ratio ||
        a.comparison.distance - b.comparison.distance ||
        a.page.path.length - b.page.path.length ||
        a.page.title.localeCompare(b.page.title)
      );
    })
    .slice(0, limit)
    .map(match => match.page);
}