s15.ps

c programming pearls answer

DpostDict begin
/saveobj save def
mark
5 pagesetup
20 H f
(Markov English Letters)2 2040 1 2040 960 t
20 HI f
(Monkey Typing:)1 1416 1 720 1560 t
20 H f
(uzlpcbizdmddk njsdzyyvfgxbgjjgbt-)1 3076 1 2192 1560 t
(sak rqvpgnsbyputvqqdtmgltz ynqotqigexjumqphu-)2 4408 1 720 1800 t
(jcfwn ll jiexpyqzgsdllgcoluphl sefsrvqqytjakmav)3 4144 1 720 2040 t
20 HI f
(Order-0:)720 2520 w
20 H f
(saade ve mw hc n entt da k eethetocusos-)8 3764 1 1522 2520 t
(selalwo gx fgrsnoh,tvettaf aetnlbilo fc lhd okleut-)6 4264 1 720 2760 t
(sndyeoshtbogo eet ib nheaoopefni ngent)4 3636 1 720 3000 t
20 HI f
(Order-1:)720 3480 w
20 H f
(t I amy, vin. id wht omanly heay atuss n)9 3504 1 1522 3480 t
(macon aresethe hired boutwhe t, tl, ad torurest t plur)9 4656 1 720 3720 t
(I wit hengamind tarer-plarody thishand.)4 3470 1 720 3960 t
20 HI f
(Order-2:)720 4440 w
20 H f
(Ther I the heingoind of-pleat, blur it dwere)7 3718 1 1522 4440 t
( lar on wassing, an sit.")5 2058( Yout)1 526(wing waske hat trooss.)3 2030 3 720 4680 t
("Yould," "I that vide was nots ther.)6 3020 1 720 4920 t
20 HI f
(Order-3:)720 5400 w
20 H f
(I has them the saw the secorrow. And win-)8 3782 1 1522 5400 t
(tails on my my ent, thinks, fore voyager lanated the)9 4532 1 720 5640 t
(been elsed helder was of him a very free)8 3616 1 720 5880 t
20 HI f
(Order-4:)720 6360 w
20 H f
(His heard." "Exactly he very glad trouble,)6 3636 1 1522 6360 t
( it on of the who dif\256centralia.)6 2602( That)1 514(and by Hopkins!)2 1440 3 720 6600 t
(He rushed likely?" "Blood night that.)5 3192 1 720 6840 t
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-15-5)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 5 5
%%Page: 6 6
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
6 pagesetup
20 H f
(Markov English Words)2 2004 1 2058 960 t
(A \256nite-state Markov chain with stationary transition)6 4572 1 720 1560 t
(probabilities.)720 1800 w
20 HI f
(Order-1:)720 2280 w
20 H f
(The table shows how many contexts; it)6 3448 1 1522 2280 t
(uses two or equal to the sparse matrices were not)9 4430 1 720 2520 t
( Section 13.1, for a more ef\256cient that)7 3340(chosen. In)1 984 2 720 2760 t
(``the more time was published by calling recursive)7 4402 1 720 3000 t
(structure translates to build scaffolding to try to know)8 4676 1 720 3240 t
(of selected and testing and more robust)6 3530 1 720 3480 t
20 HI f
(Order-2:)720 3960 w
20 H f
(The program is guided by veri\256cation)5 3290 1 1522 3960 t
(ideas, and the second errs in the STL implementa-)8 4498 1 720 4200 t
(tion \(which guarantees good worst-case perfor-)5 4194 1 720 4440 t
(mance\), and is especially rich in speedups due to)8 4386 1 720 4680 t
( should be to use a macro:)6 2368( Everything)1 1060(Gordon Bell.)1 1116 3 720 4920 t
(for)720 5160 w
20 HI f
(n)1010 5160 w
20 S f
(=)1171 5160 w
20 H f
( its run time;)3 1092(10 , 000,)2 704 2 1314 5160 t
20 HI f
(Order-3:)720 5640 w
20 H f
(A Quicksort would be quite ef\256cient for the)7 3762 1 1522 5640 t
(main-memory sorts, and it requires only a few dis-)8 4434 1 720 5880 t
(tinct values in this particular problem, we can write)8 4470 1 720 6120 t
(them all down in the program, and they were making)9 4664 1 720 6360 t
(progress towards a solution at a snail's pace.)7 4006 1 720 6600 t
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-15-6)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 6 6
%%Page: 7 7
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
7 pagesetup
20 H f
(Algorithms and Programs)2 2262 1 1929 960 t
(Shannon, 1948: ``To construct [order-1 letter-level)5 4408 1 720 1560 t
(text] for example, one opens a book at random and)9 4548 1 720 1800 t
( letter is)2 702( This)1 490(selects a letter at random on the page.)7 3430 3 720 2040 t
( book is then opened to another page)7 3334(recorded. The)1 1306 2 720 2280 t
( The)1 458(and one reads until this letter is encountered.)7 4010 2 720 2520 t
( to)1 224( Turning)1 792(succeeding letter is then recorded.)4 3070 3 720 2760 t
(another page this second letter is searched for and)8 4524 1 720 3000 t
( similar pro-)2 1044( A)1 246(the succeeding letter recorded, etc.)4 3138 3 720 3240 t
(cess was used for [order-1 and order-2 letter-level)7 4438 1 720 3480 t
( It)1 224(text, and order-0 and order-1 word-level text].)6 4028 2 720 3720 t
(would be interesting if further approximations could)6 4530 1 720 3960 t
(be constructed, but the labor involved becomes)6 4210 1 720 4200 t
(enormous at the next stage.'')4 2580 1 720 4440 t
(Kernighan and Pike's Exposition, 1999)4 3440 1 720 4920 t
(Build a data structure while training)5 3124 1 1008 5400 t
(Randomly traverse the structure to generate)5 3928 1 1008 5880 t
(Implemented in C, C++, Java, Awk, Perl)6 3554 1 1008 6360 t
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-15-7)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 7 7
%%Page: 8 8
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
8 pagesetup
20 H f
(Suf\256x Arrays to the Rescue)4 2432 1 1988 960 t
(Word array for)2 1280 1 720 1560 t
20 HI f
(k)2056 1560 w
20 S f
(=)2205 1560 w
20 H f
(1 ``of the people, by the people,)6 2796 1 2348 1560 t
(for the people'':)2 1374 1 720 1800 t
20 CW f
(word[0]: by the)2 1800 1 1296 2095 t
(word[1]: for the)2 1920 1 1296 2330 t
(word[2]: of the)2 1800 1 1296 2565 t
(word[3]: people)1 1800 1 1296 2800 t
(word[4]: people, for)2 2400 1 1296 3035 t
(word[5]: people, by)2 2280 1 1296 3270 t
(word[6]: the people,)2 2400 1 1296 3505 t
(word[7]: the people)2 2280 1 1296 3740 t
(word[8]: the people,)2 2400 1 1296 3975 t
20 H f
(The Critical Function)2 1838 1 720 4515 t
20 CW f
(int wordncmp\(char *p, char* q\))4 3600 1 720 4810 t
(n = k)2 600 1 1200 5045 t
(for \( ; *p == *q; p++, q++\))7 3240 1 1200 5280 t
(if \(*p == 0 && --n == 0\))7 2880 1 1680 5515 t
(return 0)1 960 1 2160 5750 t
(return *p - *q)3 1680 1 1200 5985 t
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-15-8)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 8 8
%%Page: 9 9
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
9 pagesetup
20 H f
(Code Sketch, Part 1)3 1798 1 2161 960 t
(Read and Store Training Sample)4 2924 1 720 1560 t
20 CW f
(word[0] = inputchars)2 2400 1 720 1855 t
(while scanf\("%s", word[nword]\) != EOF)4 4440 1 720 2090 t
(word[nword+1] = word[nword] +)3 3480 1 1200 2325 t
(strlen\(word[nword]\) + 1)2 2760 1 3120 2560 t
(nword++)1200 2795 w
(/* put k null characters at end */)7 4080 1 720 3030 t
(for i = [0, k\))4 1680 1 720 3265 t
(word[nword][i] = 0)2 2160 1 1200 3500 t
20 H f
(Print First)1 856 1 720 4040 t
20 HI f
(k)1632 4040 w
20 H f
(Words)1788 4040 w
20 CW f
(for i = [0, k\))4 1680 1 720 4335 t
(print word[i])1 1560 1 1200 4570 t
20 H f
(Sort The Array)2 1304 1 720 5110 t
20 CW f
(qsort\(word, nword, sizeof\(word[0]\), sortcmp\))3 5280 1 720 5405 t
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-15-9)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 610 726
%%EndPage: 9 9
%%Page: 10 10
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
10 pagesetup
20 H f
(Code Sketch, Part 2)3 1798 1 2161 960 t
(Generate Text)1 1284 1 720 1560 t
20 CW f
(phrase = first phrase in input array)6 4320 1 720 1855 t
(loop)720 2090 w
(perform a binary search for phrase)5 4080 1 1200 2325 t
(in word[0..nword-1])1 2280 1 1680 2560 t
(for all phrases equal in k words)6 3840 1 1200 2795 t
(select one at random,)3 2520 1 1680 3030 t
(pointed to by p)3 1800 1 2160 3265 t
(phrase = word following p)4 3000 1 1200 3500 t
(if k-th word of phrase is length 0)7 4080 1 1200 3735 t
(break)1680 3970 w
(print k-th word of phrase)4 3000 1 1200 4205 t
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-15-10)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 10 10
%%Page: 11 11
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
11 pagesetup
20 H f
(Pseudocode for Text Generation)3 2904 1 1608 960 t
20 CW f
(phrase = inputchars)2 2280 1 720 1615 t
(for \(left = 10000; left > 0; left--\))7 4320 1 720 1850 t
(l = -1)2 720 1 1200 2085 t
(u = nword)2 1080 1 1200 2320 t
(while l+1 != u)3 1680 1 1200 2555 t
(m = \(l + u\) / 2)6 1800 1 1680 2790 t
(if wordncmp\(word[m], phrase\) < 0)4 3840 1 1680 3025 t
(l = m)2 600 1 2160 3260 t
(else)1680 3495 w
(u = m)2 600 1 2160 3730 t
(for \(i = 0; wordncmp\(phrase, word[u+i]\))5 4680 1 1200 3965 t
(== 0; i++\))2 1200 1 2640 4200 t
(if rand\(\) % \(i+1\) == 0)5 2640 1 1680 4435 t
(p = word[u+i])2 1560 1 2160 4670 t
(phrase = skip\(p, 1\))3 2280 1 1200 4905 t
(if strlen\(skip\(phrase, k-1\)\) == 0)4 3960 1 1200 5140 t
(break)1680 5375 w
(print skip\(phrase, k-1\))2 2760 1 1200 5610 t
20 H f
(Comparison to Typical Approaches)3 3122 1 720 6150 t
(Similar speed, less space, less code)5 3234 1 1008 6630 t
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-15-11)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 598 726
%%EndPage: 11 11
%%Page: 12 12
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
12 pagesetup
20 H f
(The Complete Code)2 1796 1 2306 960 t
8 CW f
(#include <stdio.h>)1 864 1 1008 1235 t
(#include <stdlib.h>)1 912 1 1008 1330 t
(#include <string.h>)1 912 1 1008 1425 t
(char inputchars[4300000];)1 1200 1 1008 1615 t
(char *word[800000];)1 912 1 1008 1710 t
(int nword = 0;)3 672 1 1008 1805 t
(int k = 2;)3 480 1 1008 1900 t
(int wordncmp\(char *p, char* q\))4 1440 1 1008 2090 t
( n = k;)3 336({ int)1 528 2 1008 2185 t
(for \( ; *p == *q; p++, q++\))7 1296 1 1392 2280 t
(if \(*p == 0 && --n == 0\))7 1152 1 1776 2375 t
(return 0;)1 432 1 2160 2470 t
(return *p - *q;)3 720 1 1392 2565 t
(})1008 2660 w
(int sortcmp\(char **p, char **q\))4 1488 1 1008 2850 t
( wordncmp\(*p, *q\);)2 864({ return)1 672 2 1008 2945 t
(})1008 3040 w
(char *skip\(char *p, int n\))4 1248 1 1008 3230 t
( \( ; n > 0; p++\))6 768({ for)1 528 2 1008 3325 t
(if \(*p == 0\))3 576 1 1776 3420 t
(n--;)2160 3515 w
(return p;)1 432 1 1392 3610 t
(})1008 3705 w
(int main\(\))1 480 1 1008 3895 t
( i, wordsleft = 10000, l, m, u;)7 1488({ int)1 528 2 1008 3990 t
(char *phrase, *p;)2 816 1 1392 4085 t
(word[0] = inputchars;)2 1008 1 1392 4180 t
(while \(scanf\("%s", word[nword]\) != EOF\) {)5 1968 1 1392 4275 t
(word[nword+1] = word[nword] + strlen\(word[nword]\) + 1;)6 2592 1 1776 4370 t
(nword++;)1776 4465 w
(})1392 4560 w
(for \(i = 0; i < k; i++\))7 1104 1 1392 4655 t
(word[nword][i] = 0;)2 912 1 1776 4750 t
(for \(i = 0; i < k; i++\))7 1104 1 1392 4845 t
(printf\("%s0, word[i]\);)1 1056 1 1776 4940 t
(qsort\(word, nword, sizeof\(word[0]\), sortcmp\);)3 2160 1 1392 5035 t
(phrase = inputchars;)2 960 1 1392 5130 t
(for \( ; wordsleft > 0; wordsleft--\) {)7 1776 1 1392 5225 t
(l = -1;)2 336 1 1776 5320 t
(u = nword;)2 480 1 1776 5415 t
(while \(l+1 != u\) {)4 864 1 1776 5510 t
(m = \(l + u\) / 2;)6 768 1 2160 5605 t
(if \(wordncmp\(word[m], phrase\) < 0\))4 1632 1 2160 5700 t
(l = m;)2 288 1 2544 5795 t
(else)2160 5890 w
(u = m;)2 288 1 2544 5985 t
(})1776 6080 w
(for \(i = 0; wordncmp\(phrase, word[u+i]\) == 0; i++\))8 2400 1 1776 6175 t
(if \(rand\(\) % \(i+1\) == 0\))5 1152 1 2160 6270 t
(p = word[u+i];)2 672 1 2544 6365 t
(phrase = skip\(p, 1\);)3 960 1 1776 6460 t
(if \(strlen\(skip\(phrase, k-1\)\) == 0\))4 1680 1 1776 6555 t
(break;)2160 6650 w
(printf\("%s0, skip\(phrase, k-1\)\);)2 1536 1 1776 6745 t
(})1392 6840 w
(return 0;)1 432 1 1392 6935 t
(})1008 7030 w
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-15-12)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 12 12
%%Trailer
DpostDict begin
done
end
%%Pages: 12
%%DocumentFonts: Courier Helvetica Times-Italic Times-Roman Symbol Helvetica-Oblique