Todos * pangrams perfeitos de inglês

Um Pangram inglês é uma frase que contém todas as 26 letras do alfabeto inglês. O pangrama inglês mais conhecido é provavelmente “A rápida raposa marrom salta sobre o cachorro preguiçoso”. Meu pangrama favorito é “Incrivelmente poucas discotecas oferecem jukeboxes.”

Um pangrama perfeito é um pangrama em que cada uma das letras aparece apenas uma vez. Eu encontrei algumas fontes online que listam os pangramas perfeitos conhecidos. Ninguém parece ter se esforçado com sucesso para produzir todos eles exaustivamente, então aceitei isso como um desafio divertido. Foi assim que encontrei todos os * pangramas perfeitos do inglês. Explicarei o asterisco mais tarde.

• Beliche de fjeld Crwth vox zaps qi gym. (O som de um violino celta atinge um centro de fitness voltado para as forças espirituais orientais situado em um planalto árido da Escandinávia.) Este aqui são palavras jurídicas do Scrabble!
• Squdgy kilp job zarf enésimo cwm vex. (A alga malformada compra um aquecedor de copo ornamental que irritou uma das muitas cavidades semiabertas nas laterais de um vale ou montanha.)
• Ninfas de Jock waqf drug vex blitz. (A doação de caridade embriagou os espíritos da floresta, que frustraram o atleta, que se envolveu em um ataque.)
• Hm, valsa do fiorde, cinq busk, pyx veg. (Vejamos, uma longa e estreita enseada profunda dança, os cinco nos dados fazem música na rua e o pequeno recipiente redondo para os enfermos e incapazes repousa.) Também Scrabble legal, mas tem uma interjeição (Hm).

Infelizmente, essas são algumas das frases mais legíveis que consegui encontrar *. Todos os pangramas perfeitos gerados a partir da Lista oficial de palavras do torneio e clube 3 (OWL3) para Scrabble sem interjeições incluem a palavra cwm ou crwth. Waqf é um torneio de Scrabble legal fora da América do Norte.

Como encontrar todos os pangramas perfeitos

O método para encontrar os pangramas perfeitos vem em duas etapas. A primeira é encontrar todos os conjuntos de palavras que contenham cada letra do alfabeto inglês uma vez. A segunda etapa é ver quais desses conjuntos podem ser reorganizados em frases válidas em inglês.

Etapa 1: Encontrar conjuntos de palavras para o pangrama perfeito

Para começar a encontrar conjuntos de palavras que estender o alfabeto inglês requer uma lista de palavras em inglês. Encontrar e manter uma lista de palavras de alta qualidade foi muito mais difícil do que eu esperava. Originalmente, pensei que este projeto levaria dois dias, mas acabou demorando duas semanas como resultado desse problema de qualidade de dados.

Comecei com o dicionário Unix, que é uma lista de palavras em inglês disponível gratuitamente que vem com quase todos os sistemas operacionais baseados em Unix. Percebi imediatamente que a lista tinha problemas de qualidade. Primeiro, cada letra do alfabeto era considerada uma palavra no dicionário Unix e incluía muitas não palavras, como “vejoz”. Isso demonstrou a necessidade de uma lista negra para gerenciar as listas de palavras encontradas online. Em segundo lugar, o O dicionário Unix não tinha plurais para as palavras, então o dicionário incluiria a palavra “laranja”, mas não “laranjas”. A lista de palavras é tão restritiva, na verdade, que nenhum pangrama perfeito conhecido anteriormente inclui apenas palavras do dicionário Unix. Ainda encontrei alguns, como “squdgy kilp job zarf nth cwm vex”.

Eu então me virei para a internet para encontrar conjuntos maiores de palavras. Encontrei conjuntos de palavras muito grandes que eram enormes, mas quando comecei a cavar por pangramas perfeitos dessas listas, descobri que eles estavam muito poluídos com palavras de baixa qualidade que não são palavras válidas em inglês. Mesmo depois de muitas rodadas de iteração, ainda não consegui reduzir a lista para encontrar qualquer pangrama razoável ou gerenciável. Tentei limpar isso criando uma lista de permissões de palavras de determinados comprimentos, mas a lista ainda era de qualidade extremamente baixa.

Finalmente, depois de muitas iterações, paguei $ 15 para comprar uma associação experimental do North American Scrabble® Players Association, que me deu acesso ao OWL3 proprietário e protegido por direitos autorais, que é fonte de alguma controvérsia. Mesmo assim, tive que adicionar algumas palavras conhecidas em inglês, como as palavras de uma só letra “a” e “I”.

