Reemplazar una base de datos SQLite de 3 GB por un binario FST (transductor de estado finito) de 10 MB

• Taskusanakirja es un diccionario finés-inglés que ofrece búsqueda por prefijo mientras se escribe
• Con la expansión de las formas flexionadas del finés, las entradas crecieron hasta 40 a 60 millones y el trie llegó a su límite
• La solución temporal con SQLite FTS era rápida, pero requería una descarga inicial de 3 GB
• Un FST basado en Rust redujo los datos de SQLite a un binario de unos 10 MB, un ahorro de 300 veces
• El FST comparte tanto prefijos como sufijos, así que encaja bien con patrones repetidos de flexión

---

La estructura de búsqueda de Taskusanakirja y sus límites iniciales

• Taskusanakirja, abreviado tsk, es un diccionario finés-inglés que ofrece una función de búsqueda incremental mientras se escribe
• Esta función es, en esencia, un problema de búsqueda por prefijo, y la solución clásica para autocompletado era implementar un trie
• La primera implementación se escribió en Go, y el objetivo inicial del diseño era distribuir todo el programa como un solo .exe, una sola .app o un único binario con enlace estático
• Con cantidades de palabras de un orden intermedio de seis cifras, para evitar hacer match con todas las entradas que podían corresponder a algunos porcentajes de un solo dígito, se devolvían solo los primeros 50 o 100 resultados y se memorizaban combinaciones de 1, 2 y 3 letras
• Con este enfoque fue posible meter un trie con optimizaciones básicas en unos 60 MB, y aun usándolo mucho durante un año no se percibía latencia

El problema de escala creado por los datos de flexión del finés

• El finés es una lengua aglutinante, así que una sola palabra base puede tener más de 100 terminaciones si se consideran todas las combinaciones
• Las combinaciones no son regulares, y la ortografía finlandesa, muy sistematizada, hace que la forma en que realmente hablan los hablantes quede reflejada tal cual por escrito, de modo que la palabra base crece, se desplaza y se transforma al combinarse con terminaciones
• A un principiante le resulta fácil atorarse con una palabra específica en una frase como “Opiskelijassammekin on leijonan sydän”, y tsk buscaba incluir también información para ayudar a dividir las palabras en los límites correctos
• En términos lingüísticos, estas transformaciones corresponden a la gradación consonántica y la armonía vocálica, y el finés usa ambas al mismo tiempo
• Por ejemplo, katu significa “street”, pero su forma genitiva no es katun, sino kadun, porque la t se debilita a d debido a una sílaba cerrada
• Si a esta estructura se le multiplican 15 casos, 2 plurales, 6 sufijos posesivos y una cantidad indeterminada de partículas enclíticas, un trie ingenuo no puede repartir el costo de terminaciones compartidas por miles de palabras, como -ssa-mme-kin
• Unas 400 mil entradas podían mantenerse en un trie usando alrededor de 50 MB de RAM, pero el mismo enfoque no escalaba a 40 a 60 millones de entradas
• Como solución temporal, las formas flexionadas se pusieron en una base de datos separada de SQLite FTS para consultarlas cuando hiciera falta; funcionaba sin latencia perceptible, pero exigía una descarga inicial de 3 GB

El resultado al cambiar a Rust y FST

• Nueve meses después, al intentarlo de nuevo en Rust, se escribió un programa mínimo en Rust que extraía datos de la base SQLite de 3 GB y los comprimía en un FST
• El detonante fue el texto de BurntSushi aka Andrew Gallant, Index 1,600,000,000 Keys with Automata and Rust, cuya idea central es que una máquina de estados finitos puede representar conjuntos o mapas ordenados de cadenas de manera compacta y rápida
• El binario resultante quedó en aproximadamente 10 MB, unas 300 veces menos espacio que la base de datos SQLite de 3 GB
• Este uso encajaba especialmente bien con el crate fst, porque el problema consistía en mapear formas flexionadas y conjugadas de una lengua altamente aglutinante de vuelta a su definición original
• Un trie comprime prefijos, pero un FST comprime tanto prefijos como sufijos
• En el corpus del diccionario finés hay unos pocos sufijos muy frecuentes que se repiten muchísimo, así que compartir sufijos produce un gran efecto
• Como los datos son estáticos y no cambian durante la ejecución, se evitó la mayor debilidad de fst

Por qué el FST quedó más pequeño que el trie

• La clave para que un FST sea mucho más pequeño que un trie en datos de lenguaje natural es compartir sufijos
• Un trie comparte prefijos, como cuando kadun y kaduille comparten los tres primeros nodos, pero guarda por separado las rutas de sufijos distintas
• Un autómata finito determinista acíclico mínimo fusiona dos subárboles estructuralmente idénticos
• En un corpus donde 100 mil palabras terminan con unos 12 patrones de flexión similares, esa fusión se traduce en un gran ahorro de memoria
• La heurística central de este caso es reemplazar una base de datos genérica improvisada por una estructura de datos pequeña, estática y especializada que hace exactamente lo necesario, obteniendo un ahorro de memoria de 300 veces

