Dear Maintainer,

Debian installs sharkdp's fd as /usr/bin/fdfind and bat as /usr/bin/batcat, because fdclone has /usr/bin/fd and bacula-console-qt has /usr/sbin/bat (Policy 10.1).
The renames stay: #1051647 (please ship a fd binary) is wontfix since 2026-09-01, and forky still ships /usr/bin/batcat after #1029096.
command-not-found reads only the Contents index, so a person who types `fd` is told to install fdclone, and `bat` offers bacula-console-qt:

    $ fd
    Command 'fd' not found, but can be installed with:
    sudo apt install fdclone

The attached patch reads a small table in the data directory, /usr/share/command-not-found/renamed-commands, with four fields: the command, the package, the name Debian installs it as, and "first" or "after".
It names the renamed package with the name to run, before or after the packages that have the command itself, and those stay listed:

    $ fd
    Command 'fd' not found, but can be installed with:
    sudo apt install fd-find  # run it as 'fdfind'
    sudo apt install fdclone
    $ ts
    Command 'ts' not found, but can be installed with:
    sudo apt install moreutils
    sudo apt install task-spooler  # run it as 'tsp'

A command with no row is advised exactly as before.
A row whose package the database does not have is not offered.
When the renamed program is already installed, the message says so in its place.
When the table cannot be read (missing, unreadable, or a broken row), one line says so with the way to restore it, and the command is advised as without it.

The table has nine rows, each resting on the package's own README.Debian or changelog.
First: antlr (runantlr), bat (batcat), cl (iraf's irafcl) and fd (fdfind).
After the packages that have the name: cal (ccal), spline (aspline), ts (tsp), wipe (lamwipe) and xsd (xsdcxx).
A script makes it from forky's Contents, Packages and popularity contest; the popularity contest decides first or after (more installations than every package that has the name, or fewer).

Tests: nine new ones beside the existing ones; six of them fail on 23.04.0-3, and all 21 pass with the patch, pyflakes clean.
The existing output tests now read the source tree's data directory, which holds the table.
In a Debian testing container, in bash, zsh and fish (interactive and in a pty session), `fd` and `bat` offered fdclone and bacula-console-qt with 23.04.0-3, and fd-find and bat first with the patch.
`ts` and `cal` keep moreutils and ncal first and now also name task-spooler and ccal.
300 sampled commands and 23 words without a row gave byte-identical output before and after.

This work was done with AI assistance (Claude Opus 5.5), directed and reviewed by me.

Daniel Campos Ramos