Usa una tabella hash. La tabella hash includerebbe una chiave ragionevolmente unica generata dalla stringa e puntatori alle stringhe che corrispondono alla chiave hash.
Un hash semplice e veloce con una piccola tabella hash (256 voci), ma molte collisioni tra chiavi, sarebbe l'xor di tutti i byte nella stringa. Un hash più lento e più complicato con una tabella hash molto più grande (come molte voci delle stringhe), ma dove le collisioni chiave sono improbabili, sarebbe la crittografia AES.
Mi rendo conto che stai usando C #, ma qui c'è un piccolo script perl che ti aiuta a indagare su quale tabella hash vorresti usare. Questa versione della funzione keyify () somma solo la stringa in un intero a 16 bit.
# keyspace.pl
sub keyify {
use constant HASH_KEY_SIZE_IN_BITS => 16;
return unpack( '%' . HASH_KEY_SIZE_IN_BITS . 'A*', $_ );
}
$/ = "\r\n"; # Windows EOL
$offset = 0;
while(<>) {
$newoffset = $offset + length($_);
$key = keyify($_);
if (defined $myhash{$key}) {
# key collision, add to the list of offsets
push @{ $myhash {$key} }, $offset;
} else {
# new key, create the list of offsets
$myhash { $key } = [$offset];
}
$offset = $newoffset;
}
printf "%d keys generated\n", scalar (keys %myhash);
$max = 0;
foreach (keys%myhash) {
$collisions = scalar @{ $myhash{$_} };
$max = $collisions if ( $collisions > $max );
}
print "maximum # of string offsets in a hash = $max\n";
exit;
# dump hash table
foreach (keys%myhash) {
print "key = $_:";
foreach my $offset ( @{ $myhash{$_} } ) {
print " $offset";
}
print "\n";
}
Usalo in questo modo:
perl keyspace.pl <strings.dat
La stessa cosa in PowerShell, con una funzione di hashing molto più semplice. Dovrai impegnarti se vuoi che questo sia utile.
# keyspace.ps1
# Don't use "gc -Encoding Byte -Raw" because it reads the ENTIRE file into memory.
function keyify {
return $args[0].Substring(0,1);
}
$myHash = @{};
$offset = 0;
$file = New-Object System.IO.StreamReader($args[0]);
while ($line = $file.ReadLine()) {
$newoffset = $offset + $line.Length + 2; # adjust by 2 for Windows EOL (CRLF)
$key = keyify($line);
if ($myHash.ContainsKey($key)) {
# key collision, add to the list of offsets
$myHash.Set_Item($key, $myHash.Get_Item($key)+$offset);
} else {
# new key, create the list of offsets
$myHash.Add($key, @($offset));
}
$offset = $newoffset;
}
$file.close()
echo "$($myHash.Count) keys generated";
$max = 0;
foreach ($i in $myHash.KEYS.GetEnumerator()) {
$collisionList = $myHash.Get_Item($i);
if ($collisionList.Count -gt $max) { $max = $collisionList.Count; }
}
echo "maximum # of string offsets in a hash = $max";
# echo $myHash;
Usalo in questo modo:
.\keyspace.ps1 strings.dat