Autocompletar en python: Tries/Dagw vs suffix-arrays y familia

Esto es un problema que nos ha salido recientemente, tenemos que hacer sugerencias de autocompletar en las que no solo queremos los prefijos sino la posibilidad de completar cualquier match. Asi que el candidato obvio es alguna version avanzada del array de sufijos. Pues bien, no encuentro en Python 3 una libreria que sea lo suficientemente convincente.

He hecho unas cuantas benchmarks con un haystack de 18525 frases con longitud media de unos 22.3 caracteres. Ni muy grande ni muy pequeño, o tirando a pequeño, y por eso quizas es por lo que no hay forma de decidirse. He probado con 3 needles, una de un caracter, otra de 5 y otra de 11.

El tiempo a batir es el de una busqueda ingenua (NS), digamos [x for x in wordlist if subs in x], que tarda 7.6 milisegundos.

Estos han sido mis resultados

       1        5         11           
ASI    0.740   0.00428   0.00302
NS     7.35    7.62      7.63
dawg   3.63    0.00473   0.00157
datrie 7.20    0.00605   0.000947
reS    2.72    0.374     0.82
findS  2.68    0.542     0.404
pss     -      0.0539    0.0549
cst    4.15    0.00516   0.00315
STree  8.58    0.0252    0.0269

Los packages pysubstringsearch (pss) y suffix_trees (STree) se quedan claramente detras del package csuffixtree, como era de esperar. Pero tambien se quedan detras de un Array de Sufijos Ingenuo (ASI) que pone todas las frases en una lista ordenada y luego se limita a buscarla con bisect

