Todos los * pangramas perfectos del inglés

Una El pangrama inglés es una oración que contiene las 26 letras del alfabeto inglés. El pangram inglés más conocido es probablemente «El rápido zorro marrón salta sobre el perro perezoso». Mi pangram favorito es «Sorprendentemente, pocas discotecas ofrecen máquinas de discos».

Un pangram perfecto es un pangram donde cada una de las letras aparece solo una vez. He encontrado algunas fuentes en línea que enumeran los pangramas perfectos conocidos. Nadie parece haberse esforzado con éxito en producirlos todos de forma exhaustiva, así que lo asumí como un desafío divertido. Así es como encontré todos * los pangramas perfectos del inglés. Explicaré el asterisco más adelante.

• Crwth vox zaps qi gym fjeld bunk. (El sonido de un violín celta golpea un centro de fitness orientado a las fuerzas espirituales situado en una meseta árida de Escandinavia.) ¡Estas son todas palabras legales de Scrabble!
• Squdgy kilp job zarf nth cwm vex. (Las algas mal formadas compran un calentador de tazas ornamental que uno de los muchos huecos empinados a medio abrir en la cabeza de un valle o ladera de una montaña ha irritado).
• Las ninfas jock waqf drug vex blitz. (La donación caritativa intoxicaba a los espíritus del bosque, que frustraban al atleta, que se involucraba en un ataque.)
• Hm, fjord waltz, cinq busk, pyx veg. (Veamos, una ensenada larga, estrecha y profunda baila, el cinco en los dados hace música en la calle, y el pequeño recipiente redondo para los enfermos e incapaces descansa). También es legal el Scrabble, pero tiene una interjección (Hm).

Desafortunadamente, estas son algunas de las oraciones más legibles que pude encontrar *. Todos los pangramas perfectos generados a partir de la Lista oficial de palabras de torneos y clubes 3 (OWL3) para Scrabble sin interjecciones incluyen la palabra cwm o crwth. Waqf es legal en torneos de Scrabble fuera de Norteamérica.

Cómo encontrar todos los pangrams perfectos

El método para encontrar pangrams perfectos viene en dos pasos. La primera es encontrar todos los conjuntos de palabras que contienen cada letra del alfabeto inglés una vez. El segundo paso es ver cuál de esos conjuntos se puede reorganizar en oraciones válidas en inglés.

Paso 1: Encontrar conjuntos de palabras para el pangrama perfecto

Para comenzar a encontrar conjuntos de palabras que abarcar el alfabeto inglés requiere una lista de palabras en inglés. Encontrar y mantener una lista de palabras de alta calidad fue mucho más difícil de lo que esperaba. Originalmente, pensé que este proyecto tomaría dos días, pero terminó tomando dos semanas como resultado de este problema de calidad de los datos.

Comencé con el diccionario Unix, que es una lista de palabras en inglés disponible gratuitamente que viene con casi todos los sistemas operativos basados en Unix. Noté de inmediato que la lista tenía problemas de calidad. Primero, cada letra del alfabeto se consideraba una palabra en el diccionario de Unix, e incluía muchas palabras que no eran palabras, como «vejoz». Esto demostró la necesidad de una lista negra para administrar las listas de palabras encontradas en línea. En segundo lugar, la El diccionario Unix carecía de plurales para las palabras, por lo que el diccionario incluiría la palabra «naranja» pero no «naranjas». La lista de palabras es tan restrictiva, de hecho, que ningún pangrama perfecto conocido anteriormente incluye solo palabras del diccionario Unix. Todavía encontré algunos, como «squdgy kilp job zarf nth cwm vex».

Luego busqué en Internet conjuntos de palabras más grandes. Encontré conjuntos de palabras muy grandes que eran enormes, pero cuando comencé a buscar pangramas perfectos de esas listas, descubrí que estaban demasiado contaminados con palabras de baja calidad que no son palabras válidas en inglés. Incluso después de muchas rondas de iteración, todavía no pude reducir la lista para encontrar pangramas razonables o manejables. Intenté limpiarlo creando una lista blanca de palabras de cierta longitud, pero la lista seguía siendo de muy baja calidad.

Finalmente, después de muchas iteraciones, pagué $ 15 para comprar una membresía de prueba de North American Scrabble® Players Association, que me dio acceso al OWL3 patentado y con derechos de autor, que es fuente de cierta controversia. Incluso entonces, tuve que agregar algunas palabras conocidas en inglés, como las palabras de una sola letra «a» e «I».

