Domanda Buon algoritmo e struttura dati per cercare parole con lettere mancanti?


quindi ho bisogno di scrivere un algoritmo efficiente per cercare parole con lettere mancanti in un dizionario e voglio l'insieme di possibili parole.

Ad esempio, se ho th ?? e, potrei tornare questi, quelli, theme, there.etc.

Mi chiedevo se qualcuno potesse suggerire alcune strutture dati o algoritmi che dovrei usare.

Grazie!

EDIT: Un Trie è troppo spazio-inefficiente e lo renderebbe troppo lento. Qualche altra modifica di idee?

AGGIORNAMENTO: Ci saranno fino a DUE punti interrogativi e quando si verificano due punti interrogativi, si verificheranno in sequenza.

Attualmente sto usando 3 tabelle hash per quando è una corrispondenza esatta, 1 punto interrogativo e 2 punti interrogativi. Dato un dizionario, ho cancellato tutte le parole possibili. Ad esempio, se ho la parola WORD. Ho cancellato WORD,? ORD, W? RD, WO? D, WOR ?, ?? RD, W ?? D, WO ??. nel dizionario Quindi uso una lista di link per collegare insieme le collisioni. Quindi dire hash (W? RD) = hash (STR? NG) = 17. hashtab (17) punterà a WORD e WORD puntano a STRING perché è una lista collegata.

La tempistica della ricerca media di una parola è di circa 2e-6s. Sto cercando di fare meglio, preferibilmente nell'ordine di 1e-9.

EDIT: Non ho ancora rivisto questo problema ma ci sono voluti 0,5 secondi per inserimenti di voci da 3m e ci sono voluti 4 secondi per la ricerca di 3m di voci.

Grazie!


56
2017-12-23 14:24


origine


risposte:


Credo che in questo caso sia meglio usare solo un file flat in cui ogni parola si trova in una riga. Con questo puoi usare comodamente la potenza di una ricerca di espressioni regolari, che è altamente ottimizzata e probabilmente supererà qualsiasi struttura di dati che puoi escogitare per questo problema.

Soluzione n. 1: utilizzo di Regex

Questo sta funzionando con il codice Ruby per questo problema:

def query(str, data)    
  r = Regexp.new("^#{str.gsub("?", ".")}$")
  idx = 0
  begin
    idx = data.index(r, idx)
    if idx
      yield data[idx, str.size]
      idx += str.size + 1
    end
  end while idx
end

start_time = Time.now
query("?r?te", File.read("wordlist.txt")) do |w|
  puts w
end
puts Time.now - start_time

Il file wordlist.txt contiene 45425 parole (scaricabile Qui). L'output del programma per la query ?r?te è:

brute
crate
Crete
grate
irate
prate
write
wrote
0.013689

Quindi ci vogliono solo 37 millisecondi per leggere l'intero file e trovare tutte le corrispondenze in esso. E si adatta molto bene a tutti i tipi di modelli di query, anche quando un Trie è molto lento:

domanda ????????????????e

counterproductive
indistinguishable
microarchitecture
microprogrammable
0.018681

domanda ?h?a?r?c?l?

theatricals
0.013608

Questo sembra abbastanza veloce per me.

Soluzione n. 2: Regex con dati preparati

Se vuoi andare ancora più veloce, puoi dividere la lista di parole in stringhe che contengono parole di uguale lunghezza e cerca solo quella corretta in base alla lunghezza della query. Sostituisci le ultime 5 righe con questo codice:

def query_split(str, data)
  query(str, data[str.length]) do |w|
    yield w
  end
end

# prepare data    
data = Hash.new("")
File.read("wordlist.txt").each_line do |w|
  data[w.length-1] += w
end

# use prepared data for query
start_time = Time.now
query_split("?r?te", data) do |w|
  puts w
end
puts Time.now - start_time

La costruzione della struttura dati richiede ora circa 0,4 secondi, ma tutte le query sono circa 10 volte più veloci (a seconda del numero di parole con quella lunghezza):

  • ?r?te 0,001112 sec
  • ?h?a?r?c?l? 0.000852 sec
  • ????????????????e 0,000169 sec

Soluzione 3: One Big Hashtable (requisiti aggiornati)

Dal momento che hai modificato i tuoi requisiti, puoi facilmente espandere la tua idea per utilizzare solo un grosso hashtable che contiene tutti i risultati precalcolati. Ma invece di aggirare le collisioni, puoi contare sulle prestazioni di un hash correttamente implementato.

