shabda
Comments
Reactions

Generating pseudo random text with Markov chains using Python

By : Shabda Raaj

First the definition from Wolfram

A Markov chain is collection of random variables {X_t} (where the index t runs through 0, 1, ...) having the property that, given the present, the future is conditionally independent of the past.

Wikipedia is a little clearer

...Markov chain is a stochastic process with markov property ... [Which means] state changes are probabilistic, and future state depend on current state only.

Markov chains have various uses, but now let's see how it can be used to generate gibberish, which might look legit.

The algorithm is,

  1. Have a text which will serve as the corpus from which we choose the next transitions.
  2. Start with two consecutive words from the text. The last two words constitute the present state.
  3. Generating next word is the markov transition. To generate the next word, look in the corpus, and find which words are present after the given two words. Choose one of them randomly.
  4. Repeat 2, until text of required size is generated.

The code for this is

To see a sample output, we take the text of My man jeeves by Wodehouse from Project Gutenberg, and see a sample output.

In [1]: file_ = open('/home/shabda/jeeves.txt')

In [2]: import markovgen

In [3]: markov = markovgen.Markov(file_)

In [4]: markov.generate_markov_text()
Out[4]: 'Can you put a few years of your twin-brother Alfred,
who was apt to rally round a bit. I should strongly advocate
the blue with milk'

[The files you need to run this are jeeves.txt and markovgen.py]

How is this a markov algorithm?

  • The last two words are the current state.
  • Next word depends on last two words only, or on present state only.
  • The next word is randomly chosen from a statistical model of the corpus.

Here is some sample text.

"The quick brown fox jumps over the brown fox who is slow jumps over the brown fox who is dead."

This gives us a corpus like,

{('The', 'quick'): ['brown'],
 ('brown', 'fox'): ['jumps', 'who', 'who'],
 ('fox', 'jumps'): ['over'],
 ('fox', 'who'): ['is', 'is'],
 ('is', 'slow'): ['jumps'],
 ('jumps', 'over'): ['the', 'the'],
 ('over', 'the'): ['brown', 'brown'],
 ('quick', 'brown'): ['fox'],
 ('slow', 'jumps'): ['over'],
 ('the', 'brown'): ['fox', 'fox'],
 ('who', 'is'): ['slow', 'dead.']}

Now if we start with "brown fox", the next word can be "jumps" or "who". If we choose "jumps", then the current state is "fox jumps" and next word is over, and so on.

Hints

  • The larger text we choose, the more choices are there at each transition, and a better looking text is generated.
  • The state can be set to depend on one word, two words, or any number of words. As the number of words in each state increases, the generated text becomes less random.
  • Don't strip the punctuations etc. They lead to a more representative corpus, and a better random text.

Resources


Did you know that markov chains have many other uses in finance, statistics and mathematics? In fact Google's page rank algorithm is essentially a markov chain of the web! We publish articles on Algorithms, Python, Django and related technologies every week. Why not Subscribe to us or follow us on twitter?


Related Posts


Can we help you build amazing apps? Contact us today.

Topics : seo algorithms

Comments

Oliver Gassner

links for 2009-06-17...

What is a browser?
OMFG (Ich sag ja immer: geht in die Fußgängerzone und FRAGT mal )
(tags: browser *****)

Thoughts on Opera Unite | FactoryCity
Opera Uni...

commmenttor
Paddy3118

You don't seem to use the relative frequenccy of next words to weight the random choice?

- Paddy.

commmenttor
shabda

Paddy: The words are added to the list the number of times they appear. For example, a key might be

('milk', 'honey'):['story', 'book', 'book'],
........

When you do a random.choice, book has twice the probability of story, hence it is frequency weighted.

commmenttor
Paddy3118

Thanks, I missed that!

commmenttor
sonu 22nd July, 2009

Markov chain has been the collection of random variables ,it is also used to generate gibberish ,actually markov chain depends on the present and future.It has the only one who can make a possible word of future.

commmenttor
brian metz 18th Aug., 2009

