veloce struttura dati di accesso n-grammi

Question

veloce struttura dati di accesso n-grammi

#1 da (4 voti)
#2 da (0 voti)
#3 da (0 voti)
#4 da (-1 voti)

3

TL; DR

Esiste una struttura dati che mi consenta di sincronizzare rapidamente le parole in qualsiasi momento (ad esempio, "foo" corrisponde a "foobar" e "zoofoo") e, idealmente, restituisce un elenco di "caratteri che vengono visualizzati dopo il ago "(es., 'foo' dovrebbe restituire ['b', $]).

Sto implementando un algoritmo che genera parole casuali da un set di allenamento di altre parole.

In termini semplici, è fondamentalmente così:

Scegli un punto di partenza arbitrario.
Scegli il suffisso più lungo della parola corrente che è contenuto in almeno altre 2 parole
Scegli una di quelle parole a caso e aggiungi il prossimo carattere al lavoro corrente
GOTO 2 fino a "prossimo carattere" è EOW

per esempio, se la parola corrente è "tat", alcune opzioni valide sarebbero "potato" e "tattoo"; se la parola corrente è "ophtalmi", l'unica opzione è "ophtalmic", quindi cerchiamo se alcune parole contengono "phtalmi", "htalmi", "talmi" e così via.

Ho provato un paio di implementazioni: in uno, ho usato un trie popolato con ogni suffisso di ogni parola. Questo è molto veloce nel generare parole, ma il popolamento del trie è MOLTO lento (~ 4 milioni di parole non sono terminate in oltre 10 ore).

In un altro, ho generato un hash di:

for word in words:
    for suffix in tails(words):
        for prefix, suffix in prefixes(words): # prefixes("foo") = [("f","oo"),("fo","o"),("foo","")]
            ngrams[prefix].add(suffix) # this is a set

ed è molto più veloce nella lettura del set di allenamento, e molto veloce nel generare, ma richiede molta RAM.

E, infine, l'opzione stupida, della semplice ricerca

candidates = [word for word in words if string in words]

che richiede pochissima memoria, ma è molto più lento.

Esiste una struttura dati con il comportamento di cui ho bisogno?

data-structures search string-matching trie

posta Tordek 04.03.2014 - 03:41

fonte

4 risposte

0

Sto pensando ad alcune varianti di un trie .

Un'applicazione comune di un trie è la memorizzazione di un testo predittivo o di un dizionario di completamento automatico, come quello trovato su un telefono cellulare. Tali applicazioni sfruttano la capacità di un trie di cercare, inserire ed eliminare rapidamente le voci.

risposta data 04.03.2014 - 03:54

fonte

0

O alberi di ricerca ternaria o marisa-tries sembrano strutture dati che funzionano bene per la ricerca di prefissi comuni, che è quello che stai cercando di fare.

Dato che sembra che tu stia usando Python, qui hai un pacchetto per il fomer , mentre quest'ultimo sembra avere due collegamenti Python: il uno ufficiale basato su SWIG , ma anche < a href="https://github.com/kmike/marisa-trie"> uno non ufficiale basato su Cython .

risposta data 04.03.2014 - 14:35

fonte

-1

Potresti voler esaminare Lucene (tramite Elasticsearch o Solr) o un'altra soluzione basata sulla ricerca per il tuo problema. Lucene utilizza una struttura di dati dell'indice invertito per eseguire in modo efficiente le ricerche sulle stringhe. A un certo punto era esattamente un trie, ma non sono del tutto sicuro che l'attuale implementazione possa ancora essere considerata un trie dal momento che è stata elaborata e ottimizzata così tanto.

Una cosa carina di un motore di ricerca come Lucene è costituita da funzionalità di analisi del testo. Questi analizzatori possono essere concatenati per controllare quali stringhe sono posizionate nell'indice e anche quali stringhe sono usate per interrogare quell'indice.

Lucene ha costruito l'analisi di ngram, ma puoi anche scrivere facilmente la tua che prende il testo di input e li ritaglia in un modo personalizzato per soddisfare i tuoi requisiti di ricerca.

Per una pura soluzione di ricerca Python, puoi anche consultare Whoosh .

risposta data 04.03.2014 - 06:12

fonte

Leggi altre domande sui tag data-structures search string-matching trie

classe di messaggistica e stato globale Esiste l'e-commerce senza un carrello della spesa? [chiuso]

score 4 · Accepted Answer

La risposta classica sarebbe un trie che memorizza tutte le rotazioni di parole (in scrabble c'è una necessità molto simile e una struttura dati molto simile chiamata gaddag). Si scopre che puoi fare molto meglio (B-tree of words in cui il livello più basso è delta encoded), ma la cosa più semplice che puoi fare è memorizzare un elenco ordinato di tutte le rotazioni di tutte le parole nel tuo dizionario e la ricerca binaria di cose. Esempio:

Il nostro dizionario contiene la parola w = 'zoofoo' , quindi memorizziamo:

sorted(w[i:] + '^' + w[:i] for i in range(len(w)))
['foo^zoo', 'o^zoofo', 'ofoo^zo', 'oo^zoof', 'oofoo^z', 'zoofoo^']

Guarda, una di quelle voci inizia con 'foo' ! Possiamo trovarlo tramite la ricerca binaria e ricostruire la parola originale da 'foo^zoo' sfogliando il ^ .

Se puoi anche ordinare i tuoi input, puoi fare un'intersezione lineare dell'elenco di input e del dizionario di rotazione.