Armado con una lista adecuada de palabras, implementé un algoritmo para producir todos los conjuntos de palabras de esa lista que cada uno contiene una de cada letra del alfabeto inglés. Describiré el algoritmo en profundidad en la sección «El algoritmo» a continuación.

Paso 2: Formar oraciones en inglés a partir de una bolsa de palabras

Dado un conjunto de palabras, averiguar si un Una frase válida en inglés es posible con todas las palabras proporcionadas, es un problema no trivial, pero es más fácil que la mayoría de los otros problemas de procesamiento del lenguaje natural (PNL).

Hay heurísticas útiles para eliminar oraciones no elegibles; Pude formar oraciones válidas en inglés a partir de las palabras restantes después de seguir esas heurísticas. Las oraciones a menudo eran absurdas, pero seguían siendo válidas. Aquí están las heurísticas que utilicé:

1. Debe haber al menos un verbo.
2. Solo puede haber un sustantivo más que verbos a menos que haya una conjunción o una preposición, los cuales son muy raros.
3. Si hay adjetivos, también debe haber sustantivos.

La heurística funciona en parte debido a la posibilidad de sujetos (ni perfectos ni un pangrama, pero «muévete tranquilamente y habla suavemente» es una oración con dos verbos y sin sustantivos, con el sujeto implícito de «tú»).

Dado que el espacio de palabras que puede posiblemente participar en pangrams perfectos es pequeño, es bastante fácil etiquetar manualmente cada palabra individual con sus partes elegibles del discurso y ver si el conjunto de palabras obedece a esas tres heurísticas simples. Si te gusta o no la calidad de las oraciones producidas es cuestión de gustos.

El algoritmo

Esta sección es un poco técnica, pero es de esperar que sea fácil de seguir. No dude en pasar a la sección «Resultados & Aprendizajes”.

Estrategia de alto nivel

El objetivo es producir todos los conjuntos posibles de palabras de la lista dada de palabras que abarcan el alfabeto inglés «perfectamente».

1. Limpiar la lista de palabras para reducir drásticamente el espacio de búsqueda, por ejemplo elimine las palabras que tienen letras repetidas, como «letras».
2. Use máscaras de bits para representar palabras de manera eficiente y mapeelas de nuevo a los conjuntos de palabras originales.
3. Busque en todos los estados posibles, cada una representa una posible combinación de letras, iterando repetidamente a través de la lista de máscaras de bits. El rendimiento se mejora drásticamente con la programación dinámica.
4. Dibuja flechas (bordes dirigidos) desde el estado de pangram perfecto, el estado final que tiene todos las letras en inglés, a los estados intermediarios que lo compusieron. Vuelva a hacerlo con los estados intermedios para crear una estructura de datos que pueda reconstruir los conjuntos de palabras que son posibles pangramas perfectos. Esto se llama retroceso.
5. Salida los conjuntos de palabras descubiertos que posiblemente sean pangramas perfectos como árboles.

Limpiar la lista, también conocida como Canonicalización

El primer paso es limpiar la lista original de palabras para reducir el espacio de búsqueda y aumentar la calidad de salida.

1. Elimine todos los espacios en blanco alrededor de la palabra y conviértalo solo a minúsculas
2. Asegúrese de que las palabras solo contengan letras del alfabeto inglés; Utilicé un filtro de expresión regular simple: /^+$/
3. Filtre contra cualquier otra lista, p. Ej. listas negras; si una palabra está en la lista negra, omita esa palabra
4. Elimine todas las palabras con letras repetidas

Esto acortó significativamente el espacio de búsqueda, de listas de 200,000 ~ 370,000 palabras a 35.000 ~ 65.000 palabras mucho más pequeñas.

Uso de máscaras de bits

Las máscaras de bits son representaciones enteras de estados. Hay varias ventajas de las máscaras de bits:

• Las máscaras de bits representan bien este problema. El orden de las letras no importa, por lo que todas las combinaciones de palabras se pueden representar como una serie de 26 dígitos de ceros y unos, y cada dígito representa si existe o no una letra en la combinación. Por ejemplo. si el conjunto de palabras contiene la letra «e», el quinto dígito será un 1, de lo contrario un 0.
• Las máscaras de bits son eficientes: dado que el espacio de búsqueda es constante, las máscaras de bits ofrecen un almacenamiento eficiente y representación de todas las combinaciones posibles de letras. Además, las operaciones bit a bit son rápidas; para probar si se pueden combinar dos máscaras de bits para producir una máscara de bits más grande, verifique si el AND bit a bit de las dos máscaras es igual a 0, los cuales son extremadamente operaciones rápidas.

