Long Repeated Strings
(Illustrating Section 15.2 of
Programming Pearls)
Section 15.2
describes long repeated strings in text and gives
an example.
Here are some more examples,
generated
by this program
from several sources.
King James Bible
Verse Numbers Included
the house of his precious things, the silver, and the gold, and the spices, and
the precious ointment, and all the house of his armour, and all that was found
in his treasures: there was nothing in his house, nor in all his dominion, that
Hezekiah shewed them not.
This text is found in 2 Kings 20:13 and in Isaiah 39:2.
Each text line in the original file begins with the chapter and verse
(i.e., ``GEN 1:1 In the beginning God created ...'').
Long repeated strings therefore could not cross verse boundaries;
the next experiment deleted those identifiers.
Verse Numbers Excluded
, offered:
His offering was one silver charger, the weight whereof was an hundred and thirty
shekels, one silver bowl of seventy shekels, after the shekel of the sanctuary;
both of them full of fine flour mingled with oil for a meat offering:
One golden spoon of ten shekels, full of incense:
One young bullock, one ram, one lamb of the first year, for a burnt offering:
One kid of the goats for a sin offering:
And for a sacrifice of peace offerings, two oxen, five rams, five he goats, five
lambs of the first year: this was the offering of Ahi
Numbers 7 describes offerings made over a period of twelve days;
much of this string appears twelve times.
Longest String That Occurs Twelve Times
, full of incense:
One young bullock, one ram, one lamb of the first year, for a burnt offering:
One kid of the goats for a sin offering:
And for a sacrifice of peace offerings, two oxen, five rams, five he goats, five
lambs of the first year: this was the offering of
This string occurs twelve times in Numbers 7.
This string was computed using the method of
Solution 15.8.
Programming Pearls
The Entire Text
6, 8, 12, 17-18, 51-55, 59, 62, 70-72, 82, 87-98, 116, 119, 121,
128, 137, 162, 164, 187-189, 206, 210, 214, 221, 230
I was surprised to find that the longest repeated string in the
book was in the index.
The same sequence of numbers are repeated for the entries for
``experiments'', ``run time'' and ``time, run''.
Index Excluded
expression is costly,
replace it by an algebraically equivalent expression
that is cheaper to evaluate.
I
This text appears in both the Logic Rules and the Expression Rules of
Appendix 4: Rules for Code Tuning.
The Iliad
The Entire Text
whose sake so many of the Achaeans have
died at Troy, far from their homes?
Go about at once among the host,
and speak fairly to them, man by man,
that they draw not their ships into the sea.
This example
(on Samuel Butler's translation of Homer's Iliad)
was used in
Section 15.2.
describes long repeated strings in text and gives
The text first occurs when Juno suggests it
to Minerva as an argument that might keep
the Greeks (Achaeans) from departing from Troy;
it occurs shortly thereafter when Minerva
repeats the argument verbatim to Ulysses.
Copyright © 1999
Lucent Technologies. All rights reserved.
Mon 6 Nov 2000