Die Trackzahl:
| 12 |
Dies ist sehr leicht nachzuvollziehen, aber leider keine sehr weise Entscheidung.
Eine CD mit 0 Tracks macht nicht sonderlich viel Sinn. Insofern ist die Endung '00' unmöglich und verschenkt.
Bei ca. einer Million CD's war keine CD dabei, die mehr als 99 Tracks hatte.
Wahrscheinlich ist das irgendwie verboten, oder unmöglich.
Die größte Endung für eine CSID ist daher '63' (16*6 + 3 = 99) - insgesamt werden hier also nur 99 von 256 möglichen Werten genutzt.
62% aller möglichen, 8-stelligen Hexadezimalzahlen können also gar nicht generiert werden.
Hinzu kommt folgendes:
Ein guter Hashwert zeichnet sich dadurch aus, das die Häufigkeit, mit der die Bits gesetzt sind, gleichverteilt sind, d.h.:
Wenn man eine Stichprobe (sagen wir 1000 CDs) zufällig aus der Grundgesamtheit zieht, und für jede die CSID generiert, und mitzählt, wie oft jedes Bit im Hashcode gesetzt ist, so müßte jede Bitposition ca. 500 mal gesetzt sein.
Eine Gleichverteilung erhält man beispielsweise, wenn man einen Würfel wirft, und das Vorkommen der Zahlen 1-6 zählt.
Der Normalfall bei Verteilungen ist jedoch die - der Name sagt es schon - Normalverteilung.
Eine solche erhält man, wenn man 2 Wüfel wirft, und die Summen beider Würfel addiert.
Da man eine Summe von 7 auf viele Arten erzielen kann (1+6, 2+5, 3+4, 4+3, 5+2, 6+1), eine Summe von 11 (6+5, 5+6) nur selten, ganz selten nur die Summen 12 (6+6) und 2 (1+1) - kommen einige Werte sehr oft, andere sehr selten vor.
So ist es auch mit der Trackzahl. Bei 1,06 Mio. CDs kommen 12 Tracks über 100.000 mal vor, 87 Tracks nur 8 mal.
In Tabellenform für einige Werte sieht es so aus:
| tracks | count |
|---|---|
| 1 | 6025 |
| 2 | 16363 |
| 3 | 26655 |
| 10 | 96821 |
| 11 | 76873 |
| 12 | 107077 |
| 13 | 67066 |
| 14 | 77278 |
| 30 | 2612 |
| 50 | 250 |
| 70 | 59 |
| 90 | 21 |
| 99 | 380 |
Der ungewöhnlich hohe Wert bei 99 Tracks erklärt sich sicherlich daher, dass mehr Tracks nicht möglich sind, und viele Produzenten 'soviel wie möglich' auf die CD bringen wollen.
Insgesamt habe ich beobachtet, das nur auf 10349 CDs mehr als 31 Tracks sind.
Das entspricht 1% der Gesamtmenge.
Somit werden die oberen 3 Bit in 99% der Fälle nicht gesetzt - das entspricht hex-codes größer als 'x1f' bzw. ab 'x20'
Umgerechnet sind also 7/8 des Hashcodes mehr oder weniger verschenkt, in 1/8 der Hashraumes tummeln sich 99% aller CDs.
Die Spielzeit:
| 1017 |
Die Spielzeit (in Sekunden) bildet den mittleren, breiten Teil des Hashcodes.
Im Beispiel entspricht der 0x1017 ein Dezimalwert von 4119 Sekunden, was knapp 69 Minuten entspricht.
Die Anzahl der Vorkommen in vollen Minuten in der Grundgesamtheit:
(Nur für glatte 10 Min. hier gezeigt, sowie die letzten 3 Werte.)
| minutes | anz |
|---|---|
| 0 | 64 |
| 10 | 3681 |
| 20 | 5156 |
| 30 | 6513 |
| 40 | 19616 |
| 50 | 21807 |
| 60 | 21372 |
| 70 | 22518 |
| 80 | 1176 |
| 90 | 12 |
| 100 | 3 |
| 110 | 0 |
| 150 | 1 |
| 200 | 0 |
| 250 | 0 |
| 300 | 1 |
| 541 | 1 |
| 542 | 1 |
| 3591 | 1 |
Der letzte Wert, der eine Spielzeit von ca. 60 Stunden [sic!] bedeutet, ist sicherlich falsch.
Was es mit den Spielzeiten von 81 min. und mehr auf sich hat - ob dies Alben mit mehreren CD's sind oder ob schlicht die Werte falsch sind, harrt noch der Untersuchung - zahlenmäßig fallen diese Fälle nicht sonderlich ins Gewicht.
Insgesamt behaupten lediglich 692 CD's von sich eine Spielzeit von 81 und mehr Minuten zu haben, also weniger als 0,1%.
99,9% aller CD's teilen sich hier 7,4% aller Teilstrings des Hashcodes.
92,6% aller möglichen Werte werden gar nicht - oder doch äußerst selten erzeugt.
Kombiniert mit der Erkenntnis, dass nur etwa 1/8 der unteren 2 Hexcodes ausgenutzt werden ergibt sich eine zwischenzeitliche Ausnutzung des Hashraumes von nur 1%.
Langsam fragt man sich, wie groß denn der Hashraum insgesamt ist.
Theoretisch kann er ca. 4.3 Mrd. unterschiedliche Zahlen fassen.
Praktisch sind wir nur noch bei 1% davon, also ca. 40 Mio. Zahlen.
Bei momentan 1 Mio. CD's ist also noch einiges an Luft vorhanden.
Hier könnte eine Betrachtung über das momentane und zukünftige Aufkommen neuer Einträge folgen.
Dies ist nicht ganz trivial, als diese Zahlen nicht leicht in die Zukunft hochzurechnen sind.
Einerseits wächst die Zahl der Internetuser progressiv.
Die Zahl der CD-Neuveröffentlichungen dürfte im Zunehmen begriffen sein.
Dagegen dürfte die Zahl der CD-Veröffentlichungen, die zuvor auf Vinyl erschienen sind im Abnehmen begriffen sein.
Wer in der Lage ist gute Schätzungen für das Wachstum der CDDB anzugeben ist hiermit eingeladen das zu tun.
SQS
| 11 |
Mit SQS kürze ich den etwas Ausladenden Begriff der 'Summe über die Quersummen der Trackoffsets' ab.
So funktionierts:
Jeder Track hat eine Startposition.
Dieser wird durch 75 dividiert, um auf die Startposition in Sekunden zu kommen.
Für jeden Sekunden-offset wird die Quersumme gebildet.
Die Quersummen werden summiert.
Das Resultat wird modulo 255 genommen.
Die Modulo-operation soll den Überlauf der Zahlen verhindern, ist hier jedoch missglückt.
Der Wert müsste modulo 256 genommen werden und würde dann maximal ein '0xff' liefern.
Hier liefert die Operation maximal ein '0xfe'. Dies ist jedoch gegenüber den vorherigen Unglücksfällen verschmerzbar, man verschenkt lediglich 1/256-tel der möglichen Werte, dies jedoch konsequent.
In ca. 3/4 aller Fälle beginnt der erste Track bei der Position 150 was 2 Sekunden entspricht.
Dies kann man bei gerippten CD's sich zu Nutze machen, und einfach die 2 Sekunden für jeden Track hinzuaddieren.
Es wird auch gemacht. (link: ...)
Leider ist das in 1/4 aller Fälle falsch.
Für unser Beispiel:
| Startpos | In Sek. | Quersumme |
|---|---|---|
| 150 | 2 | 2 |
| 14177 | 189 | 18 |
| 28925 | 385 | 16 |
| 44671 | 595 | 19 |
| 67655 | 902 | 11 |
| 81235 | 1083 | 12 |
| 97467 | 1299 | 21 |
| 113562 | 1514 | 11 |
| 121176 | 1615 | 13 |
| 141939 | 1892 | 20 |
| 156423 | 2085 | 15 |
| 180203 | 2402 | 8 |
| 198065 | 2640 | 12 |
| 221472 | 2952 | 18 |
| 238963 | 3186 | 18 |
| 257836 | 3437 | 17 |
| 272925 | 3639 | 21 |
| 293785 | 3917 | 20 |
| sum_quersum | 272 | |
| sqs mod 255 | 17 |
Betrachtet man die Verteilung der CDs, so ergibt sich aus Gesamtlängen von 30 bis 80 Minuten.
Dies sind 1800 bis 4800 Sekunden, also 4-stellige Dezimalziffern.
Die letzten 3 Ziffern dürften dabei gleichverteilt über das Zahlenspektrum sein, also alle Werte von 0-9 gleich oft treffen - im Mittel also die 4,5.
Die erste Ziffer dagegen wird meist 1-3 sein, gelegentlich 4, im Schnitt jedoch um die 2.
Für die 4-stelligen Zahlen ergibt sich im Schnitt eine Quersumme von 15,5.
Natürlich haben die ersten Songs kleinere Offsets - meist 3stellige Dezimalzahlen.
Deren Durchschnittswert müßte bei 3*4,5 liegen, also bei 13,5.
Nehme ich nun Pi mal Schnauze 15 als groben Schätzwert und multipliziere es mit Trackzahlen von 10 - 20, so komme ich auf SQS-Werte von 150 bis 300.
Dies führt bei einer Modulo-255 Operation zu Werten von 150-254 und 0-45, also einer Lücke zwischen 45 und 150.
Da dies jedoch grob geschätzte Mittelwerte sind, und relativ kleine Abweichungen große Wirkungen haben könen,
(Trackoffset 1299-> Quersumme=21, Trackoffset 1300-> Quersume=4)
ist dies lange nicht so kritisch zu sehen, wie die Werteballungen bei Trackzahl und Gesamtlänge.
Graphische Darstellungen der Hashraumausnutzung
- Logarithmische Darstellung
Dies ist Snapshot des Programms - bzw. eines Forks des Programms, der die Treffer bei einzelnen Bits für die Hashcodes berechnet.
Der Snapshot ist nachträglich mit Kommentaren versehen worden.
Im linken Teil ist der original-Hashwert dargestellt, im rechten mein neuer llci.
Die Bits 0-31 sind von links nach rechts aufgetragen.
Dabei sind die unteren 8 Bits gelb, die mittleren 16 blau, und die oberen 8 grün eingefärbt.
Die Einfärbung wurde auch für den llci übernommen, obwohl hier keine inhaltliche Grenze zwischen den Bits dies rechtfertigt.
Auf der y-Achse nach unten sind die Punkte ein Maß für die Häufigkeit der Treffer.
Deutlich sichtbar ist die Ausfransung des Graphen bei den CSID, wobei man sich vor Augen halten muß, dass ein zusätzlicher Punkt eine Verdopplung der Anzahl bedeuten kann. (Wegen des Rundens - z.B. 255: 7 Punkte, 256 8 Punkte, kann natürlich ein Punkt Unterschied auch einen Unterschied von Eins bedeuten.)
Daher auch eine Darstellung in Linearer Form:
Punkte Treffer 1 1 2 2 3 4 4 8 ... ... 15 32768 ... ... 19 524288 - Lineare Darstellung
-
Wie in der Vorherigen Grafik sind die Bits von links (0) nach rechts (31) aufgeführt.
Deutlich zu sehen ist die Ungleichverteilung der CSID-Bits.
Was man auch sieht, ist, dass die oberen Bits des llci seltener getroffen werden, als die unteren.
Die Abweichungen vom erwünschten Mittelwert - 530.000 counts, halten sich jedoch in Grenzen.