Suffix array: Difference between revisions

Revision as of 14:04, 15 May 2023

Revision as of 13:23, 31 October 2023

Line 162:

* fast in practice

One of the first algorithms to achieve all goals is the SA-IS algorithm of {{harvtxt|Nong|Zhang|Chan|2009}}. The algorithm is also rather simple (&lt; 100 [[Source lines of code|LOC]]) and can be enhanced to simultaneously construct the [[LCP array]].{{sfn|Fischer|2011}} The SA-IS algorithm is one of the fastest known suffix array construction algorithms. A careful [implementation by Yuta Mori<ref>{{Cite web |last=Mori |first=Yuta |title=sais |url=https://sites.google.com/site/yuta256/sais implementation|url-status=dead by|archive-url=https://web.archive.org/web/20230309123010/https://sites.google.com/site/yuta256/sais Yuta|archive-date=9 Mori]Mar 2023 |access-date=31 Aug 2023}}</ref> outperforms most other linear or super-linear construction approaches.

Beside time and space requirements, suffix array construction algorithms are also differentiated by their supported [[Alphabet (computer science)|alphabet]]: ''constant alphabets'' where the alphabet size is bound by a constant, ''integer alphabets'' where characters are integers in a range depending on <math>n</math> and ''general alphabets'' where only character comparisons are allowed.{{sfn|Burkhardt|Kärkkäinen|2003}}