Nota para os numerais: todos os números foram arredondados para o primeiro dígito significativo, porque sou fã do método “zequals” de Rob Eastaway para chegar ao ponto quando se trata de estimativa. É muito mais valioso seguir a heurística “algum cara conseguiu uma redução de memória de 300 vezes trocando um banco de dados que ele invadiu por uma estrutura de dados pequena, estática e especializada que faz exatamente o que ele precisa e nada mais”.
Encontrei-me com uma oportunidade cada vez mais rara de trabalhar neste fim de semana em Taskusanakirja, também frequentemente chamada tskum dicionário finlandês-inglês com pesquisa incremental conforme você digita.
Fundamentalmente, esse problema se resume à pesquisa de prefixo, e a solução canônica para pesquisa de prefixo com preenchimento automático é implementar um teste.
E isso funcionou maravilhosamente bem para a primeira implementação do tskque estava em Go (e sobre o qual escrevi em outro lugar e em outro lugar e em outro lugar). Com algumas otimizações básicas. Para evitar a correspondência em uma porcentagem de um único dígito do número médio de palavras de seis dígitos que estávamos inserindo no binário (desde o início tem sido um objetivo de design enviar o programa inteiro como um .exe, um .appou um
binário vinculado estaticamente), definimos um limite de, por exemplo, apenas as primeiras 50 ou 100 correspondências ou mais e depois memorizamos todas as combinações de 1, 2 e 3 caracteres, após o que nunca mais notei um atraso perceptível no programa após um ano de uso pessoal pesado. Poderíamos praticamente espremer uma tentativa com algumas otimizações básicas como essa em aproximadamente 60 MB de espaço.
Mas o finlandês é uma língua fortemente aglutinante. Não é impossível que uma única palavra base na língua tenha mais de cem finais possíveis, quando todas as combinações são consideradas. E as combinações não são regulares! A ortografia extremamente regularizada da língua finlandesa
também significa que não há mentiras quando se trata de quais alto-falantes
na verdade diga na página, e isso significa que as palavras básicas se estendem, mudam e se transmutam de maneiras acusticamente agradáveis à medida que você adiciona finais, o que faz todo o sentido
depois você já passou alguns anos imerso no idioma. Quando você é iniciante e vê uma frase como, por exemplo, “Opiskelijassammekin on leijonan sydän”, há uma palavra na qual você tem uma probabilidade desproporcional de ficar preso. Parte do que esta ferramenta tenta fazer é ajudar o aluno a descobrir como partir a palavra nas bordas direitas, incorporando todas essas informações também.
A tentativa caiu naquele ponto. Eu poderia manter cerca de 400.000 itens na tentativa, bebendo cerca de 50 MB de RAM. O mesmo truque não chega a 40-60 milhões. Não, se você quiser que tudo rode no laptop antigo de um universitário de Jacarta. Frustrado e sem tempo, levantei as mãos e disse: “Enviaremos as inflexões em um banco de dados SQLite separado com FTS (Full Text Search) e deixaremos que eles pesquisem isso se estiverem tão desesperados”, o que
trabalhado – ainda sem atraso perceptível – mas exigiu um download único de 3 gigabytes. Não é o ideal!
Foi aí que a história parou há cerca de 9 meses. Neste fim de semana, com mais 9 meses de intensa engenharia de software em tempo integral, perguntei corajosamente: Eu já havia pensado em reescrevê-lo em Rust?
Acontece que há um muito, muito cara inteligente chamado BurntSushi, também conhecido como Andrew Gallant, famoso por ripgrep, um grep realmente muito rápido – uma ferramenta tão onipresentemente útil que a coloquei anos atrás em minha “Santíssima Trindade” de comandos shell modernos – que também enfrentou um problema semelhante em algum momento no passado e escreveu um post chamado Index 1.600.000.000 Keys with Automata and Rust. (Aviso: longo, extremamente interessante.) A abertura estraga tudo:
Acontece que as máquinas de estados finitos são úteis para outras coisas além de expressar computação. Máquinas de estados finitos também podem ser usadas para representar de forma compacta conjuntos ordenados ou mapas de strings que podem ser [prefix, fuzzy, suffix] procurei muito rapidamente.
Bem, pensei, isso parece promissor. Vamos escrever um programa Rust mínimo para retirar os dados desse banco de dados de 3 GB e compactá-los em uma dessas coisas do FST. Quer dizer, sempre foi óbvio que era um hack, mas foi o melhor hack que consegui fazer com o tempo e a energia da época. Quão pequeno poderíamos conseguir?
Dez _mega_bytes. Uma redução de 300x no espaço. Mesmo no mundo de fst Para usuários de crate, esse aplicativo específico — mapeando conjugações e declinações de uma linguagem altamente aglutinativa de volta às suas definições de origem — era extremamente adequado ao domínio. Ao contrário das tentativas, os FSTs compactam
ambos prefixos e sufixos, e em uma língua como o finlandês, há um pequeno número de sufixos populares que são repetidos com muita frequência no corpus do dicionário. A carga de dados é estática em tempo de execução, o que contorna fsta maior fraqueza.
Gostaria de salientar, claro, que a razão pela qual foi possível fazer experiências baratas e deparar-me com este acaso foi porque, há 9 meses, confrontado com a escolha entre fazer a coisa má e fácil ou a boa nada, optei por fazer a coisa má e fácil.
O banco de dados SQLite funcionou! EU entendido
como funcionou, nos bastidores com suas árvores B e sua extensão Full Text Search. Acho que até usei a mesma extensão FTS para potencializar alguns recursos menos usados que são não nos alfas de tsk v2.0.0 no momento e provavelmente serão totalmente abandonados se isso significar comprometer essa pegada de memória agora salivante.
Porque a versão Pro do
v2 está chegando a cerca de 20 megabytes, com todas as baterias incluídas, o que é 3 vezes menos que a versão gratuita do v1
sempre foi. Veremos o que passará pela sala de edição a tempo.
Fonte: theverge
