Zählen leicht gemacht: Neuer CVM-Algorithmus löst jahrzehntealtes Problem

Wissenschaftler haben eine neue Methode zur Zählung entdeckt, die das jahrzehntealte Problem der Erkennung von unterschiedlichen Objekten löst: Den CVM-Algorithmus. Dieser Durchbruch ist besonders für Computeranwendungen bedeutsam. Die Anwendungsmöglichkeiten reichen von der Netzwerkverkehrsanalyse über Betrugserkennung bis hin zur Bioinformatik.

Der neue CVM-Algorithmus wurde von Vinodchandran Variyam von der University of Nebraska–Lincoln, Sourav Chakraborty vom Indian Statistical Institute und Kuldeep Meel von der University of Toronto entwickelt. Laut Variyam basierten frühere Algorithmen auf Hashing-Techniken, deren Qualität von den gewählten Hash-Funktionen abhing. Der neue Algorithmus verwendet eine Sampling-Strategie und kann mit einfachen Methoden analysiert werden.

Übrigens: Laut TESSA ist ein Hash oder Hashwert ein Datensatz mit einer festen Länge (z.B. 16 Bit, 32 Bit, 64 Bit), der zur Verifizierung von Daten oder Datenübertragungen dient. Um einen Hashwert zu erzeugen, wird eine Hash-Funktion verwendet. Diese Funktion wandelt beliebige Daten wie Texte, Musik oder Programme in einen Hashwert um, wobei die Länge des Hashwerts stets gleich bleibt, unabhängig von der Größe der ursprünglichen Daten. Hashwerte werden meist in hexadezimaler Schreibweise dargestellt, wobei die Zahlen 0-9 und die Buchstaben A-F verwendet werden.

Im Laufe der Zeit sind viele verschiedene Hash-Funktionen entwickelt worden. Es ist ein ständiger Wettlauf zwischen kriminellen Hackern, die versuchen, diese Funktionen zu knacken, und Entwicklern oder Organisationen wie der NSA, die immer sicherere Hash-Funktionen entwerfen.

Vereinfachtes Zählen

Laut iflscience reduziert der CVM-Algorithmus den Speicherbedarf drastisch, was in der heutigen Ära von Big Data (größere und komplexere Datensätze) von großer Bedeutung ist. Er nutzt eine Wahrscheinlichkeitsmethode, die Variyam und seine Kollegen anhand des Beispiels der Wortzählung in Shakespeares „Hamlet“ veranschaulichen:

Stellen Sie sich vor, Sie möchten die Anzahl der einzigartigen Wörter im Text zählen, aber Ihr Speicher kann nur 100 Wörter gleichzeitig speichern. Zunächst speichern Sie die ersten 100 einzigartigen Wörter, die Sie finden. Danach entscheiden Sie mit einem Münzwurf, welche Wörter behalten werden. Bei „Kopf“ bleibt das Wort, bei „Zahl“ wird es gelöscht.

Nach diesem Vorgang haben Sie etwa 50 Wörter gespeichert. Dann wiederholen Sie den Prozess, aber jedes Mal, wenn ein Wort bereits auf der Liste steht, entscheiden Sie erneut per Münzwurf, ob es gelöscht wird. In der zweiten Runde müssen Sie zwei Mal hintereinander „Kopf“ werfen, um ein Wort zu behalten. In der dritten Runde drei Mal, und so weiter. Am Ende des Textes bleiben nur die Wörter, die in jeder Runde bestehen blieben.

Durch diesen wiederholten Prozess sorgt der Algorithmus dafür, dass jedes Wort dieselbe Wahrscheinlichkeit hat, in der endgültigen Liste zu stehen. Nehmen wir an, es dauert sechs Runden, bis „Hamlet“ vollständig durchlaufen ist und am Ende 61 einzigartige Wörter übrig bleiben. Sie können dann diese Zahl mit 2⁶ (weil es sechs Runden waren) multiplizieren, um eine Schätzung der Gesamtzahl der Wörter zu erhalten. Das Ergebnis wäre 3.904 Wörter, was nahe an der tatsächlichen Anzahl von 3.967 liegt. Mit mehr Speicherplatz erhöht sich die Genauigkeit weiter.

Positive Resonanz in der Wissenschaft

Andrew McGregor, Professor an der University of Massachusetts, Amherst, kommentierte, der Algorithmus sei „erstaunlich einfach und leicht zu implementieren“ und werde möglicherweise die Standardmethode zur Lösung des Problems der unterschiedlichen Objekte. Der Algorithmus erregt große Aufmerksamkeit und wird von vielen Computerwissenschaftlern bewundert.

Donald Knuth, bekannt als „Vater der Algorithmenanalyse“, lobte den Algorithmus in einem im Mai 2023 veröffentlichten Papier. Verschiedene Teams arbeiten seitdem an der Feinabstimmung des Algorithmus, und einige lehren ihn bereits in ihren Computerkursen. Variyam glaubt, dass der Algorithmus zukünftig in Grundkursen zur Informatik und probabilistischen Algorithmen unterrichtet wird. Knuth stimmte zu und meinte, er sei „wunderbar geeignet, um Studenten die Grundlagen der Informatik beizubringen“.

Einfachheit führt zu Durchbruch

Variyam erklärte, dass die Entdeckung eines so einfachen Algorithmus überraschend sei, aber nicht ungewöhnlich in der Wissenschaft. „Es ist nicht selten, dass Einfachheit über Jahre hinweg übersehen wird,“ sagte er.

Was du dir merken solltest:

• Wissenschaftler haben mit dem CVM-Algorithmus eine neue Methode zur Zählung unterschiedlicher Objekte entwickelt, die Speicherbedarf drastisch reduziert und besonders für Computeranwendungen bedeutend ist, wie Netzwerkverkehrsanalyse, Betrugserkennung und Bioinformatik.
• Der von Vinodchandran Variyam, Sourav Chakraborty und Kuldeep Meel entwickelte Algorithmus verwendet eine Sampling-Strategie anstelle von Hashing-Techniken und ermöglicht einfache Analysen, was ihn besonders effizient und leicht implementierbar macht.
• Der CVM-Algorithmus hat seit seiner Veröffentlichung große Aufmerksamkeit in der Wissenschaft erregt und wird von Experten wie Donald Knuth als Durchbruch gefeiert, wobei er als geeignetes Lehrmittel in der Informatik und probabilistischen Algorithmen angesehen wird.

Bild: © Vecteezy