do you remember a program from waaaaay back called "text mangler"? it used markov chains (i guess), and it was almost creepy how the sentences came out. it was hours of pointless and amazing fun... i haven't been able to get the same results with all the other newer generators... thanks for this - i'm going to get all texty with this tonight!!!!!

commmenttor
lagerkoller's soup

Generating pseudo random text with Markov chains using Python — The Usware Blog - Django Web Development...

...

commmenttor
Sebastian Paaske Tørholm

For fun, here's a Markov-chain-based word generator to make words that have a realistic structure, based on existing words.

http://gist.github.com/360212

Usage is pretty much the same.

commmenttor
Michael T 24th Nov., 2011

Real Good description and clear examples.
Big help in understanding.
Thanks

commmenttor
Daniel Ellis 7th Aug., 2013

I did a quick modification that lets you specify chain size. Changing the chain size to 4 makes the text less random, but also makes it seem like less gibberish. It looks like it tends to make the 25 words come from 2 or 3 separate sentences:

https://gist.github.com/dellis23/6174914

commmenttor
Brendan

When I run the code I get an error:
::import markovgen

ImportError Traceback (most recent call last)
in ()
----> 1 import markovgen

ImportError: No module named markovgen

I have the code in Ipython. would that cause the problem?

commmenttor
Air Jordan 2011 Q Flight Zoom Making Use of Shock Absorption Round The Palm

Generating pseudo random text with Markov chains using Python - Agiliq Blog | Django web app development

commmenttor
nike air max pas cher pour homme

Donc, je n'ai pas d'opinion ou insatisfaction ciseaux hommes sortent. De même, à moins que l'auteur peut vraiment remuer mes émotions, sinon je sympathise souvent avec le meurtrier (beaucoup de romans policiers, les individus de destruction sont si fort, vigoureux effort doit être calculée pour différents réglages accidentels coïncidences écrivain, afin qu'ils puissent accomplir la tâche, même J'ai essentiellement échappé meurtrier admirer) 93 points: la disparition de personnes (Deaver): réalisme contemporain rare crime impossible, qui divers chambre, Yi Rongshu, un angle double, échappé chirurgie après l'autre, et Di et Ep plupart des oeuvres, point culminant, la plus cruciale, deux truc de base est un type rare de réalisme (pourrait tout aussi bien vous dire que l'une de l'astuce narrative mais oh).

commmenttor
new style nike broncos authentic eric decker blue white red elite limited at the official site

To Those People Who Wish To grasp nfl jersey But Aren't able to Get Going
new style nike broncos authentic eric decker blue white red elite limited at the official site http://www.akumaneko.com/abouts/make-a-football-jersey-online/vintage-nhl-jersey/enkumvxb-p-890.html

commmenttor
luxury mike wallace navy white gold jersey nike throwback dolphins elite wall to wall values

That explains why just about everything you have found out about nfl jersey is undoubtedly wrong and what you should realize.
luxury mike wallace navy white gold jersey nike throwback dolphins elite wall to wall values http://www.animalhospitalofpolaris.com/css/major-league-baseball-jersey/authentic-phillies-jersey/mike-wallace-navy-white-gold-jersey-nike-throwback-dolphins-elite-p-713.html

commmenttor
cheap quality lavonte david blue red white jersey throwback buccaneers elite limited sale cheap

Rumours of which nfl jersey drafts to a end, this is the follow-up
cheap quality lavonte david blue red white jersey throwback buccaneers elite limited sale cheap http://www.rittenhouseacupuncture.com/products/2013-nfl-nike-jerseys-raiders/pelzelmv-p-320.html

commmenttor
the great rebate authentic justin blackmon womens mens youth jersey nike elite limited for sale

Finish your meal and take a rest As you are Getting to know the Secrets to nfl jersey
the great rebate authentic justin blackmon womens mens youth jersey nike elite limited for sale http://www.cottenhamsawmills.com/Styles/colorado-rockies-nhl-jersey/team-jerseys-for-basketball/szptngxy-p-529.html

commmenttor
discover our latest collection of chris long jersey

