Trova tutte le corrispondenze parziali al vettore di unsigned

Question

Per un mio progetto AI, ho bisogno di applicare a uno stato fattorizzato tutte le regole che si applicano ai suoi componenti parziali. Questo deve essere fatto molto spesso, quindi sto cercando un modo per farlo il più velocemente possibile.

Ho intenzione di descrivere il mio problema con le stringhe, tuttavia il vero problema funziona allo stesso modo con i vettori di interi senza segno.

Ho un sacco di voci (di lunghezza N) come questo, che ho bisogno di memorizzare in qualche modo:

__a_b 
c_e__ 
___de 
abcd_ 
fffff 
__a__ 

mio input è una singola voce ciede a cui devo trovare, il più velocemente possibile , tutte le voci memorizzate che corrispondono ad esso. Per esempio in questo caso le partite sarebbero c_e__ e ___de. La rimozione e l'aggiunta di voci dovrebbero essere supportate, tuttavia non mi interessa quanto sia lento. Cosa vorrei essere il più veloce possibile è:

for (const auto & entry : matchedEntries(input)) 

mio problema, come detto, è quella in cui ogni lettera è in realtà un intero senza segno, e il vettore ha una lunghezza specificata (ma nota). Non ho requisiti per il modo in cui le voci dovrebbero essere archiviate, o quale tipo di metadati sarà associato a loro. L'algoritmo ingenuo di abbinamento di tutti è O (N), è possibile fare di meglio? Il numero di voci ragionevoli che ho bisogno di memorizzare è < = 100k.

Sto pensando che una sorta di ordinamento potrebbe aiutare, o qualche strana struttura ad albero, ma non riesco a trovare un buon modo per affrontare questo problema. Sembra anche che qualche word processor debba già fare, quindi qualcuno potrebbe essere in grado di aiutare.

Answer 1

Archiviare i dati in un albero, 1 ° livello rappresenta il 1 ° elemento (carattere o numero intero) e così via. Ciò significa che l'albero avrà una profondità costante di 5 (esclusa la radice) nell'esempio. Non preoccuparti dei caratteri jolly ("_") a questo punto. Basta archiviarli come gli altri elementi.

Durante la ricerca delle partite, attraversare l'albero eseguendo una ricerca per ampiezza e creare dinamicamente il set di risultati. Ogni volta che incontri un jolly, aggiungi un altro elemento al set di risultati per tutti gli altri nodi di questo livello che non corrispondono. Se nessun sottonodo corrisponde, rimuovere la voce dal set di risultati.

È inoltre necessario saltare le voci di ridondante quando si crea l'albero: Nel proprio esempio, __a_b è ridondante, perché ogni volta che corrisponde, corrisponde anche a __a__.

Answer 2

La soluzione più semplice è quella di creare un trie contenente le voci. Durante la ricerca del trie, si inizia nella root e si segue in modo ricorsivo un margine, che corrisponde al carattere del proprio input. Ci saranno al massimo due di questi bordi in ogni nodo, uno per il carattere jolly _ e uno per la lettera effettiva.

Nel peggiore dei casi è necessario seguire due spigoli da ciascun nodo, che aggiungerebbero fino a O (2^n) complessità, dove n è la lunghezza dell'input, mentre la complessità spaziale è lineare.

Un approccio diverso sarebbe quello di pre-elaborare le voci, per consentire la ricerca lineare. Questo è fondamentalmente ciò che compila le espressioni regolari.Per l'esempio, considera seguente espressione regolare che corrisponde l'ingresso desiderato:

(..a.b|c.e..|...de|abcd.|fffff|..a..) 

Questa espressione può essere implementato come un nondeterministic finite state automaton, con stato iniziale avente ε-mosse per un automa deterministico per ciascuna delle singole voci. Questo NFSA può quindi essere trasformato in un FSA deterministico, utilizzando lo standard powerset construction.

Sebbene questa costruzione possa aumentare sostanzialmente il numero di stati, la ricerca della parola di input può essere eseguita in tempo lineare, semplicemente simulando l'automa deterministico.

