Der bahnbrechende CVM-Algorithmus löst Zählprobleme aus über 40 Jahren! Informatiker wirft Münze, um einzigartiges Wort für „Hamlet' zu finden

Zählen klingt einfach, ist aber in der Praxis nur sehr schwer umzusetzen.

Stellen Sie sich vor, Sie werden in einen unberührten tropischen Regenwald geschickt, um eine Wildtierzählung durchzuführen. Wenn Sie ein Tier sehen, machen Sie ein Foto.

Die Digitalkamera zeichnet nur die Gesamtzahl der verfolgten Tiere auf, Sie interessieren sich jedoch für die Anzahl der einzelnen Tiere, es gibt jedoch keine Statistik.

Also, wie kommt man am besten an dieses einzigartige Tier?

An diesem Punkt müssen Sie sagen: Fangen Sie von jetzt an an zu zählen und vergleichen Sie schließlich jede neue Art vom Foto mit der Liste.

Allerdings ist diese gängige Zählmethode für Informationsmengen bis zu Milliarden von Einträgen manchmal nicht geeignet.

Informatiker des Indian Statistical Institute, UNL, und der National University of Singapore haben einen neuen Algorithmus vorgeschlagen – CVM.

Es kann die Anzahl verschiedener Elemente in einer langen Liste annähern und muss sich nur eine kleine Anzahl von Elementen merken.

Papieradresse: https://arxiv.org/pdf/2301.10191

Dieser Algorithmus eignet sich für jede Liste, in der jeweils ein Element erscheint, z. B. Text in einer Rede, Waren auf ein Förderband, oder Autos auf der Autobahn.

Der CVM-Algorithmus ist nach den Anfangsbuchstaben der drei Autoren benannt und hat erhebliche Fortschritte bei der Lösung des „Problems verschiedener Elemente“ gemacht.

Dieses Problem beschäftigt Informatiker seit mehr als 40 Jahren.

Es erfordert eine effiziente Möglichkeit, einen Strom von Elementen (deren Gesamtzahl den verfügbaren Speicher überschreiten kann) zu überwachen und die Anzahl der darin enthaltenen eindeutigen Elemente abzuschätzen.

Wie löst der CVM-Algorithmus das Problem?

Pionierender CVM-Algorithmus, das Geheimnis liegt in der „Randomisierung“

Angenommen, Sie hören das Hörbuch „Hamlet“.

Dieses Drama hat insgesamt 30557 Wörter, wie viele sind unterschiedlich?

Um die Antwort zu finden, können Sie beim Zuhören eine Pause einlegen, jedes Wort in alphabetischer Reihenfolge aufschreiben, dann die Wörter, die sich bereits auf der Liste befinden, überspringen und zum Schluss einfach jedes Wort auf der Liste zählen.

Diese Methode ist machbar, aber sie stellt das „Gedächtnis“ zu sehr auf die Probe.

Der Forscher Vinodchandran Variyam sagte: „In einer typischen Datenflusssituation müssen möglicherweise Millionen von Elementen verfolgt werden. Möglicherweise möchten Sie nicht alle Informationen speichern.

Das ist ein Cloud-Server, auf dem Algorithmen einfachere Bereitstellung ermöglichen können.“ Methoden".

Der Trick ist die „Randomisierung“.

Vinodchandran Variyam half bei der Entwicklung eines CVM-Algorithmus zur Schätzung der Anzahl unterschiedlicher Elemente in einem Datenstrom

Wie viele einzigartige Wörter gibt es in „Hamlet“? Coin Flip Challenge

Zurück zu „Hamlet“, vorausgesetzt, Ihr „effektives Gedächtnis“ kann nur 100 Wörter fassen.

Sobald die Audiowiedergabe beginnt, notieren Sie die ersten 100 Wörter, die Sie hören, und überspringen alle wiederholten Wörter.

Wenn Sie mit der Aufnahme von 100 Wörtern fertig sind, müssen Sie nur noch für jedes Wort eine Münze werfen –

Kopf, behalten Sie das Wort. Wenn es sich um die Rückseite handelt, löschen Sie sie.

Nach dieser Vorrunde bleiben Ihnen etwa 50 verschiedene Wörter übrig.

Jetzt fahren Sie mit dem fort, was das Team Runde 1 nennt, indem Sie weiter Hamlet lesen und neue Wörter hinzufügen.

Wenn Sie erneut auf ein Wort stoßen, das bereits auf der Liste steht, werfen Sie die Münze erneut, bis Sie 100 Wörter auf Ihrem Whiteboard im Gedächtnis haben.

Dann wird anhand der Ergebnisse von 100 Münzwürfen etwa die Hälfte der Wörter wieder zufällig gelöscht. Runde 1 endet hier.

Als nächstes geht es in die zweite Runde von Runde 2.

Wie in der ersten Runde erhöhen wir den Schwierigkeitsgrad eines Wortes – wenn Sie auf ein wiederholtes Wort stoßen, werfen Sie die Münze erneut.

Die Bedingung ist: Wenn es sich um einen Schwanz handelt, löschen Sie ihn wie zuvor. Aber wenn es „Kopf“ ist, werfen Sie die Münze noch einmal. Das Wort bleibt erst erhalten, wenn es zum zweiten Mal erscheint.

Sobald das Gedächtnis-Whiteboard voll ist, beenden Sie die Runde und löschen Sie dann basierend auf den Ergebnissen von 100 Würfen erneut etwa die Hälfte der Wörter.

In Runde 3 müssen Sie dreimal hintereinander eine Münze auf den Kopf werfen, um ein Wort zu behalten.

Behalten Sie in der vierten Runde viermal hintereinander ein Wort auf der Vorderseite und so weiter.

Abschließend hören Sie in der k-ten Runde das gesamte Stück „Hamlet“.

Der Sinn dieser Übung besteht darin, sicherzustellen, dass jedes Wort die gleiche Auftrittswahrscheinlichkeit hat: 1/2 (k).

Angenommen, Sie haben am Ende des Hamlet-Audios 61 Wörter auf Ihrer Liste und es hat sechs Runden gedauert, bis Sie fertig sind.

Sie können die Anzahl der verschiedenen Wörter schätzen, indem Sie 61 durch Wahrscheinlichkeit 1/2 (6) dividieren – das Endergebnis in diesem Spiel ist 3904.

Die Genauigkeit des Algorithmus ist proportional zur Speichermenge.

Die Forscher Chakraborty, Variyam und Meel haben mathematisch bewiesen, dass die Genauigkeit des CVM-Algorithmus proportional zur Speichermenge ist.

Und Hamlet hat zufällig 3967 einzigartige Wörter. (Mit der gewöhnlichen Zählmethode)

Bei dem Experiment mit 100-Wort-Speicher beträgt die durchschnittliche Schätzung der 5 Runden experimenteller Ergebnisse 3955 Wörter.

Bei 1000 Wörtern im Speicher stieg die durchschnittliche Speicherkapazität auf 3964.

Variyam sagte: „Wenn (der Speicher) groß genug ist, um alle Wörter aufzunehmen, können wir eine Genauigkeit von 100 % erreichen.“

William Kuszmau von der Harvard University sagte: „Dies ist ein großartiges Beispiel dafür, dass selbst für sehr grundlegende und umfassend untersuchte Probleme manchmal einfache, aber nicht offensichtliche Lösungen noch entdeckt werden müssen.“