This specific nfl jersey is actually truly terrific, it's lots of functions and features.
discover our latest collection of chris long jersey http://www.ebangkok.org/abouts/russell-football-jerseys/customize-a-jersey-online/womkeouq-p-710.html

commmenttor
cheap new style geno smith red white gold jersey nike throwback jets elite retail

To Opportunity Seekers Who Wishes To understand nfl jersey But Aren't able to Get Rolling
cheap new style geno smith red white gold jersey nike throwback jets elite retail http://www.louisfusco.com/css/cotton-button-baseball-jerseys/nfl-sport-jerseys/atkkkgty-p-418.html

commmenttor
the great rebate geno smith jersey nike jets authentic geno smith red black white online store

To Folks Who Would Like To grasp nfl jersey But Struggles to Get Started
the great rebate geno smith jersey nike jets authentic geno smith red black white online store http://www.dvmlabs.com/products/russian-ice-hockey-jerseys/cheap-practice-football-jerseys/nvtoicnm-p-911.html

commmenttor
cheap quality arian foster green navy white jersey throwback texans elite limited sale outlet store

To People Who Want To master nfl jersey But Aren't able to Get Started
cheap quality arian foster green navy white jersey throwback texans elite limited sale outlet store http://www.canadiancollectibles.ca/compics/nfl-and-nba-jerseys/yggmtqfv-p-508.html

commmenttor
hot sale redskins robert griffin iii navy red white jersey nike womens mens on sale online

Everything you don't know about nfl jersey could be costing even more than one thinks.
hot sale redskins robert griffin iii navy red white jersey nike womens mens on sale online http://www.studiohiggins.com/html/wholesale-vintage-nhl-jerseys/compare-lsu-football-jerseys/vtnwgngg-p-663.html

commmenttor
find great prices nike aldon smith womens jersey 49ers red black white authentic 2014 sale outlet

Precisely why all things you've heard of nfl jersey is undoubtedly drastically wrong and what you should be aware of.
find great prices nike aldon smith womens jersey 49ers red black white authentic 2014 sale outlet http://www.mountgambiertourism.com.au/files/cheap-hockey-jerseys-for-sale/nhl-football-jerseys-customized/uxugssap-p-735.html

commmenttor
buy authentic andy dalton navy blue white jersey throwback bengals elite limited sale outlet store

nfl jersey News Pipes Get Your Tweets Automatically
buy authentic andy dalton navy blue white jersey throwback bengals elite limited sale outlet store http://pollackphoto.com/canada/olympic-hockey-jerseys-stores/team-usa-soccer-jersey/zvdslqbu-p-950.html

commmenttor
shop discount cheap nike dqwell jackson blue white jersey browns pro shop fill you cart with savings

Here's A Quick Way In order to Get nfl jersey Skills
shop discount cheap nike dqwell jackson blue white jersey browns pro shop fill you cart with savings http://www.cash4giftcards.com/eby/football-jerseys-49ers/locngzxo-p-579.html

commmenttor
free run 3 youtube

ugg boots sale for men ugg adirondack boot ii on sale air max wright canada chaussures nike air jordan 1 retro high nike air max black leopard kopen air jordan flight 45 trk electric lime uggs size 11 womens shoes air max new 2013 air jordan kilroy flight club spike lee unveils new jordan spizike knicks pes air max 90 gs freizeitschuh junior pink ugg boots size 7 ugg noira womens boots size 10 uggs classic short size 4 ugg classic short boots 5825 navy blue clearance air max 2011 italia ugg kids cardy 5649 crochet uggs paisley uggs clearance outlet ugg patchwork boots kids girls
free run 3 youtube http://linehanconsulting.com/ssfm/index.asp?keyword=free-run-3-youtube&id;=3335

commmenttor
65% discount burberry mini orchard in grainy leather black on sale

As to why everyone seems to be absolute wrong over BUBERRY and as a consequence reasons why you really should check this analysis.
65% discount burberry mini orchard in grainy leather black on sale http://www.iaom-mea.com/css/burberry-ties-outlet/burberry-premium-outlet/burberry-mini-orchard-in-grainy-leather-black-p-5037.html

