Suma sucesiva de char para obtener la palabra más larga en el diccionario

Question

Dado un diccionario de palabras y un carácter inicial. encuentre la palabra más larga posible en el diccionario agregando sucesivamente un carácter a la palabra. En cualquier caso, la palabra debe ser válida en el diccionario.

por ejemplo: a -> a -> cat -> compra -> tabla ....

Answer 1

El método de fuerza bruta sería tratar de añadir cartas a cada índice disponibles usando una búsqueda en profundidad.

Por lo tanto, comenzando con 'a', hay dos lugares donde puede agregar una nueva letra. Delante o detrás de la 'a', representada por puntos debajo.

.a.

Si se agrega una 't', en la actualidad hay tres posiciones.

.a.t.

Usted puede tratar de añadir los 26 cartas a cada posición disponible. El diccionario en este caso puede ser una tabla hash simple. Si agrega una 'z' en el medio, obtendrá 'azt', que no estaría en la tabla hash, por lo que no continuará por esa ruta en la búsqueda.

Editar: el gráfico de Nick Johnson me hizo tener curiosidad sobre cómo sería un gráfico de todos los caminos máximos. Es una imagen de gran tamaño (1,6 MB) aquí:

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

Editar: He aquí una implementación de Python. El enfoque de la fuerza bruta en realidad se ejecuta en un tiempo razonable (unos segundos, dependiendo de la letra de inicio).

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 

Por supuesto, habrá muchos vínculos en la respuesta. Esto imprimirá los primeros N resultados, medidos por la longitud de la palabra final.

Salida para la letra de inicio 'a', utilizando el diccionario 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')) 

Y aquí están los resultados para cada letra inicial. Por supuesto, se hace una excepción que la letra de inicio simple no tiene que estar en el diccionario. Solo una palabra de 2 letras que se puede formar con ella.

(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

Si desea hacer esto una vez, lo haría el siguiente (generalizada al problema de comenzar con una palabra completa):

Tome su diccionario entero y tirar todo lo que no tiene un superconjunto de los caracteres en su palabra objetivo (digamos que tiene longitud m). Luego coloca las palabras restantes por longitud. Para cada palabra de longitud m+1, intente soltar cada letra y vea si eso produce su palabra deseada. Si no, tirarlo. Luego, compruebe cada palabra de longitud m+2 con el conjunto válido de longitud m+1, dejando caer las que no se puedan reducir. Continúa hasta que encuentres un conjunto vacío; la (s) última (s) cosa (s) que encontró serán las más largas.

Si desea hacer esto rápido para buscar, construiría un sufijo-tree- como estructura de datos.

Agrupe todas las palabras por longitud. Para cada palabra de longitud 2, coloque cada uno de sus dos caracteres en un conjunto de "subpalabras" y agregue esa palabra a cada uno de los conjuntos de "superpalabras" de los caracteres. Ahora tiene un enlace entre todas las palabras válidas de longitud 2 y todos los caracteres. Haga lo mismo con las palabras de longitud 3 y las palabras válidas de longitud 2. Ahora puede comenzar en cualquier lugar de esta jerarquía y hacer una búsqueda de amplitud para encontrar la rama más profunda.

---

Editar: la velocidad de esta solución va a depender en gran medida de la estructura de la lengua, pero si decidimos construir todo utilizando conjuntos con log(n) rendimiento para todas las operaciones (es decir, utilizamos árboles rojo-negro o similares), y tenemos N(m) palabras de longitud m, luego para formar el enlace entre las palabras de longitud m+1 y m tendrá aproximadamente (m+1)*m*N(m+1)*log(N(m)) tiempo (teniendo en cuenta que la cadena se compara toma tiempo lineal en la longitud de la cadena). Ya que tenemos que hacer esto para todas las longitudes de palabra, el tiempo de ejecución para la construcción de la estructura de datos completa será algo del orden de

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

(El binning inicial en palabras de una determinada longitud tomará tiempo lineal por lo que puede ser descuidado, la fórmula real para el tiempo de ejecución es complicada porque depende de la distribución de las longitudes de las palabras, para el caso en que lo hagas de una sola palabra es aún más complicado porque depende del número esperado de palabras más largas que tienen subwords cortas .)

Answer 3

Suponiendo que necesita hacer esto repetidamente (o quiere la respuesta para cada una de las 26 letras), hágalo al revés:

1. carga un diccionario, y ordenarla por la longitud, descendiendo
2. Establecer un mapeo, inicialmente vacío, entre las palabras y (extensión), max_len tuplas.
3. Para cada palabra en la lista ordenada:
   1. Si ya está en el mapeo, recuperar el máximo len.
   2. Si no es así, establezca la longitud máxima a la longitud de la palabra.
   3. Examine cada palabra producida al eliminar un carácter. Si esa palabra no está en la cartografía, o nuestra max_len excede el max_len de la palabra ya en el mapeo, actualizar el mapeo con la palabra actual y max_len

Entonces, para obtener la cadena para un determinado prefijo, simplemente comience con ese prefijo y búsquelo repetidamente y sus extensiones en el diccionario.

Aquí está el código de ejemplo de 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 

y su salida para cada letra del 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'] 

Editar: Teniendo en cuenta el grado en que las ramas se unen hacia el final, pensé que sería interesante para dibujar un gráfico para demostrar esto:

Una extensión interesante de este desafío: es probable que haya varias palabras finales equivalentes para algunas letras.¿Qué conjunto de cadenas minimiza el número de nodos finales (por ejemplo, combina la mayoría de las letras)?