Munido de uma lista adequada de palavras, implementei um algoritmo para produzir todos os conjuntos de palavras dessa lista em que cada um contém uma de cada letra do alfabeto inglês. Descreverei o algoritmo em detalhes na seção “O algoritmo” abaixo.

Etapa 2: Formando frases em inglês a partir de um pacote de palavras

Dado um conjunto de palavras, descobrir se um Uma frase em inglês válida é possível com todas as palavras fornecidas é um problema não trivial, mas é mais fácil do que a maioria dos outros problemas de processamento de linguagem natural (PNL).

Existem heurísticas úteis para eliminar sentenças inelegíveis; Consegui formar frases em inglês válidas com as palavras restantes após seguir essas heurísticas. As frases costumavam ser sem sentido, mas ainda assim válidas. Aqui estão as heurísticas que usei:

1. Deve haver pelo menos um verbo.
2. Só pode haver mais um substantivo do que verbos, a menos que haja uma conjunção ou uma preposição, ambas muito raras.
3. Se houver adjetivos, deve haver também substantivos.

A heurística funciona em parte devido à possibilidade de implícita sujeitos (nem perfeito nem um pangrama, mas “mova-se silenciosamente e fale suavemente” é uma frase com dois verbos e nenhum substantivo, com o sujeito implícito de “você”).

Já que o espaço de palavras que pode possivelmente participar de pangramas perfeitos é pequeno, é fácil marcar manualmente cada palavra individual com suas classes gramaticais elegíveis e ver se o conjunto de palavras obedece a essas três heurísticas simples. Gostar ou não da qualidade das frases produzidas é uma questão de gosto.

O Algoritmo

Esta seção é um pouco técnica, mas espero que seja fácil de seguir. Sinta-se à vontade para pular para a seção “Resultados & Aprendizagem”.

Estratégia de alto nível

O objetivo é produzir todos os conjuntos possíveis de palavras da lista de palavras fornecida que abrange o alfabeto inglês “perfeitamente”.

1. Limpe a lista de palavras para reduzir drasticamente o espaço de pesquisa, por exemplo, remova palavras com letras repetidas, como “letras”.
2. Use máscaras de bits para representar palavras de maneira eficiente e mapeie-as de volta aos conjuntos originais de palavras.
3. Pesquise em todos os estados possíveis, cada um representando uma possível combinação de letras, iterando repetidamente através da lista de máscaras de bits. O desempenho é dramaticamente melhorado com a programação dinâmica.
4. Desenhe setas (bordas direcionadas) a partir do estado do pangramma perfeito, o estado final que tem tudo as letras em inglês, para os estados intermediários que o compuseram. Faça isso novamente com os estados intermediários para criar uma estrutura de dados que possa reconstruir os conjuntos de palavras que são possíveis pangramas perfeitos. Isso é chamado de retrocesso.
5. Saída os conjuntos de palavras descobertos que são possivelmente pangramas perfeitos como árvores.

Limpeza da lista, também conhecida como canonização

A primeira etapa é limpar a lista original de palavras para reduzir o espaço de pesquisa e aumentar a qualidade de saída.

1. Retire todos os espaços em branco ao redor da palavra e converta para minúsculas apenas
2. Certifique-se de que as palavras contenham apenas letras do alfabeto inglês; Usei um filtro de expressão regular simples: /^+$/
3. Filtro contra qualquer outra lista, por exemplo, listas negras; se uma palavra estiver na lista negra, pule essa palavra
4. Remova todas as palavras com letras repetidas

Isso encurtou o espaço de pesquisa significativamente, de listas de 200.000 ~ 370.000 palavras para muito menor de 35.000 ~ 65.000 palavras.

Usando máscaras de bits

As máscaras de bits são representações inteiras de estados. Existem várias vantagens das máscaras de bits:

• As máscaras de bits representam bem esse problema. A ordem das letras não importa, então todas as combinações de palavras podem ser representadas como uma série longa de 26 dígitos de 0 e 1, com cada dígito representando se existe ou não uma letra na combinação. Por exemplo. se o conjunto de palavras contém a letra “e”, o 5º dígito será 1, caso contrário, um 0.
• As máscaras de bits são eficientes: como o espaço de busca é constante, as máscaras de bits oferecem um armazenamento eficiente e representação de todas as combinações possíveis de letras. Além disso, as operações bit a bit são rápidas; para testar se duas máscaras de bit podem ser combinadas para produzir uma máscara de bit maior, verifique se o AND bit a bit das duas máscaras é igual a 0, ambos extremamente operações rápidas.

