Compléter la saisie dans une barre de recherche

"""
Réordonner les suggestions avec ce sur quoi les gens ont réellement cliqué.

Niveau N1. L'arbre de préfixes de N0 classe les candidats par la fréquence à
laquelle un terme est cherché. Ce compte dit ce que les gens ont cherché, pas
ce qu'ils ont pris une fois la liste ouverte. Les clics disent la seconde
chose, et ils sont déjà dans les journaux.

Le modèle est un comptage, pas un gradient : pour chaque préfixe qui a été
frappé un jour, combien de fois chaque suggestion a été choisie. Il
s'entraîne en une passe sur le journal et se relit par des lectures de
dictionnaire, au plus une par longueur de préfixe pour chaque candidat, sur
une saisie dont la longueur comptée est plafonnée.

Les candidats arrivent en argument : ce niveau réordonne une liste, il ne la
retrouve pas.
"""

import unicodedata

# Categories M* are the accents NFKD detaches; Cf holds the invisible characters.
DROPPED = {"Mn", "Mc", "Me", "Cf"}
# NFKD has already turned non-breaking spaces into plain ones; these are the
# other spaces. The final sigma is folded by hand: JavaScript keeps it.
FOLD = str.maketrans("\t\n\v\f\rς", "     σ")

# Only the first characters of a query are counted. A pasted paragraph would
# otherwise store one key per prefix, each a copy of the prefix: the memory
# grows with the square of its length, and so does the lookup.
MAX_TYPED = 64


def normalise(text: str) -> str:
    """Same folding as the prefix tree, so both rungs agree on what was typed."""
    # Upper then lower case folds "ß" into "ss", the same way in both languages.
    # "ẞ" is the capital of "ß" and upper-casing leaves it alone; written as
    # "ß" first, the pair folds to "ss" on both sides.
    folded = unicodedata.normalize("NFKD", text.replace("\u1e9e", "ß")).upper().lower().translate(FOLD)
    kept = "".join(c for c in folded if unicodedata.category(c) not in DROPPED)
    return " ".join(word for word in kept.split(" ") if word)


def learn(clicks) -> dict:
    """
    Count clicks from pairs of (what was typed, which suggestion was clicked).

    One click teaches something about every prefix of what was typed, from the
    first letter on: whoever chose "chaussettes de sport" after typing "chau"
    also tells us what to show at "c" and at "cha". The empty prefix is left
    out on purpose: counted, one click made under any query at all would move
    its term to the top of every other query.

    Nothing here decays and nothing is windowed: a term that was clicked a lot
    two years ago keeps its lead for good.
    """
    model: dict = {}
    for typed, term in clicks:
        typed = normalise(typed)[:MAX_TYPED]
        for length in range(1, len(typed) + 1):
            key = (typed[:length], term)
            model[key] = model.get(key, 0) + 1
    return model


def _evidence(model: dict, prefix: str, term: str) -> int:
    """
    Clicks recorded for the longest prefix of the query that saw this term.

    Backing off matters: a rare prefix has too few clicks of its own, but it
    shares its first letters with past queries that do. The longer
    the matching prefix, the more specific the evidence, hence the weight.
    """
    for length in range(len(prefix), 0, -1):
        clicked = model.get((prefix[:length], term), 0)
        if clicked:
            return clicked * (length + 1)
    return 0


def rerank(model: dict, prefix: str, candidates, limit: int = 5) -> list[str]:
    """
    Sort candidates by past clicks, keeping their incoming order as tie-break.

    Candidates arrive ordered by search frequency, as the previous rung left
    them. A term nobody ever clicked keeps that order.

    What that does not make it is safe on a thin log. Clicks are counted, not
    weighed: one click recorded under "c" puts its term at the top of every
    query that starts with a "c", ahead of terms drawn from thousands of
    searches. And the clicks come from the list this very ranking produced —
    the top suggestions get clicked because they are at the top, and the count
    then hardens the order it was meant to correct.
    """
    prefix = normalise(prefix)[:MAX_TYPED]
    ranked = sorted(
        enumerate(candidates),
        key=lambda pair: (-_evidence(model, prefix, pair[1]), pair[0]),
    )
    return [term for _, term in ranked[:limit]]

