Maison Périphériques technologiques IA 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 »

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 »

Jun 07, 2024 pm 03:44 PM
ai 算法 数学

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.

Lalgorithme 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 »

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.

Lalgorithme 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 »

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".

Lalgorithme 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 »

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!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

Video Face Swap

Video Face Swap

Échangez les visages dans n'importe quelle vidéo sans effort grâce à notre outil d'échange de visage AI entièrement gratuit !

Article chaud

<🎜>: Bubble Gum Simulator Infinity - Comment obtenir et utiliser les clés royales
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
<🎜>: Grow A Garden - Guide de mutation complet
3 Il y a quelques semaines By DDD
Nordhold: Système de fusion, expliqué
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Mandragora: Whispers of the Witch Tree - Comment déverrouiller le grappin
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Sujets chauds

Tutoriel Java
1675
14
Tutoriel PHP
1278
29
Tutoriel C#
1257
24
Comment définir, obtenir et supprimer les cookies WordPress (comme un professionnel) Comment définir, obtenir et supprimer les cookies WordPress (comme un professionnel) May 12, 2025 pm 08:57 PM

Voulez-vous savoir comment utiliser des cookies sur votre site Web WordPress? Les cookies sont des outils utiles pour stocker des informations temporaires dans les navigateurs des utilisateurs. Vous pouvez utiliser ces informations pour améliorer l'expérience utilisateur par le biais de personnalisation et de ciblage comportemental. Dans ce guide ultime, nous vous montrerons comment définir, obtenir et supprimer les cookies WordPress comme un professionnel. Remarque: Il s'agit d'un tutoriel avancé. Il vous oblige à maîtriser HTML, CSS, WordPress sites Web et PHP. Que sont les cookies? Les cookies sont créés et stockés lorsque les utilisateurs visitent les sites Web.

2025 Huobi APKV10.50.0 Guide de téléchargement comment télécharger 2025 Huobi APKV10.50.0 Guide de téléchargement comment télécharger May 12, 2025 pm 08:48 PM

Huobi APKV10.50.0 Guide de téléchargement: 1. Cliquez sur le lien direct dans l'article; 2. Sélectionnez le package de téléchargement correct; 3. Remplissez les informations d'enregistrement; 4. Démarrez le processus de trading Huobi.

2025 Huobi APKV10.50.0 Adresse de téléchargement 2025 Huobi APKV10.50.0 Adresse de téléchargement May 12, 2025 pm 08:42 PM

Huobi APKV10.50.0 Guide de téléchargement: 1. Cliquez sur le lien direct dans l'article; 2. Sélectionnez le package de téléchargement correct; 3. Remplissez les informations d'enregistrement; 4. Démarrez le processus de trading Huobi.

2025 Huobi APKV10.50.0 Méthode d'installation Guide APK 2025 Huobi APKV10.50.0 Méthode d'installation Guide APK May 12, 2025 pm 08:27 PM

Huobi APKV10.50.0 Guide de téléchargement: 1. Cliquez sur le lien direct dans l'article; 2. Sélectionnez le package de téléchargement correct; 3. Remplissez les informations d'enregistrement; 4. Démarrez le processus de trading Huobi.

2025 Huobi APKV10.50.0 Télécharger le site Web 2025 Huobi APKV10.50.0 Télécharger le site Web May 12, 2025 pm 08:39 PM

Huobi APKV10.50.0 Guide de téléchargement: 1. Cliquez sur le lien direct dans l'article; 2. Sélectionnez le package de téléchargement correct; 3. Remplissez les informations d'enregistrement; 4. Démarrez le processus de trading Huobi.

Le dernier classement des dix principales applications de change de devises numériques a recommandé les dix principales applications de change de monnaie numérique Le dernier classement des dix principales applications de change de devises numériques a recommandé les dix principales applications de change de monnaie numérique May 12, 2025 pm 08:15 PM

Les derniers classements des dix principaux applications d'échange de devises numériques sont: 1. Okx, 2. Binance, 3. Huobi, 4. Coinbase, 5. Kraken, 6. Kucoin, 7. Bitfinex, 8. Gemini, 9. Bitstamp, 10. Poloniex. Les étapes de l'utilisation de ces applications comprennent: le téléchargement et l'installation de l'application, l'enregistrement d'un compte, la réalisation de la certification KYC, la recharge et le démarrage d'une transaction.

Top 10 du classement des applications de change virtuelle en 2025, top 10 les derniers classements des applications de trading de devises numériques Top 10 du classement des applications de change virtuelle en 2025, top 10 les derniers classements des applications de trading de devises numériques May 12, 2025 pm 08:18 PM

Les dix principales applications d'échange de devises virtuelles en 2025 sont classées comme suit: 1. Okx, 2. Binance, 3. Huobi, 4. Coinbase, 5. Kraken, 6. Kucoin, 7. Bybit, 8. Ftx, 9. Bitfinex, 10. Gate.io. Ces échanges sont sélectionnés en fonction de dimensions telles que l'expérience utilisateur, la sécurité et le volume de transaction. Chaque plate-forme offre des fonctions et des services uniques pour répondre aux besoins des différents utilisateurs.

Huobi APKV10.50.0 Tutoriel d'installation de la version Huobi APKV10.50.0 Tutoriel d'installation de la version May 12, 2025 pm 08:33 PM

Huobi APKV10.50.0 Guide de téléchargement: 1. Cliquez sur le lien direct dans l'article; 2. Sélectionnez le package de téléchargement correct; 3. Remplissez les informations d'enregistrement; 4. Démarrez le processus de trading Huobi.

See all articles