<jupyter_start><jupyter_text>Markov Chain[Markov Chain](https://en.wikipedia.org/wiki/Markov_chain) is a model that describe a sequence of event within a system. Normally, in real life, current event is higly influenced by what had occured in the past.  However, markov chain is simple. The occurence of current event depends on only the previous event.```Pr( Xn+1 = x | X1 = x1, X2 = x2, …, Xn = xn) = Pr( Xn+1 = x | Xn = xn)```  Text Generation Using Markov ChainHere, we are considering the **event** of text generation and that event is described by the occurences of words/tokens in the text itself. So, a sequence of words give rise to next words.  **For example**  I am -> I am a programmer  I am -> I am nostalgic  The occurence of next word in the sequence solely depends on the probability. So, the process is vaguely as:- get textual data- preprocess text- count occurence of pairs {for example count of (i, am), (i, love), ...}- create probabilities of occurence of next word given current word (this is done by the count value in above step)- for new sequence of words, go on computing probabilities and get next probable word  Load Data<jupyter_code>tweetcsv = "data/tweets/clean.csv"
df = pd.read_csv(tweetcsv)
df['created_at'] = pd.to_datetime(df['created_at'])
df.head()
# check nulls
df.isnull().sum(), df.shape
df = df.dropna()
# check nulls
df.isnull().sum(), df.shape<jupyter_output><empty_output><jupyter_text>Sort by Time (earliest to latest)<jupyter_code>df = df.sort_values(by='created_at')
df.head()<jupyter_output><empty_output><jupyter_text>Load Text<jupyter_code>text = "\n".join(df['text'].values.tolist()).strip()
text[:100]
# We have already done preprocessing.
# clean.csv is already a cleaned data<jupyter_output><empty_output><jupyter_text>Create PairsCreat word pairs like (w1, w2), (w1, w3), (w4, w9),....<jupyter_code>def create_pairs(text):
    tokens = text.split()
    return list(zip(tokens, tokens[1:]))
pairs = create_pairs(text)
pairs[:5]<jupyter_output><empty_output><jupyter_text>Trie Data StructureTrie is an efficient data structure created from hashmap/dictionary where each node points to the next node until we reach some kind of leaf. In our case, leaf means the numerical value for word pairs.So, we keep on traversing the trie until hitting a numerical value.Here, we just keep on increasing the count of word pairs for next word if the next word follows current word.Reference:- https://en.wikipedia.org/wiki/Trie<jupyter_code>def build_trie(pairs):
    trie = {}
    for pair in pairs:
        a, b = pair
        if a not in trie:
            trie[a] = {}
        if b not in trie[a]:
            trie[a][b] = 1
        else:
            trie[a][b] += 1
    return trie
trie = build_trie(pairs)<jupyter_output><empty_output><jupyter_text>Build ProbabilitiesSince trie stores the count of (current word, next word), we normalize the frequency to get the probability.<jupyter_code>def build_probabilities(trie):
    for word, following in trie.items():
        total = sum(following.values())
        for key in following:
            following[key] /= total
    return trie
trie = build_probabilities(trie)<jupyter_output><empty_output><jupyter_text>Generate Tweet  Version 1Here, we are going to introduce some small randomness. This is one way to introduce random factor into probabilities.In this technique, we are simply going to count probabilities of transition word and check the total probability to some random factor.<jupyter_code>def generate1(trie, initial_word, max_len=5, verbose=False):
    res = []
    word = initial_word
    while len(res) < max_len:
        if word not in trie:
            break
        transitions = trie[word]
        if verbose:
            print("Current word :: ", word)
            print("Transitions :: ", transitions)
        t = 0
        for w in transitions:
            p = transitions[w]
            t += p
            if t and (random.random() * t) < p:
                next_word = w
            if verbose:
                print(w, p)
        res.append(word)
        word = next_word
    return res
generated_words = generate1(trie, initial_word='i', max_len=20, verbose=False)
' '.join(generated_words)<jupyter_output><empty_output><jupyter_text>Version 2This is another way to introduce some randomness to the states. Here we are going to normalize probabilities of transition words with random number and get the next state with max probability (just like in version 1)<jupyter_code>def generate2(trie, initial_word, max_len=5, verbose=False):
    res = []
    word = initial_word
    while len(res) < max_len:
        if word not in trie:
            break
        transitions = trie[word].items()
        transitions_randomized = {w : random.random() * p for w, p in transitions }
        next_state = max(transitions_randomized.items(), key=lambda x : x[1])
        if verbose:
            print("Current word :: ", word)
            print("Transitions :: ", transitions)
            print("Next state :: ", next_state)
        res.append(word)
        word = next_state[0]
    return res
generated_words = generate2(trie, initial_word='we', max_len=20, verbose=False)
' '.join(generated_words)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09885496183206106, 'fraction_numerical': 0.006679389312977099, 'mean_word_length': 3.5415944540727904, 'pattern_counts': {'":': 0, '<': 36, '<?xml version=': 0, '>': 35, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '583505', 'license': 'MIT', 'n_tokens_mistral': 1601, 'n_tokens_neox': 1559, 'n_words': 562, 'path': 'tweet-generator-markov.ipynb', 'repo_name': 'NISH1001/tweetypie', 'size': '5240'}