/**
 * Réordonner les suggestions avec ce sur quoi les gens ont réellement cliqué.
 *
 * Niveau N1. L'arbre de préfixes de N0 classe les candidats par la fréquence à
 * laquelle un terme est cherché. Ce compte dit ce que les gens ont cherché, pas
 * ce qu'ils ont pris une fois la liste ouverte. Les clics disent la seconde
 * chose, et ils sont déjà dans les journaux.
 *
 * Le modèle est un comptage, pas un gradient : pour chaque préfixe qui a été
 * frappé un jour, combien de fois chaque suggestion a été choisie. Il
 * s'entraîne en une passe sur le journal et se relit par des lectures de
 * dictionnaire, au plus une par longueur de préfixe pour chaque candidat, sur
 * une saisie dont la longueur comptée est plafonnée.
 *
 * Les candidats arrivent en argument : ce niveau réordonne une liste, il ne la
 * retrouve pas.
 */

// Only the first characters of a query are counted. A pasted paragraph would
// otherwise store one key per prefix, each a copy of the prefix: the memory
// grows with the square of its length, and so does the lookup.
export const MAX_TYPED = 64;

/** Same folding as the prefix tree, so both rungs agree on what was typed. */
export function normalise(text) {
  // Upper then lower case folds "ß" into "ss", the same way in both languages,
  // and the final sigma is folded by hand. \p{M} holds the accents NFKD
  // detaches, \p{Cf} the invisible characters; NFKD has already turned
  // non-breaking spaces into plain ones.
  // "ẞ" is the capital of "ß" and upper-casing leaves it alone; written as
  // "ß" first, the pair folds to "ss" on both sides.
  const folded = text.replace(/\u1e9e/g, 'ß').normalize('NFKD').toUpperCase().toLowerCase().replace(/ς/g, 'σ');
  const kept = folded.replace(/[\p{M}\p{Cf}]/gu, '').replace(/[\t\n\v\f\r]/g, ' ');
  return kept.split(' ').filter(Boolean).join(' ');
}

// A map key has to be a single value. A tab never occurs inside a normalised
// prefix, since normalise turns it into a space, so the first tab splits the key.
const key = (prefix, term) => `${prefix}\t${term}`;

/**
 * Count clicks from pairs of [what was typed, which suggestion was clicked].
 *
 * One click teaches something about every prefix of what was typed, from the
 * first letter on: whoever chose "chaussettes de sport" after typing "chau"
 * also tells us what to show at "c" and at "cha". The empty prefix is left out
 * on purpose: counted, one click made under any query at all would move its
 * term to the top of every other query.
 *
 * Nothing here decays and nothing is windowed: a term that was clicked a lot two
 * years ago keeps its lead for good.
 */
export function learn(clicks) {
  const model = new Map();
  for (const [typed, term] of clicks) {
    const prefix = normalise(typed).slice(0, MAX_TYPED);
    for (let length = 1; length <= prefix.length; length += 1) {
      const at = key(prefix.slice(0, length), term);
      model.set(at, (model.get(at) ?? 0) + 1);
    }
  }
  return model;
}

/**
 * Clicks recorded for the longest prefix of the query that saw this term.
 *
 * Backing off matters: a rare prefix has too few clicks of its own, but it
 * shares its first letters with past queries that do. The longer
 * the matching prefix, the more specific the evidence, hence the weight.
 */
function evidence(model, prefix, term) {
  for (let length = prefix.length; length >= 1; length -= 1) {
    const clicked = model.get(key(prefix.slice(0, length), term)) ?? 0;
    if (clicked) return clicked * (length + 1);
  }
  return 0;
}

/**
 * Sort candidates by past clicks, keeping their incoming order as tie-break.
 *
 * Candidates arrive ordered by search frequency, as the previous rung left
 * them. A term nobody ever clicked keeps that order.
 *
 * What that does not make it is safe on a thin log. Clicks are counted, not
 * weighed: one click recorded under "c" puts its term at the top of every query
 * that starts with a "c", ahead of terms drawn from thousands of searches. And
 * the clicks come from the list this very ranking produced — the top
 * suggestions get clicked because they are at the top, and the count then
 * hardens the order it was meant to correct.
 */
export function rerank(model, prefix, candidates, limit = 5) {
  const typed = normalise(prefix).slice(0, MAX_TYPED);
  const scored = candidates.map((term, rank) => [evidence(model, typed, term), rank, term]);
  scored.sort((a, b) => b[0] - a[0] || a[1] - b[1]);
  return scored.slice(0, limit).map(([, , term]) => term);
}