[[KwList[binpos[n]] for n in range(bisect_left(binListData,kwsubs),bisect_left(binListData,kwsubs+"|||"))]

Otra idea ingenua es unir todo el texto y buscarlo con re o find (reS, findS). En este caso, a pesar de que no es muy grande el total, se nota la ausencia de un ordenado previo.

No veo pues otra forma de competir con el bisect que no sea usando una libreria subyacente en C o en algun lenguaje compilado. He probado los packages datrie y dawg, que en principio son para la prediccion de prefijos, pero podemos introducir a lo bruto las mismas claves del array de sufijos, esto es 391398 entradas. Son de hecho mas largas que en el array ya que para evitar repeticiones, lo que hago es poner rotaciones en vez de simplemente sufijos. A base de gastar mas memoria (más de la que se deberia para un Trie que aceptara repeticiones) por lo menos se consiguen buenas velocidades para needles altas; pero no tengo claro si merece la pena añadir una dependencia mas.

Cierra google correlate

Daba para sacar curiosidades. Por ejemplo el indice del IBEX 35 estuvo en la crisis bien correlacionado con compraventa.com, y recientemente con las busquedas de la web de bbva autónomos, mas alguna que otra busqueda llamativa como “trabajo basura” (interesante que no es una anticorrelacion). Por supuesto, la migración masiva a internet y los cambios en pautas de busquedas hacen dificil encontrar nada concreto.

Si uno pondera el IBEX al 30% con la subida típica de “cuanto es”, aparece el indicador “cita seguridad social” y detalles de enfermedad de estomago como “bicarbonato de sodio” y “sin lactosa” (curiosamente, nada de ulcera). Al 50% el mix correlaciona con “santander empresas” y algun otro servicio similar, pero mas que nada por su implantación reciente. Una correlación curiosa es con motos “ktm”, igual es para trabajar de repartidor y no por vicio… También se busca la s line de audi, pero tambien furgonetas de ford, y prestamos para comprar coche y matricularlo. En cualquier caso son búsquedas que correlacionan a medio plazo, no detectan los crashes.

Curiosamente en ciertos niveles de mezcla, cuando parece que la bolsa va bien, hay una correlacion tambien con las busquedas sobre el fondo “metavalor”. Al menos algunos saben venderse. Bueno, tiene cierta logica, de hecho “fondos de inversion” correlaciona muy bien con el indice.

Otras cosas interesantes: busquedas de viajes a Madrid, “ave madrid barcelona”, “madrid barrio de salamanca”, hoteles como el claridge, sitios web de info como ecobolsa. “Simulador de prestamos” “extensiones de pelo”, “felguera” (casi la unica empresa que esta correlacionada con el ibex). Casas de apuestas como “kiroljokoa”.

Lo mas raro que he visto, el uso de una distro de seguridad, wifislax. Lo mas obvio a posteriori, la busqueda de “indicators” es un indicador.

Por supuesto, no contamos nada nuevo. En el mundo bitcoin la obsesion por las señales es notoria:
https://royalsocietypublishing.org/doi/full/10.1098/rsos.191068

Las variables macroeconomicas como el paro y el GPD tambien tienen correlacion alta con los indices, https://uvadoc.uva.es/bitstream/handle/10324/30959/TFG-N.940.pdf y enlazan con google search a traves del concepto de “Nowcasting”, https://jyx.jyu.fi/handle/123456789/66363

El efecto directo en la volatilidad o en el precio mismo se intenta explicar mediante teorias de atencion del inversor,https://link.springer.com/article/10.1007/s40953-019-00185-9 https://www.sciencedirect.com/science/article/abs/pii/S0275531918307967 etc. Un paper reciente sobre estrategias de inversion ya se queja de que los datos de correlate se congelaran en el 2017: https://www.nature.com/articles/s41598-019-50131-1

Otro Nature de 2013 que usa google correlate https://www.nature.com/articles/srep01684

Para españa, este analisis encuentra palabras de alta correlacion pero no llega a determinar si son precursores de la cotizacion. https://www.elsevier.es/es-revista-investigaciones-europeas-direccion-economia-empresa-345-articulo-senales-inversion-basadas-un-indice-S1135252312000548 (Habria que ver como se comporta la correlacion en funcion del desplazamiento de una curva respecto a otra, y para que shift ocurre el máximo). El equipo de esta publicacion parece que tambien queria intentar lo del analisis de sentimiento en twitter https://fdocuments.ec/document/google-y-twitter-le-dicen-lo-que-hara-la-bolsasi-sabe-como-escuchar-el-proyecto-matrix-big-data-de-cecabank.html

Una pequeña referencia para busquedas absolutas

Cuando miramos google trends nos da datos relativos, pero los avisos de busquedas diarias nos da datos absolutos. Por ejemplo hoy acaba de salir un aviso diciendo que zara ha pasado de medio millon de busquedas. Si comparamos estas ultimas 24 horas con google, con la wikipedia o con un par de palabras constantes tendriamos las proporciones

un: 39 los:44 wikipedia: 5 google:30 zara:30

vamos, que se podria estimar que diariamente en españa hay unas 730 000 busquedas que contienen el articulo “los”, o unas 650 000 que contienen el articulo “uno”. Y poco mas de 80000 que contengan la palabra wikipedia explicitamente. Esta referencia es bastante buena porque es muy raro que una busqueda politica, que son las que mas nos suenan, supere el tanto diario de “wikipedia”. Este año vox lo ha hecho dos veces, y ni psoe ni podemos (no estamos ya en el 2014) han llegado a ese ritmo.

De hecho igual es mejor calibrar con caso de 5000 o 10000 busquedas diarias. Se podria hacer un script.

EDIT: por otro lado, wikipedia se supone que recibe unas diez millones de “page views” diarias desde españa. Pero no se puede deducir un factor 10 ó 12 genericamente. Hay que tener en cuenta que no se añade la palabra wikipedia si no tienes que buscar a la segunda, muchas veces a la primera google ya te da un resultado. Y por supuesto una visita puede tener multiples page views.

Un bot para tendencias de busqueda

Pues visto que lo de acceder a las tendencias de busqueda en android funciona tambien como llamada directa a la api, he hecho un pequeño bot que manda los resultados a twitter.

Podeis ver el código en github, tiene su gracia porque usa Peony como cliente de twitter y pivota mucho, nunca mejor dicho, en las llamadas a aiohttp. En cambio la base de datos la he dejado con la version no asincrona de peewee.

La verdad es que las tendencias sugeridas tienen un comportamiento bastante raro; tienen mucho texto asi que no son las mas frequentes del dia, pero si que vienen a ser casos extremos a partir de las cuales se puede navegar. Como si se ejecutara primero alguna clusterizacion. En cambio las de Google-Go parece que son simplemente las mayoritarias, acumuladas en el dia.

Cómo activar google trends para España

Las tendencias de busqueda de Google llevan años desactivadas, nadie sabe por qué. Posiblemente debido a la “Tasa Google”, dado que la visualizacion que emplean en la web depende mucho de Google News. En mi fichero de logs, la ultima consulta con exito a placeid=p26 es del 19 de mayo de 2016.

Ahora, en los moviles, la app de Google (la googlequicksearchbox, a.k.a “Discover”) tiene una opcion para mostrarte las tendencias, que sí que funciona para IPs localizadas en España. Lo curioso es que no emplea la llamada a trends sino al autocompletado (aka “sugerencias de la barra de busqueda”).

Asi que de momento, hasta que le pongan mas control, basta con hacer algo así como

curl "https://www.google.com/complete/search?client=qsb-android-asbl-pb&q=" -H "user-agent: Mozilla/5.0 AppleWebKit/537.36 GSA/10.77.9.21.x86" -output trend.proto

Y voila, ya tenemos de nuevo las local trends… pero la informacion es ligeramente distinta.

If you can not see anything here, is because answer is opaque. Still you can see the network traffic in the debugger

Si usamos una app de geoscreenshoot, vemos claramente que aunque no especifiquemos ningun parametro la respuesta depende de la localizacion de la direccion IP. Pero no he encontrado como refinar más alla de la escala de país. Alguno de los parametros de /complete funcionan, por ejemplo hl o gl permiten buscar en otro indicativo de pais, incluso eu. He preparado en github.io una demo sampleando medio centenar de combinaciones.

Por cierto, que solo he visto en toda la clearnet una referencia a este client, en una pagina china de ingenieria inversa.

Tampoco he encontrado mucho (bueno, nada) de las tendencias que proporciona Google-Go. Esas parecen ser las mayoritarias diarias. Por lo que se ve, Google Go, aka “searchlite”, las pide mediante una llamada gRPC a GetTrendingSearchQueries, una función que reside en las apis privadas de google -o semiprivadas, porque a veces deja que chromium las use. El complete de Google Go tambien podría ser diferente, ya que emplea otro cliente, googleit-pb.