Qui creo un grande hashtable, in cui ogni query possibile viene mappata a un elenco di risultati:

def create_big_hash(data)
  h = Hash.new do |h,k|
    h[k] = Array.new
  end    
  data.each_line do |l|
    w = l.strip
    # add all words with one ?
    w.length.times do |i|
      q = String.new(w)
      q[i] = "?"
      h[q].push w
    end
    # add all words with two ??
    (w.length-1).times do |i|
      q = String.new(w)      
      q[i, 2] = "??"
      h[q].push w
    end
  end
  h
end

# prepare data    
t = Time.new
h = create_big_hash(File.read("wordlist.txt"))
puts "#{Time.new - t} sec preparing data\n#{h.size} entries in big hash"

# use prepared data for query
t = Time.new
h["?ood"].each do |w|
  puts w
end
puts (Time.new - t)

L'output è

4.960255 sec preparing data
616745 entries in big hash
food
good
hood
mood
wood
2.0e-05

La prestazione della query è O (1), è solo una ricerca nella tabella hash. Il tempo 2.0e-05 è probabilmente inferiore alla precisione del timer. Quando lo eseguo 1000 volte, ottengo una media di 1.958e-6 secondi per query. Per farlo più veloce, vorrei passare a C ++ e utilizzare il Google Sparse Hash che è estremamente efficiente in termini di memoria e veloce.

Soluzione 4: diventa davvero serio

Tutte le soluzioni di cui sopra funzionano e dovrebbero essere sufficienti per molti casi d'uso. Se vuoi davvero fare sul serio e avere un sacco di tempo libero a portata di mano, leggi alcuni buoni documenti:


66
2017-12-30 18:50



Dati i limiti attuali:

  • Ci saranno fino a 2 punti interrogativi
  • Quando ci sono 2 punti interrogativi, appaiono insieme
  • Ci sono ~ 100.000 parole nel dizionario, la lunghezza media delle parole è 6.

Ho due soluzioni praticabili per te:

La soluzione veloce: HASH

Puoi usare un hash con le chiavi che sono le tue parole con un massimo di due "?", Ei valori sono un elenco di parole appropriate. Questo hash avrà circa 100.000 + 100.000 * 6 + 100.000 * 5 = 1.200.000 voci (se hai 2 punti interrogativi, devi solo trovare il posto del primo ...). Ogni voce può salvare un elenco di parole o un elenco di puntatori alle parole esistenti. Se si salva un elenco di puntatori e si assume che ci siano in media meno di 20 parole corrispondenti a ciascuna parola con due "?", La memoria aggiuntiva è inferiore a 20 * 1.200.000 = 24.000.000.

Se ogni dimensione del puntatore è 4 byte, il requisito di memoria qui è (24.000.000 + 1.200.000) * 4 byte = 100.800.000 byte ~ = 96 mega byte.

Per riassumere questa soluzione:

  • Consumo di memoria: ~ 96 MB
  • Tempo per ciascuna ricerca: calcolo di una funzione hash e successivo a un puntatore. O (1)

Nota: se si desidera utilizzare un hash di dimensioni ridotte, è possibile, ma è preferibile salvare una struttura di ricerca bilanciata in ogni voce anziché in un elenco collegato, per prestazioni migliori.

Lo spazio esperto, ma soluzione ancora molto veloce: variazione TRIE

Questa soluzione utilizza la seguente osservazione:

Se la '?' i segni erano alla fine della parola, Trie sarebbe una soluzione eccellente.

La ricerca nel trie cercava la lunghezza della parola, e per l'ultimo paio di lettere, una traversata DFS porterebbe tutti i finali. Soluzione molto veloce e molto adatta alla memoria.

Quindi usiamo questa osservazione per costruire qualcosa che funzioni esattamente così.

Puoi pensare a ogni parola che hai nel dizionario, come una parola che termina con @ (o qualsiasi altro simbolo che non esiste nel tuo dizionario). Quindi la parola 'spazio' sarebbe 'spazio @'. Ora, se si ruota ciascuna parola, con il segno '@', si ottiene quanto segue:

space@, pace@s, ace@sp, *ce@spa*, e@spac

(no @ come prima lettera).

Se inserisci tutte queste variazioni in una TRIE, puoi facilmente trovare la parola che stai cercando alla lunghezza della parola, ruotando la tua parola.