Portanto, transforme cada palavra em uma máscara de bits, que pode ser representada como um número inteiro. Por exemplo, a palavra “cab” é mapeada para a máscara de bits de 111, que é o número decimal 7. A palavra “ser” é mapeada para 10010, que é o número decimal 18 e assim por diante. A maior máscara de bit possível é aquela com todas as letras do alfabeto, o estado de pangramma perfeito possível, 1111111111111111111111111111, que é o número decimal 67.108.863, ou 2²⁶ -1. Isso se encaixa bem em um número inteiro de 32 bits com sinal padrão, que pode representar até para 2³¹-1.

O uso de máscaras de bits comprime ainda mais o espaço, pois os anagramas de palavra única mapeiam para a mesma máscara de bits. Tanto “forno” quanto “link” são mapeados para a máscara 10110100000000, que é o número decimal 11520. Isso reduz ainda mais o espaço de pesquisa de 35.000 ~ 65.000 palavras para 25.000 ~ 45.000 máscaras de bits.

Retenha um mapeamento da máscara de bits de volta para o conjunto de palavras de onde são derivados. Isso será útil ao gerar os conjuntos de palavras.

Procurando o pangrama perfeito com programação dinâmica

O núcleo do algoritmo é bastante simples:

Dado um estado possível (que é composto de combinações válidas de palavras existentes), tente todas as máscaras da lista de palavras inicial para ver se é possível criar um novo estado válido (verificando se o AND bit a bit de o estado e a máscara são iguais a 0, o que significa que não há letras sobrepostas). Crie o novo estado usando a operação bit a bit OR que mescla todos os 1s. Para cada novo estado descoberto, continue repetindo até que não haja mais estados inexplorados. Se chegar ao fim, significa que o algoritmo encontrou pelo menos um conjunto de palavras de pangrama perfeito possível. O primeiro estado possível que pode enumerar todos os estados possíveis é o estado vazio ou 0, onde nenhuma letra do alfabeto é incluída. Então comece lá e então descubra recursivamente quais estados são possíveis.

Um grande ganho de eficiência é perceber que há muitas maneiras de atingir um estado intermitente e que o trabalho no estado não muda com base em como ele foi alcançado. Portanto, em vez de repetir o trabalho quando um estado é revisitado, armazene o resultado de cada estado. Essa técnica é chamada de programação dinâmica e transforma um problema combinatório complexo em um programa linear. O processo de armazenamento do estado intermitente é chamado de memoização.

Portanto, crie um array de tamanho 2²⁶, entre 0 e 67.108.863, inclusive. Cada índice representa um estado de máscara de bits, conforme explicado anteriormente. O valor em cada índice da matriz representa o que se sabe sobre o estado. 0 significa que o estado não foi alterado ou está inacessível. 1 significa que o estado encontrou uma maneira de alcançar o possível estado perfeito do pangrama. -1 significa que o estado falhou em encontrar uma maneira de chegar ao fim.

Pseudocódigo abaixo:

Interlúdio: Complexidade e Análise Prática de Tempo de Execução

Existem 2²⁶ máscaras de bits possíveis para uma série de 26 bits. Uma vez que cada estado é processado apenas uma vez por causa da memoização, o tempo de execução deste algoritmo é O (n 2 ^ d), onde d é o tamanho do alfabeto, 26. A variável n não representa o número de palavras, mas o número de máscaras de bits. Com 67.108.863 e cerca de 45.000 máscaras de bits, isso chega a cerca de 3 trilhões, o que meu MacBook Pro poderia controlar em aproximadamente 45 minutos; tratável para qualquer computador moderno. Também é importante notar que a pilha de chamadas recursivas nunca ficará maior que 26 (provavelmente nunca ficará maior que 15), portanto, também é muito gerenciável nessa dimensão.

Uma vantagem da abordagem de máscara de bits com apenas 2²⁶ estados é que todos os estados podem ser armazenados na memória. Como existem apenas 3 valores por estado (-1, 0, 1), isso pode ser armazenado em um único byte. Com um único byte por estado, 2²⁶ estados chegam a cerca de 67 megabytes, o que é novamente muito gerenciável.

À medida que o alfabeto aumenta, porém, o espaço de pesquisa aumenta exponencialmente e também o tempo de execução, causando o problema se tornar intratável muito rapidamente. Uma breve discussão sobre como se aproximar do pangrama perfeito para alfabetos maiores está na seção “Linguagem com alfabetos maiores” abaixo.

Construindo dinamicamente um gráfico acíclico direcionado (DAG)

