Dater l'entrée d'une entité dans le Knowledge Graph de Google, et le codec original des MID

Un MID récent s'écrit /g/11 suivi de huit caractères, par exemple /g/11k4jj7mq1. Ces caractères viennent d'un alphabet de 32 symboles, 0123456789bcdfghjklmnpqrstvwxyz_, sans voyelles pour qu'aucun mot ne s'y forme. Le premier 1 désigne l'espace /g/ ; le reste, lu en base 32, donne un nombre compris entre 2⁴⁰ et 2⁴¹ pour tous les /g/11…. C'est ce nombre qui grandit avec le temps.

Nous avons converti en nombres les MID de 95 647 entités datées par Wikidata, réparties en dix familles : événements, albums, films, jeux, élections, compétitions sportives, organisations, produits, lieux créés et lieux ouverts. Chaque famille a été datée à partir des neuf autres seulement, et toutes suivent la même courbe. À l'année près, l'estimation est juste pour 93 % des événements imprévisibles, 81 % des albums, 76 % des films, 67 % des jeux et 46 % des organisations.

Précision par tranche

Au mois dans presque toutes les tranches, jamais sous la semaine : un événement reçoit en général son MID une à deux semaines après sa survenue. La zone /g/11k-/g/11n, partagée par deux séries, reste la moins sûre.

4 662 événements datés sans eux-mêmes, avec le MID donné par Wikidata ou celui que Google affiche aujourd'hui, pondérés selon la situation réelle des MID (bloc de 33 millions avec ou sans référence). Sur les MID affichés par Google, l'outil est à ±3 mois dans 82 % des cas en /g/11k-n et 93 % en /g/11p-t.

Au bord du compteur. Les références s'arrêtent au 22 octobre 2026. Un identifiant attribué après cette date, donc en pratique à partir de novembre 2026, tombe au-delà : l'outil le date en prolongeant le compteur. En recalant l'outil à des dates passées, nous avons mesuré que, pour la série principale, il reste à ±3 mois pour 98 à 100 % des événements des deux mois qui suivent (ici jusqu'à fin décembre 2026), puis pour 82 % au troisième mois (janvier 2027). Pour la série lente, rien ne signale qu'elle entre dans un nouveau bloc : la bonne date figure dans la réponse, souvent en seconde position, jusqu'à ce que les références soient mises à jour.

La série lente de /g/11k à /g/11p

Une première série a rempli /g/11k à /g/11p en 2020-2022. Une seconde, plus lente, occupe depuis fin 2022 les plages qu'elle avait laissées libres : ce sont les points orange du graphique, deux à cinq ans au-dessus des points bleus. Partie de /g/11k, elle est entrée dans /g/11p fin septembre 2026. Un identifiant isolé de cette zone peut donc dater de 2021 comme de 2026.

Dates des références de chaque série, du 10^e au 90^e percentile.

Les deux séries se mélangent rarement dans un même bloc de 33 millions d'identifiants : 837 blocs sur les 891 qui contiennent au moins deux références datées appartiennent à une seule série. L'outil reconnaît la série au bloc de l'identifiant ou à ses voisins. Quand les blocs voisins se contredisent, il place la série lente en premier et donne la date de la série rapide en second : la série lente était la bonne pour 86 % des événements de référence dans ce cas. Quand la série rapide est déduite des voisins, il donne aussi la date de la série lente, car celle-ci entre sans prévenir dans des blocs restés libres.

Ce que code chaque caractère

Le code de Google lit un MID comme un entier de 64 bits en trois parties : 2 bits de version, toujours à 0, 3 bits pour l'espace de noms (le « graph ID » du code), puis 59 bits de valeur. La chaîne s'écrit avec le préfixe de l'espace (/g/), un caractère qui porte la version et l'espace, puis la valeur en base 32 sans zéro de tête, dans l'alphabet que le code appelle « munch ». C'est pour cela que tous les /m/ commencent par 0 et tous les /g/ par 1 : ce premier chiffre n'appartient pas au compteur.

Pour /g/11b6377dzp : 2⁵⁹ pour l'espace /g/, plus 1b6377dzp lu en base 32 (1 449 659 708 373), soit 576462201963131861. C'est l'entier que Valentin Pletzer avait relevé en 2019 dans une URL de recherche Google (ibp=tpf;cl_tp:srp,mid:576462201963131861). Ce MID désigne « Public prosecutor's office ».

Le code de Google, reconstitué

