Read about Markov chains:

* Claude Shannon's 1948 MS thesis, "A Mathematical Theory of Communication" (https://onlinelibrary.wiley.com/doi/abs/10.1002/j.1538-7305.1948.tb01338.x)

* https://en.wikipedia.org/wiki/Markov_chain

* Chapter 3 of _The Practice of Programming_ by Brian Kernighan and Rob Pike where they discuss implementations in C, C++, Java, awk, and Perl

* "Computer Recreations", A. K. Dewdney, Scientific American, 1989 (https://archive.org/details/ComputerRecreationsMarkovChainer)

I'd like you to consider how a Markov chain creates a graph structure. Consult the three PDFs (generated by the `mk-graphs.sh` program) that visualize the graphs created by k-mer sizes of 1, 2, 3, and 4 when given this input:

Notice that sometimes the branches terminate and sometimes you can find multiple paths through the graphs. As `k` grows, there are fewer options.

import argparse

import os

import re

import sys

from collections import defaultdict

from graphviz import Digraph

def get_args():

"""Get command-line arguments"""

parser = argparse.ArgumentParser(

description='Markov chain for characters/words',

formatter_class=argparse.ArgumentDefaultsHelpFormatter)

parser.add_argument('file',

metavar='FILE',

nargs='+',

help='Training file(s)')

parser.add_argument('-k',

'--kmer_size',

help='Kmer size',

metavar='int',

type=int,

default=2)

parser.add_argument('-o',

'--outfile',

help='Output file',

metavar='str',

type=str,

default='out.gv')

return parser.parse_args()

def main():

"""Make a jazz noise here"""

args = get_args()

k = args.kmer_size

chains = defaultdict(list)

for file in args.file:

for line in open(file):

for word in line.lower().split():

word = re.sub('[^a-z]', '', word)

for i in range(0, len(word) - k):

kmer = word[i:i + k + 1]

chains[kmer[:-1]].append(kmer[-1])

dot = Digraph(comment='Paths for K={}'.format(k))

edges = set()

for kmer in chains:

dot.node(kmer)

for char in chains[kmer]:

edges.add((kmer, kmer[1:] + char))

dot.edges(edges)

dot.render(args.outfile, view=True)

if __name__ == '__main__':

main()

PRG="./graph.py"

INPUT="words.txt"

for K in 1 2 3 4; do

$PRG -k $K -o "$K-out.gv" "$INPUT"

echo "Done."

maamselle

mabi

mabolo

mac

macaasim

macabre