Agora que nós preenchemos os estados da máscara de bits, é hora de recuperar a solução!

Para encontrar os conjuntos de palavras que criaram o conjunto de pangramas perfeitos possíveis, precisamos derivar quais estados intermediários foram essenciais para a composição dos estados finais . Então, a questão de acompanhamento é quais outros estados intermediários compuseram esses estados intermediários, e assim por diante, até que a única coisa restante sejam os estados que mapeiam diretamente para palavras. Esse processo é chamado de retrocesso.

Para manter acompanhamento das relações entre os estados, o objetivo é criar um Di Gráfico acíclico corrigido (DAG), que mantém quais estados intermediários compõem um determinado estado. Os DAGs são fáceis de atravessar para recuperar saídas, especialmente devido à sua natureza não cíclica. Para construir, comece a partir do possível estado do pangrama perfeito e crie uma aresta direcionada (seta) que aponta para os estados intermediários que o compõem. Repita o processo com os estados intermediários e produzirá um DAG. Nunca haverá ciclos porque as setas sempre apontam para um estado com um valor menor.

Em vez de reconstruir os relacionamentos que foram descobertos na etapa de pesquisa, o que envolve atravessar novamente por trilhões de combinações de estados possíveis, é mais eficiente construir o DAG durante a fase de programação dinâmica. Dentro do método solve, se um estado recém-construído pode atingir o estado de pangrama perfeito possível, armazene uma aresta direcionada do estado recém-construído para o estado original apenas se o estado original for menor que seu complemento (para reduzir a duplicação da aresta). p>

Imprima os frutos do seu trabalho em forma de árvore!

Provavelmente o formato mais fácil para visualizar os conjuntos de palavras resultantes é listá-los como árvores com o nó raiz como o estado de pangrama perfeito. Dado o DAG construído acima, a melhor maneira de desempacotar é fazê-lo recursivamente, gravando cada estado no disco em cada etapa, em vez de na memória, uma vez que a árvore é uma ordem de magnitude maior do que o DAG.

Um aprimoramento dessa forma de expansão é resumir os estados que têm apenas uma única combinação possível de palavras. Um estado que é uma máscara para palavras e nenhum subestado que o compõe pode ser resumido trivialmente. Um estado pode ser resumido se seus subestados e seus compostos puderem ser resumidos, e todas as máscaras derivadas de si mesmo e seus filhos não tiverem bits / caracteres sobrepostos. Imprimir o DAG resumido melhora a legibilidade da árvore de saída resultante, reduzindo-a e simplificando-a.

Uma vez que o resumo depende apenas do menor dos dois estados, iterando através da matriz do estado inicial de 0 para cima e usar as regras acima para gerenciar a regra de sumarização permite que isso seja concluído em tempo linear.

Árvores de pangrama produzidas!

Sinta-se à vontade para percorrer as árvores de pangrama perfeitas para ver se você pode encontrar frases interessantes!

Existem muitos pangramas perfeitos possíveis

Fiquei surpreso com o número de pangramas possíveis perfeitos. Há um monte! A melhor estratégia para juntá-los não requer um processador de linguagem natural complexo. Uma vez que as palavras candidatas foram rotuladas como substantivo ou verbo elegível, o pacote de palavras deve conter pelo menos um substantivo, um verbo e a proporção correta de substantivos e verbos.

A qualidade dos dados é um problema difícil

A seção de algoritmo levou dois dias, mas o problema de qualidade de dados levou duas semanas. Quando mencionei essa descoberta para meu amigo, que é engenheiro sênior da equipe do Google, ele não se surpreendeu, comentando que os problemas de qualidade de dados são alguns dos problemas mais difíceis na engenharia. Lição aprendida.

As regras dos pangramas perfeitos

Existem muitas nuances quanto ao que se qualifica como um pangrama perfeito! Eu queria pesquisar pangramas sem interjeições (por exemplo, hm, pht), mas também existem outras restrições populares, como abreviações, acrônimos, contrações, inicialismos, letras isoladas, nomes próprios e algarismos romanos. Existem também palavras que são nomes de letras, como Qoph, que eu achei que são trapaceadoras.

Com algumas dessas restrições relaxadas, há muitos pangramas “perfeitos”. Na ordem de trilhões, provavelmente . Há muitos acrônimos e inicialismos.

O asterisco

