Aggiunta successiva di carattere per ottenere la parola più lunga nel dizionario

Question

Dato un dizionario di parole e un carattere iniziale. trova la parola più lunga possibile nel dizionario aggiungendo successivamente un carattere alla parola. In ogni caso, la parola dovrebbe essere una parola valida nel dizionario.

ex: a -> a -> cat -> carrello -> grafico ....

Answer 1

L'approccio forza bruta sarebbe quello di provare ad aggiungere le lettere a ciascun indice disponibile utilizzando una ricerca in profondità.

Quindi, a partire da 'a', ci sono due posti in cui è possibile aggiungere una nuova lettera. Di fronte o dietro la 'a', rappresentata da punti sotto.

.a.

Se si aggiunge una 't', ora ci sono tre posizioni.

.a.t.

Si può provare ad aggiungere tutte le 26 lettere per ogni posizione disponibile. Il dizionario in questo caso può essere un semplice hashtable. Se aggiungi una "z" nel mezzo, ottieni "azt" che non si troverà nella tabella delle hash, quindi non proseguirai lungo quel percorso nella ricerca.

Modifica: il grafico di Nick Johnson mi ha fatto incuriosire su quale sarebbe il grafico di tutti i percorsi massimali. Si tratta di un'immagine di grandi dimensioni (1,6 MB) qui:

http://www.michaelfogleman.com/static/images/word_graph.png

Edit: Ecco un'implementazione di Python. L'approccio forza bruta funziona in realtà in un tempo ragionevole (alcuni secondi, a seconda della lettera iniziale).

import heapq 

letters = 'abcdefghijklmnopqrstuvwxyz' 

def search(words, word, path): 
    path.append(word) 
    yield tuple(path) 
    for i in xrange(len(word)+1): 
     before, after = word[:i], word[i:] 
     for c in letters: 
      new_word = '%s%s%s' % (before, c, after) 
      if new_word in words: 
       for new_path in search(words, new_word, path): 
        yield new_path 
    path.pop() 

def load(path): 
    result = set() 
    with open(path, 'r') as f: 
     for line in f: 
      word = line.lower().strip() 
      result.add(word) 
    return result 

def find_top(paths, n): 
    gen = ((len(x), x) for x in paths) 
    return heapq.nlargest(n, gen) 

if __name__ == '__main__': 
    words = load('TWL06.txt') 
    gen = search(words, 'b', []) 
    top = find_top(gen, 10) 
    for path in top: 
     print path 

Naturalmente, ci sarà un sacco di legami nella risposta. Questo stamperà i primi risultati N, misurati in base alla lunghezza dell'ultima parola.

Uscita per lettera iniziale 'a', utilizzando il dizionario TWL06 Scrabble.

(10, ('a', 'ta', 'tap', 'tape', 'taped', 'tamped', 'stamped', 'stampede', 'stampedes', 'stampeders')) 
(10, ('a', 'ta', 'tap', 'tape', 'taped', 'tamped', 'stamped', 'stampede', 'stampeder', 'stampeders')) 
(10, ('a', 'ta', 'tan', 'tang', 'stang', 'strang', 'strange', 'strangle', 'strangles', 'stranglers')) 
(10, ('a', 'ta', 'tan', 'tang', 'stang', 'strang', 'strange', 'strangle', 'strangler', 'stranglers')) 
(10, ('a', 'ta', 'tan', 'tang', 'stang', 'strang', 'strange', 'stranges', 'strangles', 'stranglers')) 
(10, ('a', 'ta', 'tan', 'tang', 'stang', 'strang', 'strange', 'stranges', 'strangers', 'stranglers')) 
(10, ('a', 'ta', 'tan', 'tang', 'stang', 'strang', 'strange', 'stranges', 'strangers', 'estrangers')) 
(10, ('a', 'ta', 'tan', 'tang', 'stang', 'strang', 'strange', 'stranges', 'estranges', 'estrangers')) 
(10, ('a', 'ta', 'tan', 'tang', 'stang', 'strang', 'strange', 'stranger', 'strangler', 'stranglers')) 
(10, ('a', 'ta', 'tan', 'tang', 'stang', 'strang', 'strange', 'stranger', 'strangers', 'stranglers')) 