El papel que dejó la solución temporal con SQLite y el tamaño de distribución

• La elección de SQLite nueve meses antes fue un caso de preferir “algo malo pero fácil” antes que “no poder hacer algo mejor”, y en la práctica funcionó
• Como ya se entendían el B-tree de SQLite y la extensión Full Text Search, en ese momento era una solución con la que se podía experimentar rápido
• Esa misma extensión FTS también se usa para algunas funciones menos utilizadas que no están en el alfa de tsk v2.0.0, pero podría eliminarse por completo si perjudica la huella de memoria actual
• La versión Pro de v2 está apuntando a unos 20 MB incluyendo todo, lo que la hace 3 veces más pequeña que la versión gratuita de v1
• tsk empezó originalmente como un programa TUI en Go, evolucionó a partir del prototipo anterior basado en fzf llamado finstem, y se conecta con the highest-ROI program I’ve written so far
• taskusanakirja significa “diccionario de bolsillo” en finés, y se mantiene el criterio de que, si no cabe incluso en una laptop vieja, entonces no es un diccionario de bolsillo sino más bien un viejo diccionario Oxford compilado
• Aparece una idea recurrente de que “está bien resolver un problema dos veces”: en vez de quedarse paralizado por la culpa de no haber encontrado una implementación mejor ya existente, a veces rehacer algunas ruedas por cuenta propia permite llegar más rápido a los límites reales
• Esta visión se conecta con la “práctica” en la Caplanian view, y Do Ten Times as Much se presenta como un consejo incómodo, pero que funciona

[GN⁺]

Comentarios en Lobste.rs

• El texto en sí ya era interesante, y me gustó ver cómo aplicar la herramienta adecuada al trabajo adecuado logró una mejora de un solo dígito, pero la nota al pie final me impresionó más que el cuerpo del artículo.
  Señala con mucha precisión esa duda que te paraliza por la culpa de pensar que la herramienta que estás creando quizá alguien ya la implementó mejor hace 30 o 40 años. Pero eso es una trampa, y me llegó mucho esa idea de que hay que volver a inventar algunas ruedas para poder llegar hasta los límites de lo que significa hacer ruedas. En la mayoría de los campos, con cuatro o cinco basta; incluso en áreas rigurosas como matemáticas o ciencias de la computación, quizá con unas veinte o veintitantas sea suficiente, y la tesis es que las preguntas que surgen al rehacerlas tú mismo te llevan a la verdadera frontera mucho más rápido que simplemente estudiar

  • Un punto relacionado importante en el artículo es que incluso una implementación ineficiente por fuerza bruta hecha con una base de datos SQLite tenía valor como implementación de referencia.
    Como ya existía una implementación de referencia que funcionaba, fue mucho más fácil crear una implementación eficiente para reemplazarla
  • Esto encaja exactamente con el problema que estoy viviendo. Quiero construir algo optimizado para mi espacio de problema, pero me había frenado porque sé que el problema generalizado ya está resuelto.
    Pero cuando veo las soluciones existentes, traen mucho equipaje que yo no necesito. Por experiencia sé que vale la pena empujar mi idea, pero seguía pensando si no se me estaría escapando algo; después de leer esto, decidí simplemente intentarlo. Incluso si fracaso, habrá aprendizaje en el proceso

• Muy genial. Me recordó a Compressing Icelandic name declension patterns into a 3.27 kB trie

• Implementando un bot de Scrabble conocí la estructura de datos relacionada DAWG (Directed Acyclic Word Graph), y parece ser bastante común para ese uso.
  La diferencia principal con el crate fst parece ser que no asigna cada palabra a un entero único. De forma similar, el tamaño se redujo muchísimo y el rendimiento mejoró de manera enorme. Un bot de Scrabble básicamente tiene que filtrar todo el diccionario por palabras que coincidan con expresiones regulares simples como ..cat.., pero en la práctica debe manejar todas las expresiones regulares simples posibles a partir del tablero actual. Una tarea que antes tardaba como un minuto pasó a una latencia imperceptible

  • El paper de DAWG de Appel y Jacobson de 1988 apareció hace poco y también se había compartido antes

• El artículo enlazado también vale la pena leerlo: https://burntsushi.net/transducers/

• fst terminó siendo también la herramienta usada para el soporte de alemán en srgn, después de que Andrew la recomendara directamente.
  Es el mismo espacio de problema de comprimir prefijos y sufijos comunes, y realmente funciona muy bien. Además, como es una herramienta CLI, también hacía falta minimizar el costo de arranque, y el crate fst soporta carga zero-copy, así que no hay overhead en tiempo de ejecución. El FST se genera en tiempo de compilación

• Está realmente genial, y ojalá hubiera algo así también para alemán e inglés. Los compuestos en alemán todavía me confunden seguido