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.