Le fichier source metaweb/util/mid/mid.cc n'est pas public. Son chemin rappelle l'origine du codec : Metaweb, la société qui avait créé Freebase avant d'être rachetée par Google en 2010. Nous avons mis la main sur le binaire du codec original et l'avons reconstruit en C++. La logique, les constantes, les messages et les numéros de ligne sont ceux du binaire. Les noms de fonctions et de variables sont les nôtres : le binaire n'en contient plus.

// metaweb/util/mid/mid.cc                                     // reconstitution : la logique est celle du binaire, les noms sont les nôtres
static const char kMunch[] = "0123456789bcdfghjklmnpqrstvwxyz_";
static const string_view kPrefix[8] = {"/m/", "/g/", "/t/", "/x/", "/n/", "/p/", "/r/", "/s/"};
static const uint64_t kMaxValue = 0x7ffffffffffffff;           // 2^59 - 1

uint64_t MakeMid(int graph, uint64_t value) {
  if (value >> 59) {
    VLOG(1) << "Mid exceeds max size 0x" << hex << kMaxValue   // ligne 226 du fichier source
            << " for namespace " << kPrefix[graph] << ": 0x" << value;
    return -1;
  }
  if (graph == -1) return -1;
  return value | (uint64_t(graph) << 59);
}

bool ParseMunch(string_view s, uint64_t* out) {
  if (s.size() > 13) return false;
  if (s.size() == 13 && kMunchValue[s[0]] > 15) return false;  // dépasserait 64 bits
  uint64_t v = 0;
  for (char c : s) {
    int d = kMunchValue[c];                                    // -1 hors alphabet
    if (d < 0) return false;
    v = (v << 5) + d;
  }
  *out = v;
  return true;
}

uint64_t GuidToMid(string_view guid) {
  if (guid.size() != 32) return -1;
  uint64_t hi = HexToU64(guid.substr(0, 16)), lo = HexToU64(guid.substr(16, 16));
  uint64_t graph = hi - 0x9202a8c04000641f;                    // comparaison non signée
  if (lo < 0x8000000000000000 || lo > 0x80000003ffffffff || graph >= 8) return -1;
  return MakeMid(graph, lo & 0x3ffffffff);                     // 34 bits de valeur
}

uint64_t ParseMid(string_view s) {
  if (s.size() >= 4 && s[0] == '/' && s[2] == '/') {
    int graph;
    switch (s[1]) {
      case 'm': graph = 0; break;   case 'g': graph = 1; break;
      case 't': graph = 2; break;   case 'x': graph = 3; break;
      case 'n': graph = 4; break;   case 'p': graph = 5; break;
      case 'r': graph = 6; break;                              // réservé, jamais observé
      default: return -1;                                      // 's' compris, sans message
    }
    char c0 = s[3];
    if ((c0 & 0x78) != 0x30) return -1;                        // '0' à '7' : version 0
    uint64_t value;
    if (c0 == '7' || !ParseMunch(s.substr(4), &value)) {
      VLOG(1) << "Invalid mid characters: " << s;              // ligne 256 du fichier source
      return -1;
    }
    uint64_t mid = MakeMid(kMunchValue[c0], value);
    if (mid == -1) return -1;
    return ((mid >> 59) & 7) == graph ? mid : -1;              // la lettre et le chiffre doivent concorder
  }
  if (StartsWith(s, "/guid/")) return GuidToMid(s.substr(6));
  if (StartsWith(s, "#"))      return GuidToMid(s.substr(1));
  return -1;
}

string MidToString(uint64_t mid) {
  if (mid == 0) return "/m/0";
  uint64_t top = mid >> 59;                                    // version + graphe
  if (top >= 7) return "";                                     // /s/ ou version non nulle
  char buf[13];
  return StrCat(kPrefix[top], kMunch[top], MunchDigits(mid & kMaxValue, buf)); // base 32 sans zéro de tête
}

VLOG(1) est une lecture du binaire : avant d'écrire, le code teste un niveau de journal, mais la macro exacte n'est pas connue. kMunchValue est la table inverse de l'alphabet, MunchDigits écrit les chiffres de droite à gauche dans un tampon de 13 caractères.

Deux messages, et beaucoup de silences

Le fichier ne contient que deux messages d'erreur : « Mid exceeds max size 0x… for namespace … » à la ligne 226, quand une valeur dépasse 59 bits, et « Invalid mid characters: » à la ligne 256, quand un caractère sort de l'alphabet. Un préfixe inconnu, un /s/ ou une lettre qui ne concorde pas avec le premier chiffre renvoient −1 sans rien écrire au journal.

Tout le reste est de la donnée : l'alphabet, la table des huit préfixes, la table inverse, et les deux écritures d'un GUID Freebase, /guid/ et #.