Infnet-Algorithmensammlung - Falten und Hashing

Falter

Auswertung

Eine ganze Reihe von Strings wird durch den Hash-Filter gepumpt. Die Hashwerte werden sortiert und die Zahl der Überdeckungen (Häufigkeiten) der Werte gezählt.
Aus den Überdeckungen werden Stichprobenparameter ermittelt. Sei nun

n: Anzahl der verschiedenen Hashwerte
max: größte anzahl der Überdeckungen
Mittel,Varianz und Streuung: die Paramenter der Überdeckungswerte

Optimal wäre n=Anzahl der Wörter und max=1

Die Zeilen wurden mit folgendem Script generiert:

#!/bin/bash
echo "#Versuch:n:max:Mittel:varianz:streuung"
echo -n "$*:"
awk '/^ATTRIBUTE/ { print $2; }' < /exp/prod/radius/db/dictionary | \
./hashtest $* | sort | grupstich -g1 +n | grupstich -f2 +n +max +m +var +s

Am Beispiel des Ascend-Radius-Dictionaries testen wir unsere Hashfunktionen:

Faltung	hash	n	max	Mittel	varianz	streuung
8bit	modulo	93	10	1.98925	2.09771	1.44835
8bit	xor	85	8	2.17647	2.0042	1.4157
6bit	modulo	123	5	1.50407	0.629082	0.793147
6bit	xor	130	4	1.42308	0.447525	0.668973

Um so größer n und je kleiner max,die Varianz und die Streuung ist, desto besser ist die Hash-Funktion.

Es zeigt sich, daß die 6bit-Faltung mit der xor-Hashfunktion die besten Werte liefert. Die Hyphothese scheint also zu stimmen, daß mit dem Zusammenzählen mit XOR viel Informationen erhalten bleibt.

Rudolf Weber Informatik- und Netzwerkverein Ravensburg e.V.