Quel est l'algorithme de construction de tableaux de suffixes le plus avancé actuellement ?

Question

Je cherche un rapide suffixe-réseau algorithme de construction. Je suis plus intéressé par la facilité d'implémentation et la vitesse brute que par la complexité asymptotique (je sais qu'un tableau de suffixes peut être construit au moyen d'un arbre de suffixes en temps O(n), mais cela prend beaucoup d'espace ; apparemment d'autres algorithmes ont une mauvaise complexité big-O dans le pire des cas, mais fonctionnent assez rapidement en pratique). Les algorithmes qui génèrent un tableau LCP comme sous-produit ne me dérangent pas, puisque j'en ai besoin de toute façon pour mes propres besoins.

J'ai trouvé un taxonomie des différents algorithmes de construction de tableaux de suffixes mais il n'est pas à jour. J'ai entendu parler de SA-IS , qufsort et BPR mais je ne sais pas vraiment comment ils se comparent les uns aux autres, ni s'il existe des algorithmes encore meilleurs. Compte tenu de l'engouement que suscite actuellement le domaine des tableaux de suffixes, je suppose que d'autres algorithmes les ont remplacés depuis leur publication. Je crois me souvenir d'un article décrivant un algorithme rapide appelé "split", mais je n'arrive pas à le retrouver.

Alors, quel est l'état actuel de l'art ? Idéalement, j'aimerais avoir une courte liste des meilleurs algorithmes actuels (avec des liens, si possible) et un aperçu rapide de leurs forces et faiblesses relatives.

Answer 1

Actuellement, le meilleur constructeur de Suffix-Array connu est LibDivSufSort, de Yuta Mori : http://code.google.com/p/libdivsufsort/

Il utilise la méthodologie du tri induit (en gros, après avoir trié toutes les chaînes de caractères commençant par "A*", vous pouvez induire des tris de chaînes de caractères "BA*", "CA*" et "CA*"). "CA*" "DA*", etc.)

Elle est louée partout pour son efficacité et sa bonne gestion des cas dégénérés. C'est aussi le plus rapide, et il utilise la quantité optimale de mémoire (5N). La licence étant discrète, cet algorithme est intégré dans plusieurs autres programmes, comme par exemple la bibliothèque de compression libbsc, d'Ilya Grebnov. http://libbsc.com/default.aspx

À des fins de comparaison, vous trouverez un banc d'essai de la compression des tableaux de suffixes sur cette page : http://code.google.com/p/libdivsufsort/wiki/SACA_Benchmarks et cette page http://homepage3.nifty.com/wpage/benchmark/index.html

Le référentiel énumère également de nombreuses autres mises en œuvre SACA dignes d'intérêt. Néanmoins, pour des raisons de licence et d'efficacité, je recommande libdivsufsort parmi elles.

Edit : Apparemment, MSufsort est censé se diriger vers la version 4 bientôt, et est censé devenir plus rapide que Divsufsort. Si c'est vrai, il deviendrait un nouveau champion SACA. Mais encore, nous n'avons pas encore de date de sortie, et il s'agira d'une version alpha. Donc si vous avez besoin d'une implémentation éprouvée maintenant, libdivsufsort reste le meilleur choix.

Notez également que ces "meilleures implémentations SACA" n'utilisent pas "un algorithme de construction", mais combinent plusieurs astuces d'optimisation, ce qui les rend difficiles à résumer.

Answer 2

https://github.com/y-256/libdivsufsort/blob/wiki/SACA_Benchmarks.md donne la liste des algorithmes les plus rapides que vous souhaitez.

L'implémentation de kvark est la plus rapide dans la plupart des cas dans le benchmark ci-dessus. Vous pouvez trouver le code sur https://github.com/kvark/dark-archon .

libdivsufsort est une combinaison de l'algorithme d'Itoh-Tanaka et du post-processus de tri induit. Un sous-ensemble de suffixes est choisi tout comme l'algorithme de tri induit, mais au lieu de le résoudre récursivement par le tri induit, ils sont triés par l'algorithme d'IT.

libdivsufsort et l'implémentation de kvark sont toutes deux basées sur l'algorithme de IT.

L'algorithme de Ko-Aluru est similaire à l'algorithme de IT, qui apparaît dans 99. Ils divisent tous deux les suffixes en 2 catégories : type S ou type L. Si le i-ème suffixe est plus petit que le (i+1)-ème suffixe, il est de type S ; sinon il est de type L. Après avoir trié tous les suffixes de type S, nous pouvons déduire l'ordre de tous les suffixes de type L, puis nous avons terminé.

La différence entre l'algorithme de KA et l'algorithme d'IT est la suivante : KA utilise la récursion pour trier les sous-chaînes, tandis que l'algorithme d'IT fait appel au tri par insertion/MSD/quicksort multiclé.

Answer 3

Vous pourriez regarder :

Un tour rapide sur les tableaux de suffixes et les tableaux de suffixes compressés R Grossi - Informatique théorique, 2011

Les nouveaux algorithmes de tableaux de suffixes ne sont probablement plus développés au rythme que vous imaginez. Pour être à la pointe du progrès, je vous suggère de regarder les structures de données qui sont utilisées avec les tableaux de suffixes et de lire les articles sur les mathématiques liées aux tableaux de suffixes : Schürmann, Munro, He etc.