Por lo tanto, convierta cada palabra en una máscara de bits, que se puede representar como un número entero. Por ejemplo, la palabra «cab» se asigna a la máscara de bits de 111, que es el número decimal 7. La palabra «be» se asigna a 10010, que es el número decimal 18, y así sucesivamente. La máscara de bits más grande posible es una con todas las letras del alfabeto, el estado de pangrama perfecto posible, 11111111111111111111111111, que es el número decimal 67,108,863, o 2²⁶ -1. Esto encaja bien dentro de un entero estándar de 32 bits con signo, que puede representar hasta a 2³¹-1.

El uso de máscaras de bits comprime aún más el espacio, ya que los anagramas de una sola palabra se asignan a la misma máscara de bits. Tanto el «horno» como el «enlace» se asignan a la máscara 10110100000000, que es el número decimal 11520. Esto reduce aún más el espacio de búsqueda de 35.000 ~ 65.000 palabras a máscaras de 25.000 ~ 45.000 bits.

Conserva una asignación de la máscara de bits al conjunto de palabras de las que se derivan. Esto será útil al generar los conjuntos de palabras.

Búsqueda del pangrama perfecto con programación dinámica

El núcleo del algoritmo es bastante simple:

Dado un estado posible (que se compone de combinaciones válidas de palabras existentes), pruebe todas las máscaras de la lista de palabras inicial para ver si es posible crear un nuevo estado válido (comprobando si el bit a bit AND de el estado y la máscara es igual a 0, lo que significa que no hay letras superpuestas). Cree el nuevo estado utilizando la operación OR bit a bit que fusiona todos los unos. Para cada nuevo estado descubierto, siga repitiendo hasta que no haya más estados inexplorados. Si esto llega al final, significa que el algoritmo ha encontrado al menos un posible conjunto de palabras de pangrama perfecto. El primer estado posible que puede enumerar todos los estados posibles es el estado vacío o 0, donde no se incluyen letras del alfabeto. Así que comience allí y luego descubra de forma recursiva qué estados son posibles.

Una gran ganancia de eficiencia es notar que hay muchas formas de alcanzar un estado intermitente y que el trabajo en el estado no cambia en función de cómo fue alcanzado. Entonces, en lugar de repetir el trabajo cuando se revisa un estado, almacene el resultado de cada estado. Esta técnica se llama programación dinámica y convierte un problema combinatorio complejo en un programa lineal. El proceso de almacenar el estado intermitente se llama memorización.

Así que cree una matriz de tamaño 2²⁶, entre 0 y 67,108,863, inclusive. Cada índice representa un estado de máscara de bits como se explicó anteriormente. El valor de cada índice de la matriz representa lo que se conoce sobre el estado. 0 significa que el estado está intacto o inalcanzable. 1 significa que el estado ha encontrado una manera de alcanzar el posible estado de pangrama perfecto. -1 significa que el estado no ha podido encontrar una manera de llegar al final.

Pseudocódigo a continuación:

Interludio: Complejidad y análisis práctico en tiempo de ejecución

Hay 2²⁶ máscaras de bits posibles para una serie de 26 bits. Dado que cada estado se procesa solo una vez debido a la memorización, el tiempo de ejecución de este algoritmo es O (n 2 ^ d), donde d es el tamaño del alfabeto, 26. La variable n no representa el número de palabras, sino el número de máscaras de bits. Con 67,108,863 y máscaras de aproximadamente 45,000 bits, esto es del orden de 3 billones, que mi MacBook Pro podría manejar en aproximadamente 45 minutos; manejable para cualquier computadora moderna. También vale la pena señalar que la pila de llamadas recursivas nunca será más profunda que 26 (probablemente nunca más profunda que 15), por lo que también es muy manejable desde esa dimensión.

Una ventaja del enfoque de máscara de bits con sólo 2²⁶ estados es que todos los estados se pueden almacenar en la memoria. Dado que solo hay 3 valores por estado (-1, 0, 1), esto se puede almacenar en un solo byte. Con un solo byte por estado, 2²⁶ estados resultan en alrededor de 67 megabytes, lo que nuevamente es muy manejable.

Sin embargo, a medida que aumenta el alfabeto, el espacio de búsqueda aumenta exponencialmente y también el tiempo de ejecución, lo que hace que problema para volverse intratable muy rápidamente. En la sección «Idioma con alfabetos más grandes» a continuación, encontrará una breve discusión sobre cómo abordar el pangrama perfecto para alfabetos más grandes.

