- A flexão de nomes próprios islandeses muda para quatro formas de acordo com o contexto
- Foi desenvolvida uma funcionalidade, por meio de uma biblioteca JavaScript orientada por dados, que retorna o caso gramatical apropriado para o nome informado
- Ao armazenar todos os nomes diretamente, ocorriam aumento de tamanho e problemas de dados faltantes; isso foi resolvido com a estrutura trie e técnicas de compressão
- Graças à compressão por trie, foi possível inferir automaticamente com base em padrões comuns e alcançar um banco de dados muito pequeno que cobre mais de 80% dos dados
- Em situações comuns, mostra mais de 74% de precisão, e para o setor público e contextos que exigem alta precisão é oferecida uma versão strict separada
Contexto do problema
- Ao exibir nomes próprios em interface islandesa, ocorrem dificuldades devido à declinação (declension)
- Nomes islandeses mudam de forma conforme 4 casos gramaticais, como nominativo, acusativo, dativo e genitivo
- Como os bancos de dados costumam guardar nomes em forma nominativa, surgem dificuldades quando outro caso é necessário pelo contexto
- Usar a forma errada pode soar inautêntico ou estranho para nativos
Coleta e limpeza de dados
- A Islândia disponibiliza os dados da DIM (Database of Icelandic Morphology), mantidos pela Árnastofnun
- Os dados de flexão de nomes podem ser processados em CSV no Kristín’s Format (K-format)
- O conjunto completo da DIM tem 7 milhões de linhas e é excessivamente grande, mas foi possível obter dados de flexão para cerca de 3.600 nomes ao filtrar apenas 4.500 nomes próprios oficialmente aprovados
- É possível construir um array de formas do nominativo ao genitivo para cada nome
Estrutura básica da biblioteca
- A implementação inicial começou com a função applyCase, que retorna a forma correta a partir do array de variações por caso de nomes
- Porém, a carga por array simples era grande, com 30kB comprimidos via gzip
- Havia a limitação de não suportar nomes não incluídos nos dados
Remoção de duplicidade e extração de padrões
- Extraíram-se prefixos comuns entre as quatro formas de nomes para guardar apenas o conjunto de sufixos (suffix encoding) de cada um, minimizando duplicação
- Descobriu-se que muitos nomes seguem o mesmo padrão de flexão
Introdução de trie para combinação de padrões
- Por meio da estrutura de trie (inserção reversa baseada em sufixos), otimizou-se o mapeamento de valores para grupos de nomes com padrões compartilhados
- Armazena-se a informação de flexão uma vez apenas para padrões comuns de final de nome (name endings), obtendo alta capacidade de previsão para nomes novos
Compressão e otimização da trie
- Se o valor for igual em cada folha de uma subárvore, atribui-se esse valor ao nó pai e removem-se os filhos para comprimir a árvore
- Com isso, o número de nós caiu em até 15,4% e o tamanho foi reduzido para 4.01kB
- Uma segunda compressão, que funde nós-irmãos folha com valores iguais em um único nó, alcançou 3.27kB
Desempenho e generalização da trie
- Ao inserir um novo nome, torna-se possível a flexão automática baseada em padrões semelhantes
- Na prática, em nomes desconhecidos foram observados 74% de flexão correta e 26% de erro; no critério de usuários reais, a taxa de erro ficou em apenas 0,34%
- Quanto maior a regularidade (regularity) e a abrangência (comprehensiveness) dos dados, maior o efeito positivo em precisão de compressão e inferência automática
Biblioteca real e aplicação
- O resultado final foi lançado como a biblioteca beygla, que usa trie comprimido
- É oferecida uma versão de tamanho mínimo (4.46kB) e um módulo strict (15kB) personalizado, mais rigoroso e completo
- O módulo strict para lugares que exigem 100% de precisão, como documentos públicos, e a versão leve para aplicativos web comuns
Conclusão e possibilidade de expansão
- A compressão de dados de padrões de flexão linguística com trie pode ser aplicada para automatizar nomes próprios, endereços e outros substantivos em outras línguas flexivas, além do islandês
- A combinação de dados de alta regularidade com compressão em trie é uma estratégia para maximizar a eficiência de dados e desempenho da automação de flexão
Notas de agradecimento
- No desenvolvimento do beygla, foram feitos feedbacks de vários especialistas e otimizações
- A compressão adicional da trie reduziu o tamanho de 3.43kB para 3.27kB
Resumo
- Este é um exemplo de miniaturização e automação do problema de automação da flexão de nomes islandeses por meio de uma estrutura de dados trie baseada em padrões
- Oferece insights relevantes como exemplo prático de estratégia de tratamento de dados com trade-off adequado entre tamanho e precisão
1 comentários
Comentários do Hacker News
Quando comecei a aprender espanhol no ensino médio, usei um software para Windows que mostrava infinitivos e tempos verbais em sequência, e eu tinha que inserir a conjugação correspondente. Esse treino fez as regras gramaticais entrarem no automático e eu fiquei bem fluente nisso. Mas, ao aprender russo, as declinações de caso de repente ficaram difíceis, e por mais que eu procurasse um app que explicasse ou permitisse praticar padrões parecidos, nunca encontrei. Fico curioso se alguém conhece algum app para isso (web ou macOS/iOS)
Existe um deck de flashcards no Anki que usa um método chamado "KOFI (Konjugation First)". KOFI significa aprender todos os padrões de conjugação antes de estudar a língua em si. Depois de estudar francês e perceber que minha conjugação era fraca, experimentei esse método; mesmo falando com erros gramaticais ainda dava para me comunicar no dia a dia, mas não era o nível que eu queria. A proposta é decorar todos os padrões de conjugação em pouco tempo antes de aprender a língua. Um dia quero aplicar isso seriamente a uma nova língua. Acabei largando porque perdi o interesse em francês. Link para o deck do Anki
Enquanto aprendia russo, cheguei a montar um script combinando o módulo Python spaCy com um módulo grande para russo, para fazer lematização contextual e extrair etiquetas gramaticais. Mas, na prática, quando meu russo realmente melhorou, foi muito mais eficaz abandonar a tentativa de desmontar logicamente cada flexão e, em vez disso, acumular na cabeça uma biblioteca de padrões (incluindo exceções) por meio de uso e repetição. Aqui, "contexto" significa o sentido dentro da frase
Quando estudei espanhol por conta própria, 25 anos atrás, usei um dicionário espanhol/inglês. Os infinitivos vinham com um índice numérico, classificando-os em grupos com o mesmo padrão de conjugação. No começo do dicionário havia tabelas com todas as conjugações de um verbo representativo de cada grupo, em todos os tempos. Verbos irregulares tinham um índice separado e, do mesmo jeito, eram agrupados com outros verbos irregulares semelhantes (por exemplo: tener, detener). Todos os verbos acabavam organizados de forma bem limpa em algumas dezenas de padrões distintos. Cheguei a pensar em criar um software de quiz aproveitando esse sistema, mas nunca fiz. Fico me perguntando se o padrão de reverse-string trie mencionado no artigo também poderia ser usado nesse tipo de classificação
Tive a ideia de memorizar mais rápido as declinações de caso do russo criando flashcards com combinações de preposição + adjetivo + substantivo. Antes disso eu já tinha aprendido latim, e para o latim eu não esperava decorar as declinações tão rápido assim (a menos que eu fosse um monge?), mas no russo eu queria aprender depressa. No fim, isso nunca virou projeto
Estou usando o ConjuGato para iOS para praticar conjugação em espanhol. No modo de jogo, ele mostra o infinitivo/tempo/pessoa, e você tem que lembrar a forma conjugada. Dá para praticar só verbos irregulares, então é ótimo para aprender exceções
Para os 800 nomes cujas informações de declinação estão faltando no banco de dados, a solução mais direta parece ser simplesmente atribuir manualmente as declinações. Um falante nativo conseguiria terminar isso em poucas horas e, mesmo no caso de nomes totalmente desconhecidos, pelo menos daria para estimar formas que não soassem obviamente estranhas. Ou então dar para pedir isso a um LLM por um custo muito baixo. Ainda assim, codificar o resultado para distribuição numa estrutura trie dessas continua sendo uma boa ideia. Só não precisa usar a trie também como estimador de declinações
Seria desejável cobrir mais nomes — no DIM isso é uma lacuna que precisa continuar sendo preenchida. Na Islândia, novos nomes são adicionados com frequência à lista de nomes permitidos, então sempre vão existir lacunas. Eu, pessoalmente, não tenho confiança suficiente para acrescentar os dados por conta própria, e sempre que revisava resultados de 100 nomes não verificados, muitas vezes pensava: “será que isso está certo?”. Várias vezes consultei nomes parecidos no DIM e pensei: “eu não declinaria assim”. Por isso, trato os dados do DIM como a fonte da verdade mantida por especialistas da língua
Trabalho manual ajuda, mas ainda tem limitações para nomes fora da lista oficial (nomes estrangeiros etc.). Eu também moro em um país com uma lista centralizada de nomes, mas é possível pedir exceções, e pessoas nascidas antes de a lista existir ou imigrantes podem ter nomes que não estão nela. Nesses vários casos mistos, uma função de “prever uma flexão mais ou menos adequada” ainda seria útil
Não encontrei motivo para achar que um LLM faria previsões de declinação melhor do que uma trie (a menos que o exemplo específico já esteja nos dados de treino do LLM; nesse caso, uma busca na web talvez seja melhor)
Fiquei curioso se os LLMs atuais já aprenderam esses padrões
Não tenho certeza se o Rails resolve isso automaticamente, mas antigamente ele fazia esse tipo de mágica muito bem. Há muito tempo eu vi o código-fonte de
pluralise, e ele tinha codificadas até regras de plural irregular do galêsUma ideia de otimização seria, em vez de a trie mapear diretamente para a própria string de sufixos, criar um array de sufixos únicos e fazer a trie apontar para o índice desse array. Por exemplo:
E então referenciar o índice assim:
Testei isso diretamente com o Claude Code e, no gzip, acabou ficando 100 bytes maior (3456 -> 3556), embora o tamanho sem compressão tenha caído 20%. Parece que o próprio gzip já é muito bem otimizado para padrões repetidos
Dando um passo além, também daria para colocar os próprios sufixos numa trie e identificar subárvores idênticas para eliminar duplicação. Se puder usar gzip, deve haver alguma otimização inteligente com esse array de sufixos. Se usar um formato binário otimizado, talvez fique ainda melhor
Pessoalmente, continuo achando que deve existir alguma solução mágica que faça isso em <1kb sem compressão. Talvez criar uma lista minimizada de expressões regulares que classifique os nomes com 100% de precisão? Um bloom filter enorme? Ou usar features especializadas em vez de um hash genérico?
Parece uma questão de entrevista vinda direto de um pesadelo. Usar uma trie ao contrário (em ordem reversa) é o tipo de coisa que você só vai usar uma vez na vida, mas, quando usar, vão te chamar de mago
Em vez de fazer isso em JS, talvez desse para o banco de dados já devolver todas as combinações de nome+caso, e então escolher e exibir só o que for necessário no momento da renderização. Ou seja, tratar isso na camada de localização. Fico curioso sobre como isso funcionaria em cenários multilíngues. Quando uma UI em islandês lida com um nome francês, imagino que usaria sempre o nominativo; e uma UI em inglês lidando com um nome islandês provavelmente também. No fim, isso talvez só fique realmente importante em contextos de se dirigir diretamente ao usuário ou em painéis administrativos (“usuário x respondeu ao usuário y”) etc.
Existem 88 nomes com um certo padrão de declinação que terminam em “idur”, “tur”, “ður”, mas o mesmo sufixo nem sempre segue o mesmo padrão de declinação. O problema parece simples por regra, mas na prática é muito interessante. Será que o padrão de sufixo tem relação com a pronúncia da sílaba anterior? Se a ideia for lidar melhor com nomes desconhecidos, talvez fosse preciso extrair com NLP uma representação da pronúncia do nome, em vez de olhar só para letras, e então consultar uma trie ou algo do tipo?
É bom tomar cuidado para esse tipo de reflexão não descambar para uma discussão sobre Dependent Types
É uma ideia perspicaz. Na prática, existem até nomes com a mesma pronúncia, mas com padrões de declinação diferentes. Por exemplo:
Em cenários como o do beygla/strict, perfect hashing pode ser uma alternativa a considerar
Me surpreende que a flexão de caso de nomes islandeses seja simples o bastante, com padrões suficientemente determinísticos, para esse tipo de abordagem funcionar bem. Língua, em geral, costuma ser algo bem complexo