Algoritmo per l'indicizzazione di stringhe in "elenco"

2

Immagina di avere un file chiamato strings.dat . All'interno di questo file c'è un sacco di stringhe, per esempio: un milione. Le stringhe sono ordinate . Ora voglio trovare la stringa specificata, quindi posso scrivere un metodo come questo:

public long FindByName (string text)
{
  // ...
}

Questo metodo può restituirmi una posizione all'interno di un file in cui si verifica questa stringa. Ma l'iterazione di molti dati non è efficiente. Posso fare un po 'di sistema di indicizzazione, come un Dictionary<char, long> che indica a quale posizione all'interno del file si trova la prima stringa con il suo valore a partire dal dato char.

Esempio: se ho 5 stringhe: ciao
Hello2
mondo
world2
Zzz

Quindi il mio dizionario sarà come:
h 0
w 2
z 4

Ma non è efficiente se avrò 1000 string con "d" char come prima lettera e 10 milioni con "r" letter.

Sai che alcuni buoni algoritmi fanno ahi ciò che sto chiedendo?

    
posta zgnilec 28.04.2014 - 14:32
fonte

4 risposte

16

Poiché i tuoi dati sono ordinati, utilizzerei un algoritmo Ricerca binaria su di esso.

Poiché questo è un file di testo (ad esempio, le lunghezze delle stringhe / le dimensioni dei record non sono tutte uguali) avrai un po 'di aggiustamento da fare.

Ad esempio, supponi che il tuo file abbia una dimensione di 1 GB - (la lunghezza media della stringa, inclusa la fine della riga, è di circa 1.024 byte.

Apri il file e inizia a leggere i byte nella posizione 512 MB. È probabile che tu abbia raggiunto il centro di una stringa. Nessun problema, continua a leggere i byte fino a raggiungere la fine della riga, quindi leggi la riga successiva e utilizzala come pivot.

Sarà un po 'più complicato che se tutte le stringhe fossero della stessa lunghezza, ma non così terribilmente.

Se il tuo target di ricerca arriva prima della stringa pivot, la successiva lettura ad accesso casuale inizierà intorno ai 256 MB.

    
risposta data 28.04.2014 - 15:16
fonte
2

Nei commenti alla tua domanda hai menzionato che hai usato per usare un DBMS ma ti stai allontanando per risparmiare denaro e rendere il tuo progetto più portabile.

Esistono alternative DBMS libere e portatili. Consiglio vivamente di esaminare quelli invece di scriverne uno tuo.

I prodotti esistenti saranno stati progettati da sviluppatori migliori di te o me e avranno già centinaia di ore di test. In altre parole: Saranno più veloci e più stabili.

Prova a cercare sqlite .

    
risposta data 28.04.2014 - 15:55
fonte
2

Vorrei utilizzare un tipo di benna per aiutarti a ottimizzarlo.

Dato che le stringhe sono lunghezze diverse nell'esempio, e ci sono molti dati considerando che questo è un file piatto, vorrei semplicemente dividere il file in più parti in base al prefisso della stringa.

Quindi invece di avere strings.dat avrei il seguente:

  • a.dat
  • b.dat
    ...
  • z.dat

Se un determinato file è ancora troppo grande, ad esempio, una lettera comune come r o t è sproporzionatamente più grande, suddividila in bucket più piccoli:

  • r.dat
  • ra.dat
  • re.dat
    ...

Questo può continuare con rab.dat e così via.

Per trovare una stringa, inizia semplicemente con la stringa intera e cerca un file corrispondente al suo nome. Se non trovato, cerca un file che corrisponda alla stringa meno l'ultimo carattere. Fallo finché non viene trovata una corrispondenza o la stringa è di lunghezza zero (ad esempio, forse non c'è x.dat , quindi nessuna parola che inizia con x verrà mai trovata).

Esempio: qui ci sono alcuni file e una stringa che può essere localizzata in ciascuno di essi.

  • r.dat - rombo (no rh.dat )
  • ra.dat - rat (no rat.dat )
  • rab.dat - rabid (no rabi.dat )

Ogni file dovrebbe essere sufficientemente piccolo per una ricerca efficiente usando una scansione completa o una ricerca binaria, qualunque cosa tu ritenga sia appropriata data la quantità di dati.

vantaggi

  • I file di testo più piccoli sono più facili da gestire in un editor di testo se è necessario modificarli.
  • Cercare i file di testo può essere inefficiente a seconda della lingua, della libreria e della modalità file. Riducendo la quantità di dati in ogni file, questo può alleviare questo.
  • Da una prospettiva di complessità algoritmica questo non ti compra molto, semmai. Tuttavia, dal punto di vista pratico lo fa. File I / O è costoso, facilmente una delle operazioni più costose che un computer può eseguire (a meno che non si disponga di un SSD). Riducendo al minimo le ricerche / letture di file, attenuerai l'impatto sulle prestazioni reali della ricerca di 500 MB di dati ogni volta. Quanto? Definitelo per sicuro, ma mi sentirei a mio agio ad attaccarmi e dire che sarebbe una quantità misurabile.
risposta data 28.04.2014 - 19:11
fonte
1

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 =&gt 16;
    return unpack( '%' . HASH_KEY_SIZE_IN_BITS . 'A*', $_ );
}

$/ = "\r\n"; # Windows EOL
$offset = 0;
while(&lt&gt) {
    $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 &gt $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
    
risposta data 28.04.2014 - 16:06
fonte

Leggi altre domande sui tag