Substituindo um banco de dados SQLite de 3 GB por um binário FST (transdutor finito de estados) de 10 MB

• Taskusanakirja é um dicionário finlandês-inglês que oferece busca por prefixo durante a digitação
• Com a expansão das formas flexionadas do finlandês, o número de entradas cresceu para 40 a 60 milhões, levando a trie ao limite
• Uma solução temporária com SQLite FTS era rápida, mas exigia um download inicial de 3 GB
• Um FST em Rust reduziu os dados do SQLite para um binário de cerca de 10 MB, uma redução de 300 vezes
• O FST compartilha tanto prefixos quanto sufixos, o que se encaixa bem em padrões repetitivos de flexão

---

A estrutura de busca do Taskusanakirja e os limites iniciais

• Taskusanakirja, ou tsk, é um dicionário finlandês-inglês com busca incremental enquanto o usuário digita
• Esse recurso é, essencialmente, um problema de busca por prefixo, e a solução clássica para autocompletar era uma implementação de trie
• A primeira implementação foi escrita em Go, e o objetivo inicial do projeto era distribuir o programa inteiro como um único .exe, um único .app ou um binário estaticamente linkado
• Com um vocabulário na casa de algumas centenas de milhares de palavras, para evitar corresponder a todas as entradas, inclusive aquelas que representavam alguns poucos por cento de um único dígito do total, o sistema retornava apenas os primeiros 50 ou 100 resultados e memorizava combinações de 1, 2 e 3 letras
• Dessa forma, foi possível colocar uma trie com otimizações básicas em cerca de 60 MB, e mesmo após um ano de uso pessoal intenso não havia latência perceptível

O problema de escala criado pelos dados de flexão do finlandês

• O finlandês é uma língua aglutinativa, então uma única palavra-base pode ter mais de 100 terminações quando se consideram todas as combinações
• As combinações não são regulares, e a ortografia finlandesa, altamente sistematizada, reflete diretamente na escrita a forma como os falantes realmente pronunciam, fazendo com que a palavra-base cresça, se desloque e se transforme ao se combinar com sufixos
• Um iniciante pode travar facilmente em uma frase como “Opiskelijassammekin on leijonan sydän”, e o tsk também tentava incluir informações para ajudar a dividir a palavra nos limites corretos
• Em termos linguísticos, essas transformações envolvem alternância consonantal e harmonia vocálica, e o finlandês usa as duas ao mesmo tempo
• Por exemplo, katu significa “street”, mas o genitivo não é katun, e sim kadun, porque o t enfraquece para d devido à sílaba fechada
• Multiplicando essa estrutura por 15 casos, 2 plurais, 6 sufixos possessivos e um número indefinido de enclíticos, uma trie ingênua não consegue compartilhar o custo das terminações finais, como -ssa-mme-kin, que são comuns a milhares de palavras
• Cerca de 400 mil entradas ainda podiam ser mantidas em uma trie com algo em torno de 50 MB de RAM, mas a mesma abordagem não escalava para 40 a 60 milhões de entradas
• Como solução temporária, as formas flexionadas foram colocadas em um banco separado com SQLite FTS para serem pesquisadas sob demanda; isso funcionava sem latência perceptível, mas exigia um download único inicial de 3 GB

O resultado da migração para Rust e FST

• Nove meses depois, ao tentar de novo em Rust, foi escrito um programa mínimo que extraía os dados do banco SQLite de 3 GB e os comprimia em um FST
• A motivação veio do texto de BurntSushi aka Andrew Gallant, Index 1,600,000,000 Keys with Automata and Rust, cuja ideia central é que máquinas de estados finitos podem representar de forma pequena e rápida conjuntos ou mapas ordenados de strings
• O binário resultante ficou com cerca de 10 MB, uma economia de aproximadamente 300 vezes em relação ao banco SQLite de 3 GB
• Esse caso de uso também combinava especialmente bem com a crate fst, porque o problema era mapear formas flexionadas e conjugadas de uma língua altamente aglutinativa de volta para sua definição original
• A trie comprime prefixos, mas o FST comprime tanto prefixos quanto sufixos
• Como o corpus do dicionário finlandês contém um pequeno conjunto de sufixos muito frequentes e repetidos, o compartilhamento de sufixos gera grande impacto
• Os dados também são estáticos em tempo de execução, o que evitou a maior fraqueza do fst

Por que o FST ficou menor que a trie

• O principal fator que torna um FST muito menor que uma trie em dados de linguagem natural é o compartilhamento de sufixos
• Uma trie compartilha prefixos, como em kadun e kaduille, que dividem os três primeiros nós, mas armazena separadamente os caminhos de sufixo diferentes
• Um autômato finito acíclico determinístico mínimo funde duas subárvores estruturalmente idênticas
• Em um corpus em que 100 mil palavras terminam com algo como 12 padrões flexionais iguais, essa fusão leva a uma grande economia de memória
• A principal heurística deste caso é substituir um banco de dados genérico improvisado por uma estrutura de dados pequena, estática e especializada, que faz exatamente o necessário, obtendo uma redução de memória de 300 vezes

