Markov-Chain Algorithm In PerlMarkov-Chain AlgorithmAlgorithm in Perl, pt.1:Explanation of code, pt. 1:Explanation of code, pt. 2:Explanation of code, pt. 3:Example of $statetab:Algorithm in Perl , pt.2:Explanation of code, pt. 4:Explanation of code, pt. 5:Explanation of code, pt. 6:Example of output, pt. 1:Slide 13Example of output, pt. 2Now is the time for all good questions…Robert Brown – 10/21/09Sting-rewriting system:◦Uses input to write “random” output◦Grammar rules from input helps write outputAn 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 statewhile (<>) { # read each line of inputforeach (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 datawhile (<>) {foreach (split) {...}}push(@{$statetable{$w1}{$w2}}, $NONWORD);while (<>) reads in the current line of inputforeach (split) splits the input line into each individual wordforeach() then runs internal code on each word of inputwhile (<>) runs foreach() for every line of inputpush() explained in next slide# internal code of foreach(split)push(@{$statetab{$w1}{$w2}}, $_);($w1, $w2) = ($w2, $_);*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*◦$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 createdReassign $w1 and $w2◦$w1 = $w2◦$w2 = wordText 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 elemsexit if (($t = $suf->[$r]) eq $NONWORD);print “$t\n”;($w1, $w2) = ($w2, $t); # advance chain}# output data$w1 = $w2 = $NONWORD;for ($i = 0; $i < $MAXGEN; $i++){…}Start at beginning of table◦$w1 and $w2 becomes ‘\n’◦$statetab{\n}{\n} is first item in input◦$statetab{\n}{first item} is second item in inputLoop 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 $sufexit() – Terminate loop◦$suf->[$r] is the ith item in array $suf◦Only terminates if $suf->[$r] = ‘\n’# internal data of for(), pt. 2print “$t\n”;($w1, $w2) = ($w2, $t);Print the value contained in $t◦$t defined in previous expression◦Only occurs if loop was not terminatedReassign $w1 and $w2◦$w1 = $w2◦$w2 = $suf->[$r]◦Update allows the function to assess new valuesInput: “Now is the time for all good people”Output: Now NOTE: When there are nois arrays in $statetab, the then the output mimicstime the input word forfor wordallgoodpeopleInput: “Now is the time for all good people”Output: Now NOTE: When there are nois arrays in $statetab, the then the output mimicstime the input word forfor wordallgoodpeopleInput: “Show your flowcharts and conceal your tables and I will be mystified. Show your tables and your flowcharts will be obvious.”Output: Show NOTE: With a large enough input,your text may not end with last[flowcharts, tables] three words[and, will]… etc
View Full Document
Unlocking...