Di seguito è riportato un esempio di voci ab, a_, ba, _a e __. In primo luogo, inizia con un automa non deterministico, che rimuovendo le mosse ε e unendo stati equivalenti è in realtà un trie per l'insieme.

Quindi ruotare in una macchina deterministica, con stati corrispondenti a sottoinsiemi di stati del NFSA. Inizia nello stato 0 e per ciascun lato, diverso da _, crea lo stato successivo come unione degli stati nella macchina originale, che sono raggiungibili da qualsiasi stato nel set corrente.

Ad esempio, quando DFSA è nello stato 16, ciò significa che NFSA potrebbe essere nello stato 1 o 6. Dopo la transizione su a, la NFSA potrebbe arrivare agli stati 3 (da 1), 7 o 8 (da 6) - che sarà il tuo stato successivo in DFSA.

La struttura standard preserverebbe i limiti di _, ma possiamo ometterli, a condizione che l'input non contenga _.

Ora, se si dispone di una parola ab sull'ingresso, è simulare questo automa (vale a dire traversa il suo grafico di transizione) e finire in stato di 238, da cui è possibile recuperare facilmente le voci originali.

Answer 3

Ho in mente un algoritmo che ho intenzione di implementare e benchmark, ma descriverò già l'approccio. Necessita n_templates * template_length * n_symbols bit di memorizzazione (quindi per 100k modelli di lunghezza 100 e 256 simboli distinti necessita 2,56 Gb = 320 MB di RAM. Ciò non scalabili ben al gran numero di simboli meno succinct data structure viene utilizzato.

Query richiede O(n_templates * template_length * n_symbols) tempo ma deve eseguire abbastanza bene grazie alle operazioni di bit-wise

Diciamo che abbiamo dato insieme di modelli:.

__a_b 
c_e__ 
___de 
abcd_ 
_ied_ 
bi__e 

l'insieme di simboli è abcdei, per ogni simbolo abbiamo pre-calcolare una maschera di bit indicando se il modello differisce da th e simbolo in quella posizione o no:

aaaaa bbbbb ccccc ddddd eeeee iiiii 
....b ..a.. ..a.b ..a.b ..a.b ..a.b 
c.e.. c.e.. ..e.. c.e.. c.... c.e.. 
...de ...de ...de ....e ...d. ...de 
.bcd. a.cd. ab.d. abc.. abcd. abcd. 
.ied. .ied. .ied. .ie.. .i.d. ..ed. 
bi..e .i..e bi..e bi..e bi... b...e 

stesse tabelle espresse in binario:

aaaaa bbbbb ccccc ddddd eeeee iiiii 
00001 00100 00101 00101 00101 00101 
10100 10100 00100 10100 10000 10100 
00011 00011 00011 00001 00010 00011 
01110 10110 11010 11100 11110 11110 
01110 01110 01110 01100 01010 00110 
11001 01001 11001 11001 11000 10001 

Questi sono memorizzati in ordine colonnare, 64 templates/intero senza segno.Per determinare quale modello corrisponde ciede controlliamo la prima colonna della c tabella, colonna 2 ° da i, 3 ° da e e così via:

  ciede ciede 
__a_b ..a.b 00101 
c_e__ ..... 00000 
___de ..... 00000 
abcd_ abc.. 11100 
_ied_ ..... 00000 
bi__e b.... 10000 

Troviamo corrispondenti modelli come righe di zeri, il che indica che non sono state riscontrate . Siamo in grado di controllare 64 modelli in una sola volta, e l'algoritmo in sé è molto semplice (codice Python-like):

for i_block in range(n_templates/64): 
    mask = 0 
    for i in range(template_length): 
     # Accumulate difference-indicating bits 
     mask |= tables[i_block][word[i]][i] 

     if mask == 0xFFFFFFFF: 
      # All templates differ, we can stop early 
      break 

    for i in range(64): 
     if mask & (1 << i) == 0: 
      print('Match at template ' + (i_block * 64 + i)) 

Come ho detto non ho ancora provato in realtà del presente, quindi non ho idea di quanto velocemente è in pratica