commmenttor
cheap nike Air Jordan 6 17 Retro shoes

uggs for men kissing men passionately ugg slippers uk john lewis nike air jordan games online uggs for kids 0 9 calm syrup air jordan ix ad ugg style boots cheap ugg dakota usa ugg classic mini deco boot ugg boots canada women's dakota black mens byron moccasin ugg slippers ugg bailey button boots black ugg rain boots for kids girls ugg for men online womens leather ugg boots for women nike air max x liberty air max one zwart uggs outlet 4 usa boots like uggs for kids ugg kids kensington size 4 ugg essential tall black
cheap nike Air Jordan 6 17 Retro shoes http://www.bowenarchitecture.com/?keyword=cheap-nike-Air-Jordan-6-17-Retro-shoes&id;=832

commmenttor
replica hermes dogon wallet

replica hermes dogon wallet hermes birkin real or fake logo lvastcddifw

commmenttor
luxury golden tate game jersey: seahawks womens youth navy orange white say no to high prices

Regularly nfl jersey Wrap up is beginning to really feel kind of old
luxury golden tate game jersey: seahawks womens youth navy orange white say no to high prices http://www.hcdubai.com/discount/sports-jerseys-bourn-trade/2013-cheap-football-jerseys/olhzisbi-p-2.html

commmenttor
cheap authentic moncler women jackets outlet your best choice for value

MONCLER-girlfriend has tested out this new algorithm formula . . make a king's ransom from day 1
cheap authentic moncler women jackets outlet your best choice for value http://www.jstephenrhodes.com/css/moncler-women-jackets-outlet/

commmenttor
wholesale buccaneers darrelle revis red black white jersey nike womens mens wholesale

Sick of every nfl jersey trends? We're at this site for your needs!
wholesale buccaneers darrelle revis red black white jersey nike womens mens wholesale http://www.dhabaindianbistro.com/images/online-jersey-shop/bdlnkmsd-p-284.html

commmenttor
where to purchase burberry house check holdall 52371 coffee outlet york

Innovative guide disclose the low down towards BUBERRY and the reasons you will need to take action as we speak.
where to purchase burberry house check holdall 52371 coffee outlet york http://www.frocksandfrillsboutique.com/products/men-burberry-sale/fuhvsgrq-p-161.html

commmenttor
hot days, cool prices nike panthers authentic cam newton navy orange white elite limited online

Who else must I tweet? nfl jersey enthusiasts on the subject of Twitting
hot days, cool prices nike panthers authentic cam newton navy orange white elite limited online http://www.broadswaycats.com/products/team-russia-hockey-jersey/super-bowl-nfl-jerseys-49ers/teaesplg-p-250.html

commmenttor
professional gucci 2012 sneakers in canvas in black g415 cheap sale

Modernize a gucci within about half the time without having to spend more cash!
professional gucci 2012 sneakers in canvas in black g415 cheap sale http://www.mts-braille.com/blog/authentic-gucci-purse/gucci-2012-sneakers-in-canvas-in-black-g415-p-5268.html

commmenttor
buy newest cheap rob gronkowski womens mens youth jersey authentic elite limited game wholesale

What Every single person Should Know Concerning nfl jersey
buy newest cheap rob gronkowski womens mens youth jersey authentic elite limited game wholesale http://www.spearheadexecutivecoaching.com/photos/nhl-jerseys-wholesale-supplier-canada/elyssymn-p-822.html

commmenttor
great values authentic lamarr houston jersey womens mens youth black white gold no taxes

The 5 very closely-guarded nfl jersey tactics simplified in precise detail.
great values authentic lamarr houston jersey womens mens youth black white gold no taxes http://www.asia-bolt.com/abouts/2013-nike-nfl-jerseys-patriots/oslymfyo-p-763.html

commmenttor
dividend days nike roddy white womens jersey falcons purple black white authentic up to 78% off

The thing that Folks Should Know Concerning The nfl jersey Market
dividend days nike roddy white womens jersey falcons purple black white authentic up to 78% off http://bigdoggalleries.com/artists/dayton-flyers-basketball-jersey/woqfgtip-p-757.html

