L'algorithme CVM révolutionnaire résout plus de 40 ans de problèmes de comptage ! Un informaticien lance une pièce de monnaie pour trouver le mot unique pour « Hamlet »

Compter semble simple, mais il est très difficile à mettre en pratique.

Imaginez que vous soyez envoyé dans une forêt tropicale humide vierge pour effectuer un recensement de la faune. Chaque fois que vous voyez un animal, prenez une photo.

L'appareil photo numérique enregistre uniquement le nombre total d'animaux suivis, mais vous êtes intéressé par le nombre d'animaux uniques, mais il n'y a pas de statistiques.

Alors, quelle est la meilleure façon de mettre la main sur cet animal unique ?

À ce stade, vous devez vous dire, commencez à compter à partir de maintenant, et enfin comparez chaque nouvelle espèce de la photo à la liste.

Cependant, cette méthode de comptage courante n'est parfois pas adaptée aux informations pouvant atteindre des milliards d'entrées.

Des informaticiens de l'Institut indien de statistique, UNL, et de l'Université nationale de Singapour ont proposé un nouvel algorithme-CVM.

Il peut se rapprocher du nombre d'éléments différents dans une longue liste et n'a besoin de mémoriser qu'un petit nombre d'éléments.

Adresse papier : https://arxiv.org/pdf/2301.10191

Cet algorithme convient à toute liste dans laquelle un élément apparaît à la fois, comme le texte d'un discours, les biens sur un tapis roulant, ou des voitures sur l'autoroute.

L'algorithme CVM doit son nom aux premières lettres des trois auteurs et a fait des progrès significatifs dans la résolution du « problème des différents éléments ».

Ce problème préoccupe les informaticiens depuis plus de 40 ans.

Cela nécessite un moyen efficace de surveiller un flux d'éléments (dont le nombre total peut dépasser la mémoire disponible) et d'estimer le nombre d'éléments uniques qu'il contient.

Alors, comment l'algorithme CVM résout-il le problème ?

Algorithme CVM pionnier, le secret réside dans la "randomisation"

Supposons que vous écoutiez le livre audio "Hamlet".

Ce drame compte un total de 30557 mots, combien sont différents ?

Pour trouver la réponse, vous pouvez faire une pause pendant l'écoute, écrire chaque mot par ordre alphabétique, puis sauter les mots déjà sur la liste, et enfin, simplement compter chaque mot de la liste.

Cette méthode est réalisable, mais elle teste trop la « mémoire ».

Le chercheur Vinodchandran Variyam a déclaré : « Dans une situation typique de flux de données, il peut y avoir des millions d'éléments à suivre. Vous ne souhaiterez peut-être pas stocker toutes les informations.

Il s'agit d'un serveur cloud où les algorithmes peuvent fournir plus méthodes".

L'astuce est la "randomisation".

Vinodchandran Variyam a aidé à inventer un algorithme CVM pour estimer le nombre d'éléments distincts dans un flux de données

Combien de mots uniques y a-t-il dans "Hamlet" ? Coin Flip Challenge

Retour à "Hamlet", en supposant que votre "mémoire effective" ne peut contenir que 100 mots.

Une fois la lecture audio commencée, vous écrivez les 100 premiers mots que vous entendez et sautez les mots répétés.

Lorsque vous avez fini d'enregistrer 100 mots, il ne vous reste plus qu'à lancer une pièce pour chaque mot –

Tête, gardez le mot. Si c'est le verso, supprimez-le.

Après ce tour préliminaire, il vous restera environ 50 mots différents.

Maintenant, vous passez à ce que l'équipe appelle le premier tour, en continuant à lire Hamlet et en ajoutant de nouveaux mots.

Si vous rencontrez à nouveau un mot qui figure déjà sur la liste, lancez à nouveau la pièce jusqu'à ce que vous ayez 100 mots dans votre tableau blanc en mémoire.

Ensuite, environ la moitié des mots sont à nouveau supprimés au hasard en fonction des résultats de 100 tirages au sort. Le premier tour se termine ici.

Ensuite, entrez dans le deuxième tour du tour 2.

Comme au premier tour, nous allons augmenter la difficulté d'un mot - lorsque vous rencontrez un mot répété, lancez à nouveau la pièce.

La condition est que si c'est une queue, supprimez-la comme avant. Mais si c’est face, lancez à nouveau la pièce. Le mot n'est conservé que lorsqu'il apparaît face pour la deuxième fois.

Une fois le tableau blanc mémoire plein, terminez le tour, puis supprimez à nouveau environ la moitié des mots en fonction des résultats de 100 lancers.

Au tour 3, vous devez lancer une pièce de monnaie trois fois de suite pour tenir un mot.

Au quatrième tour, gardez un mot au recto quatre fois de suite, et ainsi de suite.

Enfin, au kième tour, vous écouterez l'intégralité de la pièce "Hamlet".

Le but de cet exercice est de s'assurer que chaque mot a la même probabilité d'occurrence : 1/2 (k).

Supposons qu'à la fin de l'audio Hamlet, vous ayez 61 mots dans votre liste et qu'il vous ait fallu six tours pour la terminer.

Vous pouvez estimer le nombre de mots différents en divisant 61 par probabilité 1/2 (6) - le résultat final de ce jeu est 3904.

La précision de l'algorithme est proportionnelle à la quantité de mémoire

Les chercheurs Chakraborty, Variyam et Meel ont prouvé mathématiquement que la précision de l'algorithme CVM est proportionnelle à la quantité de mémoire.

Et Hamlet possède 3967 mots uniques. (Par méthode de comptage ordinaire)

Dans l'expérience utilisant une mémoire de 100 mots, l'estimation moyenne des 5 séries de résultats expérimentaux est de 3955 mots.

Avec 1000 mots en mémoire, la capacité moyenne de mémoire est passée à 3964.

Variyam a déclaré : « Si (la mémoire) est suffisamment grande pour accueillir tous les mots, alors nous pouvons atteindre une précision de 100 %. »

William Kuszmau de l'Université Harvard a déclaré : "C'est un excellent exemple de la façon dont même pour des problèmes très fondamentaux et largement étudiés, il peut parfois y avoir des solutions simples mais pas évidentes à découvrir."

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!