Cómo implementamos la segmentación de palabras instantánea con Rust

Para sugerir y generar nuevas ideas de nombres de dominio, necesitamos identificar las palabras que componen un dominio. La segmentación de palabras es una técnica de procesamiento del lenguaje natural que suele utilizarse para encontrar palabras en cadenas de idiomas sin límites naturales entre ellas, como el chino o el japonés. La usamos para encontrar las palabras «Instant Domain Search» en dominios como instantdomainsearch.com. La biblioteca de Python wordsegment resuelve este problema, pero necesitábamos portarla a Rust para que fuera lo bastante rápida para Instant Domain Search.

Wordsegment se basa en el ejemplo de segmentación de palabras de Peter Norvig en Beautiful Data. La idea principal consiste en recorrer todas las segmentaciones posibles de una cadena y puntuarlas según su probabilidad de aparecer en un texto real. Para ello necesitamos dos componentes:

• Una forma de estimar la probabilidad de que una frase aparezca en el mundo real.
• Una forma eficiente de puntuar todas las segmentaciones posibles de la cadena de entrada.

Veamos cómo funcionan ambas.

Puntuar una frase

La forma más sencilla de puntuar las segmentaciones es asignar a cada palabra una puntuación según su probabilidad de aparecer en datos reales en inglés. Norvig utilizó un conjunto de Google llamado Google Trillion Web Corpus (2006). La colección Web 1T está disponible públicamente solo para investigación y educación, y fue la que usé inicialmente para nuestra versión.

Para obtener la puntuación de aparición de una palabra, se divide el número de coincidencias de esa palabra en el corpus por el número total de apariciones de palabras. Por ejemplo, «instant» apareció unos 28 millones de veces en Web 1T. El corpus que usamos contiene unas 588.000 millones de palabras en total, ya que no incluye las palabras poco frecuentes de la cola larga, así que asignamos a «instant» una probabilidad de aparición de 0.000049. También debemos puntuar las palabras ausentes del corpus; consulta los detalles en el capítulo de Norvig.

El siguiente paso es puntuar una secuencia de palabras. Podríamos multiplicar las probabilidades de todas las palabras de la frase. Para evitar errores aritméticos al multiplicar una serie de números pequeños, tomamos el logaritmo en base 10 de cada valor y sumamos los resultados. Para «this is a test», obtenemos -2.3 + -2.1 + -1.8 + -3.6 = -9.7. En cambio, aplicar la fórmula para palabras ausentes del corpus da -22 para «thisisatest».

Para refinar los resultados, también consideramos bigramas, como Norvig: la probabilidad condicional de que dos palabras aparezcan juntas. Para cada palabra que no esté al principio de la cadena, consideramos la probabilidad de que aparezca después de la anterior, en lugar de su probabilidad simple. Con el corpus original, puntuamos «is» después de «this» como -3.2 en vez de -2.1, lo que permite usar información contextual para afinar las puntuaciones.

Enumerar las segmentaciones

Para cadenas cortas queremos enumerar todas las segmentaciones posibles y encontrar la de mejor puntuación. Pero como su número crece exponencialmente con la longitud de la entrada, esto deja de ser viable para cadenas largas. Al mismo tiempo, las palabras muy largas son cada vez menos probables. Por eso empezamos por definir una longitud máxima de palabra de 24 caracteres. Después dividimos la cadena en cada uno de los primeros 24 límites de caracteres y sumamos la puntuación de la primera palabra a la de las restantes.

Aunque Norvig usó recursión y nosotros seguimos ese enfoque en las primeras versiones en Rust, hace poco cambiamos la implementación a partir del artículo de Wolf Garbe Fast Word Segmentation of Noisy Text. Ahora usamos una variante del algoritmo de matriz triangular que describe. En nuestra implementación, un array de tamaño dinámico (Vec de Rust) guarda la mejor puntuación en cada posición de segmentación. Por ejemplo, para «thisisatest», el candidato de la posición 6, después de «is», tendría longitud 2 y la puntuación de «this is». Este enfoque limita el tamaño de la pila y me resulta más fácil razonar sobre los bucles anidados que sobre la recursión limitada. Adaptamos el enfoque de matriz triangular para admitir puntuaciones de bigramas.

Optimizaciones de rendimiento

En mi equipo, la biblioteca wordsegment de Python puede segmentar «thisisatest» una vez cada 500 µs. La última versión de instant-segment realiza la misma tarea en 4 µs, 95 veces más rápido y haciendo el mismo trabajo. Estas son algunas técnicas que usamos.

• La primera versión solo era 1,7 veces más rápida que el código Python. Enumeraba segmentaciones de forma recursiva, como wordsegment y el código de Norvig, y usaba un mapa hash para almacenar puntuaciones parciales. Por ejemplo, calcular las puntuaciones de «thisis a test» y «this is a test» es más rápido si se reutiliza la de «a test».
• Evitar algunas asignaciones innecesarias en el bucle principal y cambiar al algoritmo ahash para la caché elevó el rendimiento a 4,9 veces el de Python.
• Usar el crate smartstring para evitar asignaciones en el heap de cadenas cortas encaja bien con este problema, porque las palabras suelen ser cortas. La mejora llegó a 9,0 veces Python.
• Integrar en línea el bucle principal que produce las posiciones de segmentación nos llevó a 11 veces Python.
• Evitar asignaciones repetidas para resultados intermedios permitió alcanzar 12 veces Python.
• Las cadenas de Rust están codificadas en UTF-8, por lo que dividirlas requiere validar las posiciones. Sin embargo, instant-segment rechaza entradas no ASCII; una pequeña cantidad de código unsafe para omitir la validación Unicode mejoró el rendimiento a 15 veces.
• Actualizar ahash a una versión más reciente nos llevó a 18 veces.
• Cambiar f64::powf() por f64::powi() ayudó a llegar a 19 veces.
• Reutilizar asignaciones intermedias cuando se realizan varias segmentaciones seguidas elevó el rendimiento a 25 veces Python.
• Finalmente, adoptar el enfoque de matriz triangular nos llevó a 95 veces.

instant-segment

Hemos publicado este trabajo como código abierto y la última versión de instant-segment está disponible en crates.io. Este año añadimos enlaces para Python con la excelente biblioteca PyO3 y actualizamos los datos de prueba de nuestro repositorio para basarlos en conjuntos más recientes y con licencias más permisivas de Google y del proyecto SCOWL. Así resulta más fácil que nunca empezar con instant-segment. ¡Nos encantaría recibir tus comentarios y saber cómo lo usas!