patternMinor
Where did Don Knuth say that suffix trees were the "Algorithm of the Year 1973?"
Viewed 0 times
suffixtheyeardidwheresaytreeswerealgorithmthat
Problem
If you do a quick search for suffix trees on Google, you'll find a bunch of sources saying that Don Knuth called them the "Algorithm of the Year 1973." However, I can't seem to find a source on this.
Is there a reference to a paper, communication, etc. where Knuth specifically says this about suffix trees?
Is there a reference to a paper, communication, etc. where Knuth specifically says this about suffix trees?
Solution
The source of the quote seems to be From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction by Giegerich and Kurtz.
On page 347, at the start of Section 6 (An Explanation of Weiner's Algorithm), they write
In this section we go back to the roots
and take a look at the “Algorithm of the Year 1973” (D. E. Knuth according to [19]).
Reference [19] is an unpublished manuscript:
[19] V.R. Pratt. Improvements and Applications of the Weiner Repetition Finder. Unpublished manuscript,
Cambridge, MA, 1973.
Apparently these are lecture notes (this is how they are referred to in the monograph Image and Text Compression by Storer).
On page 347, at the start of Section 6 (An Explanation of Weiner's Algorithm), they write
In this section we go back to the roots
and take a look at the “Algorithm of the Year 1973” (D. E. Knuth according to [19]).
Reference [19] is an unpublished manuscript:
[19] V.R. Pratt. Improvements and Applications of the Weiner Repetition Finder. Unpublished manuscript,
Cambridge, MA, 1973.
Apparently these are lecture notes (this is how they are referred to in the monograph Image and Text Compression by Storer).
Context
StackExchange Computer Science Q#90566, answer score: 7
Revisions (0)
No revisions yet.