Robert Brown 10 21 09 Sting rewriting system Uses input to write random output Grammar rules from input helps write output An example in Pseudo Code Set w1 and w2 to the first two strings in the text loop w3 is the result of markov w1 w2 w1 w2 w2 w3 Repeat loop markov pl markov chain algorithm for 2 word prefixes part 1 take input and create data relationship table MAXGEN 10000 NONWORD n w1 w2 NONWORD initial state while read each line of input foreach split push statetab w1 w2 w1 w2 w2 multiple assignment push statetable w1 w2 NONWORD add tail constants and variables MAXGEN 10000 NONWORD n w1 w2 NONWORD MAXGEN Maximum number of times function is called constant NONWORD Used at the beginning of loops and acts as terminating condition constant w1 w2 are static variables used through loops Initially defined as NONWORD read in data while foreach split push statetable w1 w2 NONWORD while reads in the current line of input foreach split splits the input line into each individual word foreach then runs internal code on each word of input while runs foreach for every line of input push explained in next slide internal code of foreach split push statetab w1 w2 w1 w2 w2 w1 and w2 are used as index for stored value statetab w1 w2 is equal an array can contain multiple entries During first execution statetab is created In previous slide push statetable w1 w2 NONWORD inserts NONWORD as the last item in the statetab This is used as a terminating condition in part 2 push inserts word from foreach into statetab Reassign w1 and w2 w1 w2 w2 word Text used Show your flowcharts and conceal your tables and I will be mystified Show your tables and your flowcharts will be obvious statetab n n Show statetab n Show your statetab Show your flowcharts tables statetab your flowcharts and will statetab flowcharts and conceal statetab flowcharts will be etc statetab be obvious n Terminating condition part 2 create output from data table created in part 1 w1 w2 NONWORD for i 0 i MAXGEN i suf statetable w1 w2 array reference r int rand suf suf is number of elems exit if t suf r eq NONWORD print t n w1 w2 w2 t advance chain Start at beginning of output data table w1 w2 NONWORD for i 0 i MAXGEN i w1 and w2 becomes n statetab n n is first item in input statetab n first item is second item in input Loop the output at most MAXGEN times Loop may exit early if terminating condition is met see next slide internal data of for pt 1 suf statetable w1 w2 r int rand suf exit if t suf r eq NONWORD suf reference to statetable w1 w2 If only one word suf is the word If an array suf is the entire array r random index of suf 1 word always 1 Array between 1 and size of suf exit Terminate loop suf r is the ith item in array suf Only terminates if suf r n internal data of for pt 2 print t n w1 w2 w2 t Print the value contained in t t defined in previous expression Only occurs if loop was not terminated Reassign w1 and w2 w1 w2 w2 suf r Update allows the function to assess new values Input Now is the time for all good people Output Now is the mimics time for all good people NOTE When there are no arrays in statetab then the output the input word for word Input Now is the time for all good people Output Now is the mimics time for all good people NOTE When there are no arrays in statetab then the output the input word for word Input Show your flowcharts and conceal your tables and I will be mystified Show your tables and your flowcharts will be obvious Output Show your flowcharts tables and will etc will be obvious NOTE With a large enough input text may not end with last three words
View Full Document
Unlocking...