commmenttor
find nike antonio gates womens jersey chargers red orange white authentic outlet shop

This is why noone is preaching about nfl jersey and therefore the thing one ought to complete right away.
find nike antonio gates womens jersey chargers red orange white authentic outlet shop http://www.bonanza-tours.com/css/cheap-sport-jersey/monaco-soccer-jerseys/nike-antonio-gates-womens-jersey-chargers-red-orange-white-authentic-p-6584.html

commmenttor
tommy hilfiger tilbud

Som nævnt i min tidligere debat artiklen "5 Elements til god ledelse" der er stadig en masse variabler, du som leder har til at styre, hvis du ønsker at opbygge nye kvalificerede forretningsmæssige kompetencer og styrke dine nuværende færdigheder, du har brug for at uddanne dig selv. At være en top niveau performer som leder i din virksomhed, skal du to.Another genstand for en vellykket ledelse er, hvordan du kan styre "Learning". Hvis du laver den fejl, og tror du ved alt, og at du har svaret på alt, du er forkert. Hvis du ønsker at være en succesfuld leder, kan du altid lære. Succesfulde ledere aldrig op med at lære. Lær af dine medarbejdere, lære gennem uddannelse, holde et åbent sind og udforske det ukendte. Det vil være en god idé at opsætte nogle læringsmål fra måned til måned eller so.One af de ting, jeg ting er meget vigtigt i mastering succesfuld ledelse er at få og have "Influence". I løbet af arbejdsdagen, vil dit lederskab påvirke folk omkring dig, og du vil blive påvirket af dem. Ved at have en vision, kan du tilløb dit team i den rigtige retning, du beslutter dig. Tænk over din vision og den måde du påvirker andre. En velkendt udtryk er Management ved at gå rundt. "Du kan ikke gøre alt ved dig selv. Når" bemyndige "dit team eller organisation, vil du erkende, at det er en meget mere kraftfuld organisation, du har. Som en god leder er det nødvendigt at bemyndige dit team uanset holdet medlems kvalifikationer. Vær opmærksom and dine kolleger behov, og husk at sætte pris på deres arbejde ved at fortælle dem.? Når dit hold vokser, vil du vokse som en leader.A god leder er "betroet" af deres ansatte . Medarbejderne ønsker at være blyholdig, uddannet og følge dig, hvis vide, at de kan regne og stoler på dig og din dømmekraft. Husk at gøre, hvad du siger, og være ærlige om, hvad der foregår i op s og ned er.? Når du kan bevise medarbejderne kan regne med dit arbejde, vil du få deres respekt og modtage troværdighed. Kig på dig selv og spørge, om du er i balance, og opholder sig tro mod din team.Emotional intelligens og autenticitet er meget vigtige faktorer i god ledelse. De har at vise, at du holder om teamet ved opmuntre dem. Ved at vise dette, vil du kører dit team frem i vanskelige og komplekse situationer. Genkend og fejre resultater og milepæle! Husk at kommunikere med andre fra dit hjerte! Foster samfund inden dit team!

commmenttor
scarpe hogan rebel donna prezzi

Dans les cinq jours qui ont suivi, il ne revient pas 脿 l'茅quipe.

commmenttor
cheap nfl jerseys

En France, le Parti pirate présentera des listes dans six des huit cheap nfl jerseyscirconscriptions, avec pas moins de 30 candidats en Île-de-France et pour les Français à l'étranger. En plus de ça, le mouvement sera présent dans une quinzaine d'autres pays européens.

commmenttor
best quality nike broncos authentic eric decker navy red white elite limited outlet shop

nfl jersey brings new lifespan into an old dilemma. . . golden classic
best quality nike broncos authentic eric decker navy red white elite limited outlet shop http://www.airmartechnology.com/catimages/soccer-goalkeeping-jerseys/authentic-nike-soccer-jerseys/fvoetwsq-p-82.html

commmenttor
cheap quality cheap nike julius peppers red black white jersey bears pro shop clearance sale