Esempio: Vuoi trovare tutte le parole che si adattano 's ?? ce' (uno di loro è lo spazio, un altro è lo slice). Costruisci la parola: s ?? ce @ e ruotala in modo che il? il segno è alla fine cioè "ce @ s ??"

Tutte le variazioni di rotazione esistono all'interno del trie, e in particolare 'ce @ spa' (contrassegnato con * sopra). Dopo aver trovato l'inizio, è necessario esaminare tutte le continuazioni nella lunghezza appropriata e salvarle. Quindi, devi ruotarli di nuovo in modo che @ sia l'ultima lettera e walla - hai tutte le parole che stavi cercando!

Per riassumere questa soluzione:

  • Consumo di memoria: Per ogni parola, tutte le sue rotazioni appaiono nel trie. In media, * 6 della dimensione della memoria viene salvata nel trie. La dimensione trie è intorno a * 3 (solo indovinando ...) dello spazio salvato al suo interno. Quindi lo spazio totale necessario per questo trie è 6 * 3 * 100.000 = 1.800.000 parole ~ = 6.8 mega byte.

  • Tempo per ogni ricerca:

    • ruotando la parola: O (lunghezza della parola)
    • cercare l'inizio nel trie: O (lunghezza della parola)
    • andando oltre tutte le finali: O (numero di partite)
    • rotazione delle estremità: O (lunghezza totale delle risposte)

    Per riassumere, è molto molto veloce e dipende dalla lunghezza della parola * piccola costante.

Per riassumere...

La seconda scelta ha una grande complessità tempo / spazio e sarebbe la migliore opzione da usare. Ci sono alcuni problemi con la seconda soluzione (nel qual caso potresti voler utilizzare la prima soluzione):

  • Più complesso da implementare. Non sono sicuro che esistano linguaggi di programmazione con i programmi di prova incorporati pronti per l'uso. Se non c'è, significa che dovrai implementarlo tu stesso ...
  • Non scala bene. Se domani decidi che hai bisogno dei tuoi punti interrogativi sparsi per tutta la parola, e non necessariamente uniti, dovrai pensare a come adattare la seconda soluzione. Nel caso della prima soluzione, è abbastanza facile generalizzare.

24
2017-12-23 15:07



Per me questo problema sembra una buona misura per a prova struttura dati. Inserisci l'intero dizionario nel tuo trie, quindi cerca la parola. Per una lettera mancante dovresti provare tutti i sotto-tentativi, che dovrebbero essere relativamente facili da fare con un approccio ricorsivo.

MODIFICARE: Ho appena scritto una semplice implementazione di questo in Ruby: http://gist.github.com/262667.


22
2017-12-24 11:45



Grafico Aciclico Diretto sarebbe perfetta struttura dati per questo problema. Combina l'efficienza di un trie (il trie può essere visto come un caso speciale di DAWG), ma è molto più efficiente nello spazio. Tipico DAWG prenderà una frazione delle dimensioni che avrebbe bisogno di un semplice file di testo con le parole.

Enumerare le parole che soddisfano condizioni specifiche è semplice e identico a quello di trie - devi attraversare il grafico in modo approfondito.


16
2017-12-30 19:08



La seconda soluzione di Anna è l'ispirazione per questo.

Innanzitutto, carica tutte le parole in memoria e dividi il dizionario in sezioni in base alla lunghezza della parola.

Per ogni lunghezza, marca n copie di una matrice di puntatori alle parole. Ordina ogni array in modo che le stringhe vengano visualizzate in ordine quando ruotato di un certo numero di lettere. Ad esempio, supponiamo che l'elenco originale di parole di 5 lettere sia [piano, mela, spazio, treno, felice, pila, hack]. Quindi i tuoi cinque array di indicatori saranno:

rotated by 0 letters: [apple, hacks, happy, plane, space, stack, train]
rotated by 1 letter:  [hacks, happy, plane, space, apple, train, stack]
rotated by 2 letters: [space, stack, train, plane, hacks, apple, happy]
rotated by 3 letters: [space, stack, train, hacks, apple, plane, happy]
rotated by 4 letters: [apple, plane, space, stack, train, hacks, happy]

(Invece di puntatori, puoi usare numeri interi che identificano le parole, se questo fa risparmiare spazio sulla tua piattaforma).