e qui sono i risultati per ogni lettera iniziale. Naturalmente, viene fatta un'eccezione sul fatto che la singola lettera iniziale non deve essere nel dizionario. Solo una parola di 2 lettere che può essere formata con esso.

(10, ('a', 'ta', 'tap', 'tape', 'taped', 'tamped', 'stamped', 'stampede', 'stampedes', 'stampeders')) 
(9, ('b', 'bo', 'bos', 'bods', 'bodes', 'bodies', 'boodies', 'bloodies', 'bloodiest')) 
(1, ('c',)) 
(10, ('d', 'od', 'cod', 'coed', 'coped', 'comped', 'compted', 'competed', 'completed', 'complected')) 
(10, ('e', 're', 'rue', 'ruse', 'ruses', 'rouses', 'arouses', 'carouses', 'carousels', 'carrousels')) 
(9, ('f', 'fe', 'foe', 'fore', 'forge', 'forges', 'forgoes', 'forgoers', 'foregoers')) 
(10, ('g', 'ag', 'tag', 'tang', 'stang', 'strang', 'strange', 'strangle', 'strangles', 'stranglers')) 
(9, ('h', 'sh', 'she', 'shes', 'ashes', 'sashes', 'slashes', 'splashes', 'splashers')) 
(11, ('i', 'pi', 'pin', 'ping', 'oping', 'coping', 'comping', 'compting', 'competing', 'completing', 'complecting')) 
(7, ('j', 'jo', 'joy', 'joky', 'jokey', 'jockey', 'jockeys')) 
(9, ('k', 'ki', 'kin', 'akin', 'takin', 'takins', 'takings', 'talkings', 'stalkings')) 
(10, ('l', 'la', 'las', 'lass', 'lassi', 'lassis', 'lassies', 'glassies', 'glassines', 'glassiness')) 
(10, ('m', 'ma', 'mas', 'mars', 'maras', 'madras', 'madrasa', 'madrassa', 'madrassas', 'madrassahs')) 
(11, ('n', 'in', 'pin', 'ping', 'oping', 'coping', 'comping', 'compting', 'competing', 'completing', 'complecting')) 
(10, ('o', 'os', 'ose', 'rose', 'rouse', 'rouses', 'arouses', 'carouses', 'carousels', 'carrousels')) 
(11, ('p', 'pi', 'pin', 'ping', 'oping', 'coping', 'comping', 'compting', 'competing', 'completing', 'complecting')) 
(3, ('q', 'qi', 'qis')) 
(10, ('r', 're', 'rue', 'ruse', 'ruses', 'rouses', 'arouses', 'carouses', 'carousels', 'carrousels')) 
(10, ('s', 'us', 'use', 'uses', 'ruses', 'rouses', 'arouses', 'carouses', 'carousels', 'carrousels')) 
(10, ('t', 'ti', 'tin', 'ting', 'sting', 'sating', 'stating', 'estating', 'restating', 'restarting')) 
(10, ('u', 'us', 'use', 'uses', 'ruses', 'rouses', 'arouses', 'carouses', 'carousels', 'carrousels')) 
(1, ('v',)) 
(9, ('w', 'we', 'wae', 'wake', 'wakes', 'wackes', 'wackest', 'wackiest', 'whackiest')) 
(8, ('x', 'ax', 'max', 'maxi', 'maxim', 'maxima', 'maximal', 'maximals')) 
(8, ('y', 'ye', 'tye', 'stye', 'styed', 'stayed', 'strayed', 'estrayed')) 
(8, ('z', 'za', 'zoa', 'zona', 'zonae', 'zonate', 'zonated', 'ozonated')) 

Answer 2

Se si vuole fare questo, una volta, mi piacerebbe fare il seguente (generalizzata al problema di iniziare con una parola piena):

