Palabras encadenadas

Seguramente todos conocéis este juego. El otro día pensé cuál sería la cadena más larga de palabras encadenadas posible. En este post voy a intentar encontrarla.

Existen muchas variantes de este juego, así que mejor definimos un conjunto cerrado de reglas antes de empezar:

  1. El primer jugador dice una palabra cualquiera.
  2. Los siguientes jugadores deben decir una palabra que empiece por la última sílaba de la palabra anterior, ignorando los acentos.
  3. No se puede repetir una misma palabra 2 veces.
  4. Sólo son válidas palabras que figuren en la 23ª edición del diccionario de la RAE. Aunque figuren en el diccionario, nombres propios, siglas y monosílabos tampoco son válidos.
  5. Al encadenar las palabras, se ignoran sus acentos.

Datos

En primer lugar, necesitamos obtener todas las palabras del diccionario de la lengua española. Aunque la RAE no proporciona un listado completo de palabras, Giusseppe Domínguez nos lo facilita.

Tras esto, necesitamos la descomposición silábica de todas las palabras del diccionario. Puede parecer trivial, pero es una tarea bastante compleja, ya que hay un gran número de reglas y excepciones. Por suerte, la librería Pyphen hace ese trabajo decentemente por nosotros.

Finalmente, tenemos una lista de 86993 palabras válidas separadas por sílabas.

Palabras por número de sílabas en español

Secuencia más larga

Para calcular la mayor secuencia posible, construimos un grafo dirigido cuyos nodos son las palabras en cuestión, y las aristas comunican dos palabras que puedan ser encadenadas.

Ejemplo de grafo de palabras encadenadas

De esta manera, el problema se reduce a encontrar el camino dirigido más largo de este grafo. A diferencia del camino más corto, encontrar el camino más largo en un grafo es un problema NP-completo. Con un grafo de 86993 nodos y 43053416 aristas, tardaríamos 1.82 × 101012 años en encontrar la solución perfecta a este problema, así que debemos probar soluciones aproximadas.

Camino aleatorio

Escogiendo caminos de forma aleatoria, el camino más largo obtenido es de tan sólo 92 palabras:

sopa -> pantalla -> llaneza -> […] -> ramuja -> jagüel -> güeldrés

Esto se debe a que es fácil llegar a un sumidero, es decir, una palabra a la que es posible llegar, pero no es posible salir de ella, como es el caso de güeldrés.

Otras aproximaciones

Existen otras formas de resolver este problema, como:

¿Se te ocurren más formas de resolver este problema? ¿Cuál es la cadena más larga que has sido capaz de encontrar? Si lo deseas, puedes dejar un comentario con tus resultados.

Comentarios

Giusseppe Domínguez Reply
Me alegra saber en qué se está empleando el diccionario (listado de palabras del mismo) que tecleé hace tiempo. Como digo, está tecleado a mano, así que incluye un error que he estimado en torno al 1,5%. Estoy, durante estos días, realizando una corrección del mismo, así como una recopilación de las definiciones en texto plano de todas palabras del diccionario.

Si te interesa, no dudes en contactarme.
Un cordial saludo,
Giusseppe Domínguez
Juan C. Roldán Reply

En respuesta a Giusseppe Domínguez:

Muchas gracias Giusseppe. En una investigación que iniciamos hace poco, necesitábamos un corpus de este tipo que tuviera la mayor cantidad posible de palabras, y decidimos usar un repositorio de subtítulos de 234,000 series y películas para extraerlas: http://opus.nlpl.eu/download.php?f=OpenSubtitles/v2018/xml/es.zip

Pero sin duda una corrección con las definiciones nos será útil si me la puedes facilitar :) espero tu respuesta
Giusseppe Domínguez Reply
En cuanto termine de analizar las (aprox) 1000 palabras que no se han encontrado en la RAE vía web (con un programa que automáticamente las consulta, hecho en Bash/Linux, que si quieres también te puedo proporcionar), será un placer ponerlas a disposición pública.

Deja un comentario

Recibir un mail

🍪 ¿Cookies?

Esta web usa cookies para identificar qué contenido es interesante y escribir más contenido similar. Puedes obtener más información aquí.