Creación dinámica de un gráfico acíclico dirigido (DAG)

Ahora que Hemos completado los estados de la máscara de bits, ¡es hora de recuperar la solución!

Para encontrar los conjuntos de palabras que crearon el conjunto de posibles pangramas perfectos, necesitamos derivar qué estados intermedios fueron esenciales para componer los estados finales . Luego, la pregunta de seguimiento es qué otros estados intermediarios componían esos estados intermedios, y así sucesivamente hasta que lo único que queda son los estados que se asignan directamente a las palabras. Este proceso se llama retroceso.

Mantener seguimiento de las relaciones entre estados, el objetivo es crear un Di rected Acyclical Graph (DAG), que mantiene qué estados intermedios componen cualquier estado dado. Los DAG son fáciles de recorrer para recuperar salidas, especialmente debido a su naturaleza no cíclica. Para construir, comience desde el posible estado perfecto del pangrama y cree un borde dirigido (flecha) que apunte a los estados intermedios que lo componen. Repita el proceso con los estados intermedios y producirá un DAG. Nunca habrá ciclos porque las flechas siempre apuntan a un estado con un valor menor.

En lugar de reconstruir las relaciones que se descubrieron en el paso de búsqueda, que implica atravesar nuevamente trillones de posibles combinaciones de estados, es más eficiente construir el DAG durante la fase de programación dinámica. Dentro del método de resolución, si un estado recién construido puede alcanzar el posible estado de pangrama perfecto, almacene un borde dirigido desde el estado recién construido al estado original solo si el estado original es más pequeño que su complemento (para reducir la duplicación del borde).

¡Imprima los frutos de su trabajo en forma de árbol!

Probablemente, el formato más fácil para ver los conjuntos de palabras resultantes es enumerarlos como árboles con el nodo raíz como el estado perfecto del pangrama. Dado el DAG construido desde arriba, la mejor manera de descomprimirlo es hacerlo de forma recursiva, escribiendo cada estado en el disco en cada paso en lugar de en la memoria, ya que el árbol es un orden de magnitud mayor que el DAG.

Una mejora de esta forma de expansión es resumir estados que tienen solo una única combinación posible de palabras. Un estado que es una máscara para las palabras y no hay subestados que lo compongan puede resumirse trivialmente. Un estado se puede resumir si sus subestados y sus compuestos se pueden resumir, y todas las máscaras derivadas de sí mismo y sus hijos no tienen bits / caracteres superpuestos. La impresión del DAG resumido mejora la legibilidad del árbol de salida resultante acortándolo y simplificándolo.

Dado que el resumen depende solo del menor de los dos estados, iterar a través de la matriz desde el estado inicial de 0 hacia arriba y El uso de las reglas anteriores para administrar la regla de resumen permite que esto se complete en tiempo lineal.

¡Árboles Pangram producidos!

Siéntase libre de recorrer los árboles pangram perfectos para ver si ¡Puede encontrar oraciones interesantes!

Hay muchos posibles pangramas perfectos

Me sorprendió la cantidad de pangramas perfectos posibles. ¡Hay muchos! La mejor estrategia para unirlos no requiere un procesador de lenguaje natural complejo. Una vez que las palabras candidatas se han etiquetado como sustantivo o verbo elegible, la bolsa de palabras debe contener al menos un sustantivo, un verbo y la proporción correcta de sustantivos y verbos.

La calidad de los datos es un problema difícil

La sección del algoritmo tomó dos días, pero el problema de calidad de los datos tomó dos semanas. Cuando le mencioné este hallazgo a mi amigo, que es un ingeniero senior de Google, no se sorprendió y comentó que los problemas de calidad de los datos son algunos de los problemas más difíciles en ingeniería. Lección aprendida.

Las reglas de los Pangrams perfectos

¡Hay muchos matices en lo que se considera un pangram perfecto! Quería buscar en pangramas sin interjecciones (por ejemplo, hm, pht), pero también existen otras restricciones populares como abreviaturas, acrónimos, contracciones, iniciales, letras aisladas, nombres propios y números romanos. También hay palabras que son nombres de letras, como Qoph, que sentí que estaba haciendo trampa.

Con algunas de esas restricciones relajadas, hay muchos pangramas «perfectos». En el orden de billones, probablemente . Hay muchos acrónimos e iniciales.

El asterisco