Prendete il vostro intero dizionario e buttare via tutto ciò che non ha un superset dei caratteri nella tua parola target (diciamo che ha lunghezza m). Quindi inserire le parole rimanenti per lunghezza. Per ogni parola di lunghezza m+1, prova a rilasciare ogni lettera e vedere se ciò produce la parola desiderata. Altrimenti, buttalo. Quindi controlla ogni parola di lunghezza m+2 rispetto alla serie di lunghezza valida m+1, eliminando quelle che non possono essere ridotte. Continua finché non trovi un set vuoto; l'ultima cosa che hai trovato sarà la più lunga.

Se si desidera velocizzare la ricerca, creo un suffisso-albero- come la struttura dati.

Raggruppa tutte le parole per lunghezza. Per ogni parola di lunghezza 2, posiziona ognuno dei suoi due caratteri in un set di "parole crociate" e aggiungi quella parola a ciascun set di "superword" dei personaggi. Ora hai un collegamento tra tutte le parole valide di lunghezza 2 e tutti i caratteri. Fai lo stesso con parole di lunghezza 3 e parole valide di lunghezza 2. Ora puoi iniziare da qualche parte in questa gerarchia e fare una ricerca in ampiezza per trovare il ramo più profondo.

---

Edit: la velocità di questa soluzione dipenderà molto dalla struttura della lingua, ma se decidiamo di costruire tutto utilizzando i set con log(n) prestazioni per tutte le operazioni (ad esempio usiamo alberi rosso-neri o simili), e abbiamo N(m) parole di lunghezza m, quindi per creare il collegamento tra le parole di lunghezza m+1 e m sarà circa (m+1)*m*N(m+1)*log(N(m)) tempo (tenendo conto che i confronti di stringa prendono tempo lineare nella lunghezza della stringa). Dal momento che abbiamo a che fare questo per tutte le lunghezze di parola, il tempo di esecuzione per la costruzione della struttura di dati completo sarà qualcosa dell'ordine di

(typical word length)^3 * (dictionary length) * log (dictionary length/word length) 

(Il binning iniziale in parole di una certa lunghezza avrà tempo lineare quindi può essere trascurato, la formula effettiva per il runtime è complicata perché dipende dalla distribuzione delle lunghezze delle parole, nel caso in cui lo si stia facendo da una singola parola è ancora più complicato perché dipende dal numero atteso di parole più lunghe che hanno sottotitoli più brevi .)

Answer 3

Supponendo che sia necessario farlo ripetutamente (o si desidera la risposta per ognuna delle 26 lettere), farlo all'indietro:

1. Caricare un dizionario, e di risolvere per lunghezza, scendendo
2. Stabilire una mappatura, inizialmente vuoto, tra parole e (estensione, max_len) tuple.
3. Per ogni parola nella lista ordinata:
   1. Se è già nella mappatura, recuperare il massimo len.
   2. Se non lo è, imposta la lunghezza massima della parola.
   3. Esamina ogni parola prodotta eliminando un carattere. Se questa parola non è nella mappatura, o la nostra max_len supera il max_len della parola già nella mappatura, aggiornare la mappatura con la parola corrente e max_len

Quindi, per ottenere la catena per una data prefisso, inizia semplicemente con quel prefisso e guarda ripetutamente e le sue estensioni nel dizionario.

Ecco il codice di esempio Python:

words = [x.strip().lower() for x in open('/usr/share/dict/words')] 
words.sort(key=lambda x:len(x), reverse=True) 
word_map = {} # Maps words to (extension, max_len) tuples 

for word in words: 
    if word in word_map: 
    max_len = word_map[word][1] 
    else: 
    max_len = len(word) 
    for i in range(len(word)): 
    new_word = word[:i] + word[i+1:] 
    if new_word not in word_map or word_map[new_word][2] < max_len: 
     word_map[new_word] = (word, max_len) 

