For learning purposes, I'm trying to implement a Markov Chain from scratch in Python.
The goal is, provided a file with a list of words, and some sequence, to predict the next letter according the the probability computed from the list of words.
My questions are not related to the Python syntax (for instance I know that I can do better than defaultdict
with Counter
at some places but I don't care about that), rather to the Markov Chain algorithm in itself, and in particular:
- is it a correct/efficient way to implement a MC?
- if not, how could this algorithm be more efficient?
- is the method of inserting
state_length - 1
blanks before each word a good practice to allow searching sequences smaller thanstate_length
? - is the way of representing
<EXIT>
a good practice?
The file mdp_sequences.txt
goes like this:
HELLO
CELLO
HELL
HELLO
HELL
SHELL
YELLOW
HELLO
YELLOW
...
1. Parsing
The first part of the program reads the file and computes a count of all words:
from collections import Counter, defaultdict
from pprint import pprint
states = []
state_length = 4
# read and parse csv file into a counted dict of sequences
sequences = defaultdict(int)
with open('mdp_sequences.txt') as f:
for sequence in f:
seq = " " * (state_length - 1) + sequence.rstrip()
sequences[seq] += 1
The resulting sequences
dict is just a count of all words found in mdp_sequences.txt
, with the particularity that is has state_length - 1
spaces inserted before each word:
sequences = {
' HELLO': 342,
' CELLO': 117,
' HELL': 200,
' SHELL': 120,
' YELLOW': 250,
...
}
2. Enumerating states
Next we enumerate each possible state:
for seq, count in sequences.items():
for i in range(len(seq) - state_length + 1):
for j in range(int(count)):
states.append(seq[i:][:state_length])
counted_states = dict(Counter(states))
At this point, the counted_states
dict goes like:
counted_states = {
' H': 542,
' HE': 542,
' HEL': 542,
'HELL': 662,
' C': 117,
' CE': 117,
' CEL': 117,
'CELL': 117,
'ELLO': 709,
...
}
3. Building the Markov Chain
Now we build the Markov Chain itself:
mc = defaultdict(lambda: defaultdict(float))
for state, scount in counted_states.items():
for seq, wcount in sequences.items():
if state in seq:
for i in range(len(seq) - state_length + 1):
if seq[i:][:state_length] == state:
next_step = seq[i+state_length:][:1]
if next_step == '':
next_state = '<EXIT>'
else:
next_state = seq[i+1:][:state_length]
probability = float(wcount) / float(scount)
mc[state][next_state] += probability
The mc
dict is a mapping of each state to its possible following states,
with the probability for each possible following state:
mc = {
' H': {
' HE': 1.0
},
' HE': {
' HEL': 1.0
},
' HEL': {
'HELL': 1.0
},
'HELL': {
'ELLO': 0.5167,
'<EXIT>': 0.4833
},
'ELLO': {
'LLOW': 0.3526,
'<EXIT>': 0.6474
},
'LLOW': {
'<EXIT>': 1.0
},
...
}
4. Testing
Finally, we ask the user for a particular sequence, and list the most probable following states based on this sequence, considering only state_length - 1
:
user_input = input("Enter the current sequence: ")
user_input = " " * (state_length - 1) + user_input
lookup = user_input[-4:]
print("Considering the following sequence: '{}'".format(lookup))
print("Most probable next states are:")
for k, v in sorted(mc[lookup].items(), key=lambda x: x[1], reverse=True):
if k == '<EXIT>':
print(' <EXIT> - p: {}'.format(round(v, 3)))
else:
print(' {} (next step: {}) - p: {}'.format(k, k[-1:], round(v, 3)))
A this point, if the user inputs a sequence with length > state_length
,
we only consider state_length
last letters,
for instance if the user inputs "NUTSHELL" with state_length = 4
,
we consider "HELL"
If the user inputs a sequence with length < state_length
,
we insert spaces before to match state_length
,
for instance if the user inputs "HE" with state_length = 4
,
we consider " HE"
Full example with "NUTSHELL" and state_length = 4
:
- consider only "HELL"
- lookup for
mc["HELL"]
Output for this example is:
"ELLO" (next step: O) - p: 0.517
<EXIT> - p: 0.483
Full example with "H" and state_length = 4
:
- consider only " H"
- lookup for
mc[" H"]
Output for this example is:
" HE" (next step: E) - p: 1.0