El asterisco está en su lugar porque la definición de todos los pangramas perfectos del inglés no está bien definida. Hay matices relacionado con lo que debería permitirse en los pangramas perfectos de inglés. También hay muchas disputas sobre si algunas palabras son o no palabras en inglés. Dados estos matices, es realmente difícil decir que he encontrado todos los pangrams perfectos. Puedo hacer dos afirmaciones con bastante seguridad:

1. He encontrado una metodología para producir todos los pangramas perfectos de inglés y otros idiomas con conjuntos de caracteres similares o más pequeños.
2. I han enumerado todos los conjuntos de palabras que posiblemente pueden formar pangramas perfectos utilizando el diccionario oficial del torneo de Scrabble y, OWL3.

¡Siéntase libre de producir sus propios pangrams perfectos con las técnicas descritas en esta publicación!

La dependencia de Perfect Pangrams de palabras de raíces galesas y árabes

Las palabras derivadas del galés y el árabe eran realmente importantes para la existencia de pangramas perfectos en inglés (a menos que se relajen las limitaciones del pangrama perfecto). Usando la lista de palabras OWL3 con reglas estrictas con respecto a los pangramas perfectos, no hay pangramas perfectos que no incluyan las palabras «cwm (s)» o «crwth (s)», ambas palabras en galés. En el Scrabble internacional, la palabra derivada del árabe «waqf (s)» es una palabra válida que puede producir pangramas perfectos sin recurrir a «cwm (s)» o «crwth (s)».

Eficiencias del flujo de trabajo

Era importante ser más eficiente en la paralelización de tareas durante este proyecto. Una ejecución completa toma 25 minutos para el diccionario Unix y cerca de una hora para los diccionarios realmente grandes. Tuve algunos problemas iniciales al cambiar de contexto durante una ventana de 30 minutos, pero mejoré a medida que avanzaba para mejorar mi productividad.

Extensión / Generalización – Buscador de anagramas

El pangrama perfecto La búsqueda también es equivalente a un buscador de anagramas para la cadena «abcdefghijklmnopqrstuvwxyz». ¿Qué pasa si quisieras construir un buscador de anagramas genérico?

La misma técnica se puede usar siempre que las reglas de representación y administración del estado para verificar La validez de la combinación de palabras se actualiza. En lugar de que los estados se administren como un número entero, sería más fácil rastrear el estado como un mapa de los caracteres relevantes. Ver si las combinaciones son válidas es decir que la combinación de dos mapas no excede el el recuento de caracteres deseado del anagrama para cada letra. Solo asegúrate de que el espacio de estado sea manejable; con demasiadas letras, el espacio de búsqueda puede ser realmente grande en un santiamén. Además, ¿puedes repetir palabras? Asegúrate de definir esas reglas dentro tu programación dinámica solución.

Idiomas con alfabetos más grandes

Este enfoque y solución son lineales en el tamaño del conjunto de palabras, pero exponenciales en el tamaño del alfabeto. Es posible que este enfoque no funcione con un conjunto de caracteres más grande, digamos el japonés moderno que tiene 46 silabarios. 2⁴⁶ es 70.368.744.177.664; más de un millón de veces más grande que el espacio de búsqueda en inglés de 2²⁶ = 67,108,864.

No está del todo claro si este enfoque funcionaría o no para el japonés. Si el idioma japonés tiene una entropía suficientemente baja, lo cual es posible, este enfoque sería viable. En lugar de inicializar una matriz de tamaño 2⁴⁶, los estados se mantendrán rastreados en un mapa. Además, se puede aprovechar la estructura del japonés; por ejemplo, el kana を (wo) se utiliza casi exclusivamente como participio posposicional y se puede excluir de la búsqueda, reduciendo el espacio de búsqueda.

El idioma camboyano de Khmer tiene el alfabeto más grande con 74. Otro posible próximo paso es explorar soluciones que sean sub-exponenciales en tamaño alfabético.

Inspiración

Me inspiré en el avance de Aubrey De Grey en encontrar el número cromático del plano al menos 5. Este es un avance significativo que se logró a través de métodos computacionales básicos.

No hace falta decir que encontrar pangramas perfectos no es suficiente para mejorar el límite inferior del número cromático de un plano.

Esto me hace creer que hay muchos problemas de fruta madura que tienen métodos computacionales simples para resolver un problema que es intratable manualmente. Te desafío a encontrar y resolver algunos de estos problemas. ¡Por favor, avíseme si encuentra algo!

Gracias

Estoy muy agradecido por mis excelentes amigos que me ayudaron revisando e improvisando esto conmigo, especialmente Anna Zeng, Catherine ¡Gao, Danny Wasserman, George Washington y Nick Wu!