c++ - ingles - trie significado

¿Hay alguna buena biblioteca de C++ Suffix Trie?

Question

¿Alguien sabe de una biblioteca C ++ realmente sólida para intentos de sufijo? Aparte de la de Mummer?
Idealmente, me gustaría:
Algún concepto de concurrencia.
Buen comportamiento de caché.
Licencia permisiva.
Soporte para alfabetos arbitrarios.

Answer 1

Habiendo usado y olvidado PATL, me gustaría incluir un enlace en una respuesta.
code.google.com/p/patl
Tiene un par de características realmente distintas, y en general es una lectura agradable también.

Answer 2

Lo más probable es que este sea un tutorial pero IMO vale la pena leerlo y con el código fuente: http://marknelson.us/1996/08/01/suffix-trees .

Answer 3

Siendo bioinformático, mi elección sería SeqAn (consulte la sección del índice de secuencias ). Implementa un árbol de sufijos perezosos y una matriz de sufijos mejorada (una estructura de datos equivalente), los cuales tienen un buen comportamiento de caché.