Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fast Markov chains in ~20 lines of sh, grep, cut and Awk

0x0f0f0f.github.io

Post reply on HN
Print view View original

11–20 of 42 posts

Re: Fast Markov chains in ~20 lines of sh, grep, cut and Awk

#11

Post by make3 »

jstanley wrote: post #9
make3 wrote: post #7

Earlier quoted context omitted.

In his dataset, all sentences start at the beginning of the line and end at it's end. This is strictly a toy, no one serious would use this for anything anyways.

> In his dataset, all sentences start at the beginning of the line and end at it's end. Right, but the sentence start is taken from the first word of a random state transition pair, not the first word of a random sentence.

The first random state should be picked with start probability, which are equal to the frequency of a word beginning a sentence, which is exactly equal to picking the first word of a random sentence

Re: Fast Markov chains in ~20 lines of sh, grep, cut and Awk

#13

Post by dredmorbius »

jstanley wrote: post #3

> At first, mrkwords.sh will pick a random line from the model and pick the first word of the pair as the first word of our output message. In my opinion, this is not the best way to do it. This will generate sentences that start with words that can never start sentences. The best thing to do is to define a "sentinel" to go at the start and end of a sentence. For example, a "$" sign, or a NUL byte. Then to generate a…

'^' and '$' are already the regex convention for start and end of string. With a corpus already broken into sentences, this would be readily applied.

Re: Fast Markov chains in ~20 lines of sh, grep, cut and Awk

#14

Post by dredmorbius »

korpiq wrote: post #6
beefhash wrote: post #5

Earlier quoted context omitted.

> The best thing to do is to define a "sentinel" to go at the start and end of a sentence. For example, a "$" sign, or a NUL byte. The $ sign would get in the way if people actually use it in conersation, and maybe other things don't like the NUL byte. Maybe '\x1F' (ASCII Unit Separator) or '\x1E' (ASCII Record Separator) are better candidates?

Or just upper case first letter and full stop?

Because, as Mr. Obvious notes, capitalisation and stops never appear elsewhere in sentences, etc., etc.

Re: Fast Markov chains in ~20 lines of sh, grep, cut and Awk

#16

Post by jnellis »

The best read for something like this is The Practice of Programming which is a great little book to have in general. This link to a sample chapter covers the entire analysis and creation of a markov chain program, none of which require many lines of code.

https://ptgmedia.pearsoncmg.com/images/9780201615869/samplep...

One thing I've noticed from playing with these types of programs is the number of words to use as a hash. Two to start with of course, will quickly reproduce the sample text once you get to only five or six prefix words. Where as two prefix words usually generate nonsense, the sweet spot to a believable quality is only three or four words as a prefix with five or more reproducing the original text. The larger the varied sample text, the much better the results. Furthermore, only breaking words on whitespace creates even better quality output than assuming you need to tinker with the punctuation.

Re: Fast Markov chains in ~20 lines of sh, grep, cut and Awk

#17

Post by ngrammaton »

jnellis wrote: post #16

The best read for something like this is The Practice of Programming which is a great little book to have in general. This link to a sample chapter covers the entire analysis and creation of a markov chain program, none of which require many lines of code. https://ptgmedia.pearsoncmg.com/images/9780201615869/samplep... One thing I've noticed from playing with these types of programs is the number of words to use as a…

The question of how many words are used is discussed here: https://en.wikipedia.org/wiki/N-gram#n-gram_models

See also https://en.wikipedia.org/wiki/Google_Ngram_Viewer which recently popularized the term n-gram.

Re: Fast Markov chains in ~20 lines of sh, grep, cut and Awk

#20

Post by m31415 »

mkoryak wrote: post #19

This is awesome because it is a real shell script that does something interesting AND it's well documented. I'm bookmarking this as a bash script reference.

Not being pedantic, but OP's script isn't Bash, it's POSIX sh. POSIX sh can be executed in Bash, but there are several differences. The only non-POSIX command I can spot in that script is shuf.
Post reply on HN