Per cercare, basta chiedere quanto si dovrebbe ruotare il modello in modo che i punti interrogativi appaiano alla fine. Quindi puoi effettuare una ricerca binaria nell'elenco appropriato.

Se hai bisogno di trovare le corrispondenze per ?? ppy, dovresti ruotare quello per 2 per rendere ppy ??. Quindi guarda nell'array che è in ordine quando ruotato di 2 lettere. Una rapida ricerca binaria scopre che "felice" è l'unica partita.

Se hai bisogno di trovare le corrispondenze per th ?? g, dovresti ruotare quello per 4 per fare gth ??. Quindi guarda nell'array 4, dove una ricerca binaria trova che non ci sono corrispondenze.

Questo funziona indipendentemente da quanti punti interrogativi ci sono, purché compaiano tutti insieme.

Spazio richiesto oltre al dizionario stesso: per parole di lunghezza N, ciò richiede spazio per (N volte il numero di parole di lunghezza N) puntatori o interi.

Tempo per ricerca: O (log n) dove n è il numero di parole della lunghezza appropriata.

Implementazione in Python:

import bisect

class Matcher:
    def __init__(self, words):
        # Sort the words into bins by length.
        bins = []
        for w in words:
            while len(bins) <= len(w):
                bins.append([])
            bins[len(w)].append(w)

        # Make n copies of each list, sorted by rotations.
        for n in range(len(bins)):
            bins[n] = [sorted(bins[n], key=lambda w: w[i:]+w[:i]) for i in range(n)]
        self.bins = bins

    def find(self, pattern):
        bins = self.bins
        if len(pattern) >= len(bins):
            return []

        # Figure out which array to search.
        r = (pattern.rindex('?') + 1) % len(pattern)
        rpat = (pattern[r:] + pattern[:r]).rstrip('?')
        if '?' in rpat:
            raise ValueError("non-adjacent wildcards in pattern: " + repr(pattern))
        a = bins[len(pattern)][r]

        # Binary-search the array.
        class RotatedArray:
            def __len__(self):
                return len(a)
            def __getitem__(self, i):
                word = a[i]
                return word[r:] + word[:r]
        ra = RotatedArray()
        start = bisect.bisect(ra, rpat)
        stop = bisect.bisect(ra, rpat[:-1] + chr(ord(rpat[-1]) + 1))

        # Return the matches.
        return a[start:stop]

words = open('/usr/share/dict/words', 'r').read().split()
print "Building matcher..."
m = Matcher(words)  # takes 1-2 seconds, for me
print "Done."

print m.find("st??k")
print m.find("ov???low")

Sul mio computer, il dizionario di sistema è grande 909 KB e questo programma utilizza circa 3,2 MB di memoria oltre a ciò che serve solo per memorizzare le parole (i puntatori sono 4 byte). Per questo dizionario, è possibile ridurlo a metà utilizzando numeri interi a 2 byte anziché puntatori, poiché ce ne sono meno di 216 parole di ogni lunghezza.

misure: Sulla mia macchina, m.find("st??k") funziona in 0,000032 secondi, m.find("ov???low") in 0,000034 secondi e m.find("????????????????e") in 0.000023 secondi.

Scrivendo la ricerca binaria invece di usare class RotatedArray e il bisect libreria, ho ottenuto quei primi due numeri fino a 0.000016 secondi: due volte più veloce. L'implementazione di questo in C ++ lo renderebbe ancora più veloce.


9
2017-12-23 14:42



Per prima cosa abbiamo bisogno di un modo per confrontare la stringa di query con una determinata voce. Assumiamo una funzione usando regex: matches(query,trialstr).

Un algoritmo O (n) dovrebbe semplicemente scorrere ogni voce di elenco (il tuo dizionario verrebbe rappresentato come una lista nel programma), confrontando ciascuno con la stringa di query.

Con un po 'di pre-calcolo, puoi migliorare questo aspetto per un numero elevato di query creando un ulteriore elenco di parole per ogni lettera, in modo che il tuo dizionario possa avere il seguente aspetto:

wordsbyletter = { 'a' : ['aardvark', 'abacus', ... ],
                  'b' : ['bat', 'bar', ...],
                  .... }

Tuttavia, questo sarebbe di uso limitato, in particolare se la stringa di query inizia con un carattere sconosciuto. Quindi possiamo fare ancora meglio notando dove in una determinata parola giace una lettera particolare, generando:

wordsmap = { 'a':{ 0:['aardvark', 'abacus'],
                   1:['bat','bar'] 
                   2:['abacus']},
             'b':{ 0:['bat','bar'],
                   1:['abacus']},
             ....
           }

Come puoi vedere, senza usare indici, finirai per aumentare enormemente la quantità di spazio di archiviazione richiesto - in particolare un dizionario di n parole e la lunghezza media m richiederà nm2 di stoccaggio. Tuttavia, potresti velocemente fare il tuo look per ottenere tutte le parole da ciascun set che possono corrispondere.

L'ottimizzazione finale (che si può usare a priori nell'approccio ingenuo) è anche quella di separare tutte le parole della stessa lunghezza in negozi separati, poiché si sa sempre quanto è lunga la parola.

Questa versione sarebbe O (kx) dove K è il numero di conosciuto lettere nella parola di interrogazione e X=X(n) è il momento di cercare un singolo elemento in un dizionario di lunghezza n nella tua implementazione (solitamente log (n).

Quindi con un dizionario finale come:

allmap = { 
           3 : { 
                  'a' : {
                          1 : ['ant','all'],
                          2 : ['bar','pat']
                         }
                  'b' : {
                          1 : ['bar','boy'],
                      ...
                }
           4 : {
                  'a' : {
                          1 : ['ante'],
                      ....

Quindi il nostro algoritmo è solo:

possiblewords = set()
firsttime = True
wordlen = len(query)
for idx,letter in enumerate(query):
    if(letter is not '?'):
        matchesthisletter = set(allmap[wordlen][letter][idx])
        if firsttime:
             possiblewords = matchesthisletter
        else:
             possiblewords &= matchesthisletter

Alla fine, il set possiblewords conterrà tutte le lettere corrispondenti.


4
2017-12-23 14:33



Se generate tutte le parole possibili che corrispondono al modello (arate, arbte, arcte ... zryte, zrzte) e poi le guardate in alto in una rappresentazione ad albero binario del dizionario, avrà le caratteristiche medie delle prestazioni di O (e ^ N1 * log (N2)) dove N1 è il numero di punti interrogativi e N2 è la dimensione del dizionario. Sembra abbastanza buono per me, ma sono sicuro che è possibile capire un algoritmo migliore.

MODIFICARE: Se avrete più di tre punti di domanda, date un'occhiata alla risposta di Phil H e al suo approccio di indicizzazione delle lettere.


3
2017-12-23 15:29



Supponi di avere abbastanza memoria, potresti costruire una gigantesca mappa di hash per fornire la risposta in tempo costante. Ecco un rapido esempio in python:

from array import array
all_words = open("english-words").read().split()
big_map = {}

def populate_map(word):
  for i in range(pow(2, len(word))):
    bin = _bin(i, len(word))
    candidate = array('c', word)
    for j in range(len(word)):
      if bin[j] == "1":
        candidate[j] = "?"
    if candidate.tostring() in big_map:
      big_map[candidate.tostring()].add(word)
    else:
      big_map[candidate.tostring()] = set([word])

def _bin(x, width):
    return ''.join(str((x>>i)&1) for i in xrange(width-1,-1,-1))

def run():
  for word in all_words:
    populate_map(word)

run()

>>> big_map["y??r"]
set(['your', 'year'])
>>> big_map["yo?r"]
set(['your'])
>>> big_map["?o?r"]
set(['four', 'poor', 'door', 'your', 'hour'])

3
2017-12-23 14:30



Puoi dare un'occhiata a come è finito un incantesimo. Indica suggerimenti di parole corrette per le parole errate.


2
2017-12-30 21:26



Costruisci un hash set di tutte le parole. Per trovare le corrispondenze, sostituire i punti interrogativi nel motivo con ciascuna combinazione possibile di lettere. Se ci sono due punti interrogativi, una query è composta da 262 = 676 ricerche di hash veloci, costanti e attese.

import itertools

words = set(open("/usr/share/dict/words").read().split())

def query(pattern):
    i = pattern.index('?')
    j = pattern.rindex('?') + 1
    for combo in itertools.product('abcdefghijklmnopqrstuvwxyz', repeat=j-i):
        attempt = pattern[:i] + ''.join(combo) + pattern[j:]
        if attempt in words:
            print attempt

Questo usa meno memoria della mia altra risposta, ma diventa esponenzialmente più lento man mano che aggiungi altri punti interrogativi.


2
2018-01-03 12:48