# Get a chain for each letter 
for term in "abcdefghijklmnopqrstuvwxyz": 
    chain = [term] 
    while term in word_map: 
    term = word_map[term][0] 
    chain.append(term) 
    print chain 

e la sua uscita per ogni lettera dell'alfabeto:

['a', 'ah', 'bah', 'bach', 'brach', 'branch', 'branchi', 'branchia', 'branchiae', 'branchiate', 'abranchiate'] 
['b', 'ba', 'bac', 'bach', 'brach', 'branch', 'branchi', 'branchia', 'branchiae', 'branchiate', 'abranchiate'] 
['c', 'ca', 'cap', 'camp', 'campo', 'campho', 'camphor', 'camphory', 'camphoryl', 'camphoroyl'] 
['d', 'ad', 'cad', 'card', 'carid', 'carida', 'caridea', 'acaridea', 'acaridean'] 
['e', 'er', 'ser', 'sere', 'secre', 'secret', 'secreto', 'secretor', 'secretory', 'asecretory'] 
['f', 'fo', 'fot', 'frot', 'front', 'afront', 'affront', 'affronte', 'affronted'] 
['g', 'og', 'log', 'logy', 'ology', 'oology', 'noology', 'nosology', 'nostology', 'gnostology'] 
['h', 'ah', 'bah', 'bach', 'brach', 'branch', 'branchi', 'branchia', 'branchiae', 'branchiate', 'abranchiate'] 
['i', 'ai', 'lai', 'lain', 'latin', 'lation', 'elation', 'delation', 'dealation', 'dealbation'] 
['j', 'ju', 'jug', 'juga', 'jugal', 'jugale'] 
['k', 'ak', 'sak', 'sake', 'stake', 'strake', 'straked', 'streaked'] 
['l', 'la', 'lai', 'lain', 'latin', 'lation', 'elation', 'delation', 'dealation', 'dealbation'] 
['m', 'am', 'cam', 'camp', 'campo', 'campho', 'camphor', 'camphory', 'camphoryl', 'camphoroyl'] 
['n', 'an', 'lan', 'lain', 'latin', 'lation', 'elation', 'delation', 'dealation', 'dealbation'] 
['o', 'lo', 'loy', 'logy', 'ology', 'oology', 'noology', 'nosology', 'nostology', 'gnostology'] 
['p', 'pi', 'pig', 'prig', 'sprig', 'spring', 'springy', 'springly', 'sparingly', 'sparringly'] 
['q'] 
['r', 'ra', 'rah', 'rach', 'brach', 'branch', 'branchi', 'branchia', 'branchiae', 'branchiate', 'abranchiate'] 
['s', 'si', 'sig', 'spig', 'sprig', 'spring', 'springy', 'springly', 'sparingly', 'sparringly'] 
['t', 'ut', 'gut', 'gutt', 'gutte', 'guttle', 'guttule', 'guttulae', 'guttulate', 'eguttulate'] 
['u', 'ut', 'gut', 'gutt', 'gutte', 'guttle', 'guttule', 'guttulae', 'guttulate', 'eguttulate'] 
['v', 'vu', 'vum', 'ovum'] 
['w', 'ow', 'low', 'alow', 'allow', 'hallow', 'shallow', 'shallowy', 'shallowly'] 
['x', 'ox', 'cox', 'coxa', 'coxal', 'coaxal', 'coaxial', 'conaxial'] 
['y', 'ly', 'loy', 'logy', 'ology', 'oology', 'noology', 'nosology', 'nostology', 'gnostology'] 
['z', 'za', 'zar', 'izar', 'izard', 'izzard', 'gizzard'] 

Edit: Dato il grado in cui i rami si fondono verso la fine, ho pensato che sarebbe interessante tracciare un grafico per dimostrare questo:

Un'interessante estensione di questa sfida: è probabile che ci siano diverse parole finali di equilibrio per alcune lettere.Quale serie di catene riduce al minimo il numero di nodi finali (ad esempio, unisce la maggior parte delle lettere)?