Frage zu "Encoding Gaps" (wm-ir.pdf, Folie 33)

Moderator: Web Mining

Benutzeravatar
Patr0rc
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 8. Feb 2008 11:43

Frage zu "Encoding Gaps" (wm-ir.pdf, Folie 33)

Beitrag von Patr0rc »

Es geht auf der angegebenen Folie um mögliche Encodierungen für die Differenzen zwischen IDs, damit man nicht die IDs selbst, sondern nur die ersten ID und danach nur die Differenzen der darauffolgenden IDs speichern muss, um Platz zu sparen. Auf Folie 33 sind nun einmal binäres Encoding, unäres Encoding und Gamma-Encoding angegeben.
Meine Frage ist nun: Worin liegt der Vorteil vom Gamma-Encoding gegenüber dem binären Encoding? Das binäre Encoding wächst logarithmisch mit der Größe der Zahl mit, während das Gamma-Encoding zwischen logarithmisch und linear liegt (da es ja ein Mix aus linearem Codieren der größten beinhalteten Zweierpotenz und binärem Codieren der restlichen Zahl ist). Rein so gesehen würde ich immer das binäre Encoding nehmen, wenn ich weiß, dass ich dabei nicht eine bestimmte Anzahl an Bits benutze, sondern die Anzahl an Bits dynamisch mit der Größe der Zahl wächst, d.h. nicht von vornherein 32 Bits für die Darstellung einer Zahl genommen wird, sondern für die 1 einfach 1 und 16 z.B. 1000 usw. Kann mir jemand vielleicht meinen "Denkfehler" erklären oder mir sagen, dass ich keinen mache? ;-)

jm1035
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 28. Okt 2005 09:26

Re: Frage zu "Encoding Gaps" (wm-ir.pdf, Folie 33)

Beitrag von jm1035 »

Du hast dir die Frage doch eigentlich schon selbst beantwortet. Um die binäre Codierung nutzen zu können, müsstest du vorher wissen, wie viele Stellen deine Zahl hat. Am einfachsten lässt sich das bewerkstelligen, indem man die Zahl mit führenden Nullen speichert und eine fixe Anzahl von Stellen verwendet. Dann bräuchtest du aber für die 1 genauso viele Stellen wie für die 1.000.000. Sinn von unary und gamma ist es eben kleine Zahlen möglichst platzsparend zu speichern.

Benutzeravatar
Patr0rc
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 8. Feb 2008 11:43

Re: Frage zu "Encoding Gaps" (wm-ir.pdf, Folie 33)

Beitrag von Patr0rc »

jm1035 hat geschrieben:Du hast dir die Frage doch eigentlich schon selbst beantwortet. Um die binäre Codierung nutzen zu können, müsstest du vorher wissen, wie viele Stellen deine Zahl hat. Am einfachsten lässt sich das bewerkstelligen, indem man die Zahl mit führenden Nullen speichert und eine fixe Anzahl von Stellen verwendet. Dann bräuchtest du aber für die 1 genauso viele Stellen wie für die 1.000.000. Sinn von unary und gamma ist es eben kleine Zahlen möglichst platzsparend zu speichern.
Auf das Fettgedruckte oben möchte ich antworten: Das stimmt doch aber nicht. Ich muss nicht alle Zahlen mit der gleichen Anzahl an Bits kodieren. Es reicht, wenn ich die 2 (dezimal) als 10 (binär) und die 17 (dezimal) als 10001 (binär) speichere; dabei muss ich gar nicht die 2 (dezimal) als 00010 speichern. Ich brauche in meiner Version keine feste Anzahl an Binärstellen (und mir würde auch nicht einleuchten, was an meiner Version nicht geht, denn ich kann eine Zahl in meiner binären Version immer eindeutig umwandeln in Dezimalsystem). Also bringen die anderen beiden Kodierungen ggü meiner binären Version keinerlei Vorteil. Oder habe ich noch einen Denkfehler?!?

jm1035
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 28. Okt 2005 09:26

Re: Frage zu "Encoding Gaps" (wm-ir.pdf, Folie 33)

Beitrag von jm1035 »

Wenn du im Speicher auf die Bitfolge 10001 stößt, woher weißt du, dass das eine 17 ist und nicht zum Beispiel eine 8 gefolgt von einer 1? Doch nur, weil du weißt, dass die Zahl, die du jetzt lesen willst 5 Stellen hat.

Benutzeravatar
Patr0rc
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 8. Feb 2008 11:43

Re: Frage zu "Encoding Gaps" (wm-ir.pdf, Folie 33)

Beitrag von Patr0rc »

Das war das, was mir gefehlt hat. Das klingt einleuchtend. Danke.

Antworten

Zurück zu „Web Mining“