Those things Every single person Ought To Know With Regards To nfl jersey Marketing
cheap quality cheap nike julius peppers red black white jersey bears pro shop clearance sale http://www.davemcnallyart.com/products/mlb-jerseys-shop-online/cheap-nike-julius-peppers-red-black-white-jersey-bears-pro-shop-p-8792.html

commmenttor
jordan retro 10 for sale

Nice post. I learn something alot more challenging on different blogs everyday. It'll continually be stimulating to read content from other writers and practice a bit some thing from their store. I'd prefer to use some using the content on my blog regardless of whether you don't mind. Natually I'll give you a link on your web weblog. Thanks for sharing.
jordan retro 10 for sale http://coachstresszero.com/Images/_notes/sys.asp?key=jordan-retro-10-for-sale-119

commmenttor
the best ugg lauri 1000403 red sandals for sale

The Primary Solutions To Learn about ugg And Ways You Can Become a part of The ugg Top dogs
the best ugg lauri 1000403 red sandals for sale http://www.hvcs.hu/images/ugg-boots-sale-men/ugg-lauri-1000403-red-sandals-p-582.html

commmenttor
cheap price coach poppy in sequin signature medium gold totes ady discount price and high quality!

Small business News - babyliss Understood to be A Necessity In these modern times
cheap price coach poppy in sequin signature medium gold totes ady discount price and high quality! http://thybony.com/wordpress/coach-factory-online-shopping/coach-poppy-in-sequin-signature-medium-gold-totes-ady-p-8675.html

commmenttor

Reactions

aduric

NLTK has a pretty good text generation library. It generates text based on any corpus you give it.

This comment was originally posted on Reddit

jcsalterego

Not ground-breaking by any means, but a nice, concrete application of Markov chains.

This comment was originally posted on Hacker News

davidw

This is relevant, if you want to do something fancier:http://megahal.alioth.debian.org/How.html

BTW, has anything better than Megahal turned up in the meantime, that is also open source?

This comment was originally posted on Hacker News

davidw

This is relevant, if you wan to do something fancier:http://megahal.alioth.debian.org/How.html

BTW, has anything better than Megahal turned up in the meantime, that is also open source?

This comment was originally posted on Hacker News

Dylan Richard

Markov chains can be hilarious.

This comment was originally posted on FriendFeed

Caligula

This is a big reason why speech recognition works. You have a list of probabilities of sequence of words occuring(language model) and it decides on the next word based on the last few previous words.So if you have the word Super, odds are the next word is Man and not Microphone.

This comment was originally posted on Hacker News

alxv

In "The Practice of Programming", Brian Kernighan and Rob Pike use the Markov Chain Algorithm to illustrate a number of lessons about software design and implementation. I used it as my "Hello world" program when learning a new programming language.In Python, the implementation is surprisingly succinct:

import sys import random import collections MAXGEN = 10000 NONWORD = "" suffixchain = collections.defaultdict(list) w1 = w2 = NONWORD for line in sys.stdin: for word in line.split(): suffixchain[(w1, w2)].append(word) w1, w2 = w2, word suffixchain[(w1, w2)].append(NONWORD) w1 = w2 = NONWORD for i in range(MAXGEN): suffixes = suffixchain[(w1, w2)] next = random.choice(suffixes) if next is NONWORD: break print next, w1, w2 = w2, nextTo use it, just run: $ python markov.py < english_corpus.txt

This comment was originally posted on Hacker News

SuperMicrophone

I resent that.

This comment was originally posted on Hacker News

DarkXanthos

This should be called how to use a library in Python. Pretty weak IMO.

This comment was originally posted on Reddit

DarkXanthos

Here’s one I wrote that actually shows how they’re coded: http://justinbozonier.posterous.com/markov-chains-in-python

This comment was originally posted on Reddit

fas2

I once was given homework by the information theory lecture to implement such a random text generator (k-th order markov chain, k configurable). As I just started with python I thought it would be fun to do that in a one liner. It happened, though it was a really long line and a total lambda mess.

This comment was originally posted on Reddit

© Agiliq, 2009-2012