O papel que a solução temporária com SQLite ainda deixou e o tamanho da distribuição

• A escolha pelo SQLite nove meses antes foi um caso de preferir “algo ruim, mas fácil” a “não conseguir fazer algo bom”, e na prática funcionou
• Como já havia familiaridade com a B-tree do SQLite e com a extensão Full Text Search, ela foi na época uma solução rápida de experimentar
• A mesma extensão FTS também é usada em alguns recursos menos utilizados que não estão no alpha do tsk v2.0.0, mas ela pode acabar sendo removida completamente se prejudicar a pegada de memória atual
• A versão Pro do v2 está ficando em torno de 20 MB com tudo incluído, o que a torna 3 vezes menor que a versão gratuita do v1
• O tsk começou originalmente como um programa TUI em Go, evoluiu a partir do protótipo anterior fzf-based finstem, e se conecta com the highest-ROI program I’ve written so far
• taskusanakirja significa “pocket dictionary” em finlandês, e o critério continua sendo que, se não couber até em um notebook velho, então não é um dicionário de bolso, mas algo mais próximo de um antigo dicionário Oxford compilado
• Há aí uma ideia recorrente de que “não tem problema resolver o mesmo problema duas vezes”: em vez de travar por culpa de não ter encontrado ainda a melhor implementação já existente, às vezes é preciso reinventar algumas rodas para atingir os limites reais mais rápido
• Essa visão se conecta com a Caplanian view de “prática”, e Do Ten Times as Much é apresentado como um conselho desconfortável, mas que funciona

[GN⁺]

Comentários do Lobste.rs

• O texto em si já era interessante, e foi legal ver uma ferramenta adequada aplicada ao trabalho certo para obter uma melhoria de uma ordem de grandeza, mas a nota de rodapé final me impressionou mais do que o corpo do texto
  Ela aponta com precisão aquela angústia que faz a gente parar por se sentir culpado, achando que a ferramenta que está construindo talvez já tenha sido implementada melhor por alguém há 30 ou 40 anos. Mas isso é uma armadilha, e fez sentido para mim a ideia de que é preciso reinventar algumas rodas para chegar até os limites de como se faz uma roda. Na maioria das áreas, quatro ou cinco já bastam, e mesmo em campos rigorosos como matemática ou ciência da computação talvez umas vinte e poucas sejam suficientes; além disso, o argumento é que as perguntas que surgem ao reconstruir isso por conta própria levam muito mais rápido à verdadeira fronteira do que apenas estudar

  • Um ponto relacionado importante no texto é que até uma implementação ineficiente de força bruta feita com SQLite DB tinha valor como implementação de referência
    Como já existia uma implementação de referência funcional, ficou mais fácil criar uma implementação eficiente para substituí-la
  • Isso cai como uma luva para o problema que estou vivendo agora. Eu queria construir algo otimizado para o meu espaço de problema, mas fiquei travado por saber que o problema generalizado já foi resolvido
    Só que, olhando para as soluções existentes, elas vêm com muita bagagem de que eu não preciso. Pela minha experiência, eu já sabia que valia a pena insistir na minha ideia, mas continuava pensando se não estaria deixando passar alguma coisa; depois de ler isso, resolvi simplesmente tentar. Mesmo que eu falhe, ainda vou aprender no processo

• Muito legal. Lembrou Compressing Icelandic name declension patterns into a 3.27 kB trie

• Ao implementar um bot de Scrabble, acabei conhecendo a estrutura de dados relacionada DAWG (Directed Acyclic Word Graph), que aparentemente é bem comum para esse tipo de uso
  A principal diferença em relação ao crate fst parece ser que ela não mapeia cada palavra para um inteiro único. Da mesma forma, o tamanho caiu bastante e o desempenho melhorou absurdamente. Um bot de Scrabble basicamente precisa filtrar o dicionário inteiro por palavras que correspondam a regexes simples como ..cat.., mas na prática precisa lidar com todas as regexes simples possíveis no tabuleiro atual. Algo que antes levava cerca de 1 minuto caiu para uma latência imperceptível

  • O artigo sobre DAWG de Appel e Jacobson, de 1988, apareceu recentemente também, e já havia sido compartilhado antes

• O texto linkado também vale a leitura: https://burntsushi.net/transducers/

• fst acabou sendo a ferramenta usada também no suporte a alemão do srgn, depois que o próprio Andrew recomendou
  É o mesmo espaço de problema de comprimir prefixos e sufixos em comum, e funciona muito bem. Como também era uma ferramenta de CLI, eu precisava de custo de inicialização mínimo, e o crate fst oferece carregamento zero-copy, então não há overhead em tempo de execução. O FST é gerado em tempo de compilação

• Muito legal mesmo, e seria ótimo ter algo assim também para alemão e inglês. Os compostos do alemão ainda me confundem bastante com frequência