O asterisco existe porque a definição de todos os pangramas perfeitos do inglês não está bem definida. Existem nuances relacionado ao que deveria ser permitido em pangramas perfeitos do inglês. Também existem muitas controvérsias sobre se algumas palavras são ou não palavras em inglês. Dadas essas nuances, é realmente difícil dizer que encontrei todos os pangramas perfeitos. Posso fazer duas afirmações com bastante segurança:

1. Encontrei uma metodologia para produzir todos os pangramas perfeitos de inglês e outras línguas com conjuntos de caracteres semelhantes ou menores.
2. I enumeraram todos os conjuntos de palavras que podem formar pangramas perfeitos usando o dicionário oficial do torneio Scrabble y, OWL3.

Sinta-se à vontade para produzir seus próprios pangramas perfeitos com as técnicas descritas neste post!

Dependência dos Pangrams perfeitos de palavras de raízes galesas e árabes

Palavras derivadas de galês e árabe foram realmente importantes para a existência de pangramas ingleses perfeitos (a menos que as restrições do pangrama perfeito sejam relaxadas). Usando a lista de palavras OWL3 com regras estritas relativas a pangramas perfeitos, não há pangramas perfeitos que não incluam as palavras “cwm (s)” ou “crwth (s)”, ambas palavras galesas. No Scrabble internacional, a palavra derivada do árabe “waqf (s)” é uma palavra válida que pode produzir pangramas perfeitos sem recorrer a “cwm (s)” ou “crwth (s)”.

Eficiências do fluxo de trabalho

Era importante se tornar mais eficiente na paralelização de tarefas durante este projeto. Uma execução completa leva 25 minutos para o dicionário Unix e cerca de uma hora para os dicionários realmente grandes. Tive alguns problemas iniciais para alternar o contexto para uma janela de 30 minutos, mas fui melhorando à medida que aumentava minha produtividade.

Extensão / Generalização – Localizador de Anagramas

O pangrama perfeito search também é equivalente a um localizador de anagramas para a string “abcdefghijklmnopqrstuvwxyz”. E se você quisesse construir um localizador de anagramas genérico?

A mesma técnica pode ser usada contanto que a representação de estado e regras de gerenciamento para verificação a validade da combinação de palavras é atualizada. Em vez de os estados serem gerenciados como um número inteiro, seria mais fácil rastrear o estado como um mapa dos caracteres relevantes. Ver se as combinações são válidas é dizer que a combinação de dois mapas não excede o a contagem de caracteres desejada do anagrama para cada letra. Apenas certifique-se de que o espaço de estado seja tratável; com muitas letras, o espaço de pesquisa pode ficar muito grande em um instante. Além disso, você tem permissão para repetir palavras? Certifique-se de definir essas regras dentro sua programação dinâmica solução.

Idiomas com alfabetos maiores

Esta abordagem e solução são lineares no tamanho do conjunto de palavras, mas exponenciais no tamanho do alfabeto. Essa abordagem pode não funcionar com um conjunto de caracteres maior, digamos, o japonês moderno, que tem 46 silabários. 2⁴⁶ é 70.368.744.177.664; mais de um milhão de vezes maior do que o espaço de pesquisa em inglês de 2²⁶ = 67,108,864.

Não está totalmente claro se essa abordagem funcionaria ou não para o japonês. Se a língua japonesa tiver entropia suficientemente baixa, o que é possível, essa abordagem seria viável. Em vez de inicializar uma matriz de tamanho 2⁴⁶, os estados serão mantidos rastreados em um mapa. Além disso, a estrutura do japonês pode ser explorada; por exemplo, o kana を (wo) é quase exclusivamente usado como um particípio pós-posicional e pode ser excluído da pesquisa, reduzindo o espaço de pesquisa.

O idioma cambojano Khmer tem o maior alfabeto, com 74. Outra possível próxima etapa é explorar soluções que são subexponenciais no tamanho do alfabeto.

Inspiração

Fui inspirado pelo avanço de Aubrey De Grey em encontrar o número cromático do plano a ser pelo menos 5. Este é um avanço significativo que foi alcançado por meio de métodos computacionais básicos.

Não é preciso dizer que encontrar pangramas perfeitos não se compara a melhorar o limite inferior do número cromático de um plano.

Isso me faz acreditar que existem muitos problemas fáceis de encontrar que possuem métodos computacionais simples para resolver um problema que é intratável manualmente. Eu o desafio a encontrar e resolver alguns desses problemas. Por favor, deixe-me saber se você encontrar algo!

Obrigado

Estou muito grato pelos meus excelentes amigos que ajudaram revisando e improvisando isso comigo, especialmente Anna Zeng, Catherine Gao, Danny Wasserman, George Washington e Nick Wu!