40 Years of Suffix Trees

When William Legrand finally decrypted the string, it did not seem to make much more sense than it did before. But at least it did sound more like natural language, and eventually guided the main character of Edgar Allan Poe's "The Gold-Bug"36 to discover the treasure he had been after. Legrand solved a substitution cipher using symbol frequencies. He first looked for the most frequent symbol and changed it into the most frequent letter of English, then similarly inferred the most frequent word, then punctuation marks, and so on. Both before and after 1843, the natural impulse when faced with some mysterious message has been to count frequencies of individual tokens or subassemblies in search of a clue. Perhaps one of the most intense and fascinating subjects for this kind of scrutiny have been biosequences. As soon as some such sequences became available, statistical analysts tried to link characters or blocks of characters to relevant biological functions.