# lib/hn_title_generator/markov_model.rb

# Markov Models
#
# source: https://www.omniref.com/github/omniref/hn_title_generator/0.1.0/symbols/HNTitleGenerator::MarkovModel
#
# A Markov Model is a set of states, along with the probability of the
# transition between each state. For example, in a series of fair coin
# tosses, the 2 possible states are heads and tails, and the coin will
# transition between the states on each toss with 50% probability.

# Markov Model of coin tossing

# ╔═════╗ ──50%─> ╔═════╗
# ║Heads║         ║Tails║
# ╚═════╝ <─50%── ╚═════╝
#  ^   │           ^   │
#  └50%┘           └50%┘

# Given a corpus of documents, you can build a similar Markov Model
# based on each word being a state, along with the probability of every
# word that comes after it in a sentence.

# Markov Model of "Babies eat. Babies sleep."

# ┌──────────100%───────────┐
# v                         │
# ╔══════╗         ╔═════╗  │
# ║Babies║ ──50%─> ║ eat.║  │
# ╚══════╝         ╚═════╝  │
#    │                │     │
#   50%              100%   │
#    v                v     │
# ╔══════╗         ╔═════╗  │
# ║sleep.║ ─100%─> ║null ║──┘
# ╚══════╝         ╚═════╝

# Common phrases mean sets of words can probabilistically determine what
# comes several words later in a sentence, so you can consider chains of
# words to be a single state that predict the next state (word).
# These are Markov Chains.

# Ruby enables a particularly elegant representation of a Markov Model
# in single line of code: a Hash with keys that represent a particular
# state, to values that are the Array of all observed transitions from
# that state.

# I’ll walk deeper into building the markov model in the next note.
# Table of Contents

#     Creating the Model
#     Training the Model
#     Using the Model

# Tokenization is the process of converting a sentence into (not quite)
# words. I retain extra information in "tokens" vs "words", like
# punctuation, which helps the model reproduce more accurate results.
#
# I’ve chosen a markov chain length of 2 (1 was too squirrely, 3 was
# too exact) after experimenting.
# This means I’ll consider the last 2 tokens as the markov_state that
# probabilistically predicts the current token.
# We handle the last token, given the 2 preceding tokens until there is
# nothing left.

# e.g.

# sentence = 'a b c a b d.'
# tokens = ['a', 'b', 'c', 'a', 'b', 'd.']
# markov_model = {
#  [nil, nil] => ['a'],
#  [nil, 'a'] => ['b'],
#  ['a', 'b'] => ['c', 'd.'],
#  ['b', 'c'] => ['a'],
#  ['c', 'a'] => ['b']
# }

# "I was in ['x'] and ['y'] than I go into ['z']"

# Note, when you query this model for the key[‘b’, ‘d’] it’ll return
# the default "[]".

# So once we have this "model" how do we use it to generate probable
# titles from hacker news? Check out #complete_sentence.

# Sampling the model

# Once the Markov Model is "trained" with all observed states mapped to
# an Array of observed transitions, we can probabilistically advance to
# the next transition by calling Array#sample for any given state in
# the model.

# There's some extra logic here to abort the loop if the token ends in
# punctuation, or we've hit nil (end of a previously observed title) or
# we've exceded a predetermined word count for a reasonable title.

# That's pretty much all there is Markov Models... 3 lines of Ruby to
# create, train and sample.

module HNTitleGenerator

  ##
  # A model to represent all Hacker News titles, and generate sentences using
  # markov chains.
  class MarkovModel
    ##
    # Creates the ultimate buzzword generator using markov chains trained on the
    # titles found in MarkovNews::Item.titles.
    def initialize
      @markov_model = Hash.new { |hash, key| hash[key] = [] }

      Item.each_title do |title|
        tokens = tokenize(title)
        until tokens.empty?
          token = tokens.pop
          markov_state = [tokens[-2], tokens[-1]]
          @markov_model[markov_state] << token
        end
      end
    end

  ##
  # Completes a sentence using the Markov Model trained on news titles.
  #
  # @param [String] sentence to be completed, empty string is acceptable
  # @param [Integer] min_length specifies the lower bound on random sentence
  # length. The sentence may be shorter than this if a punctuation character
  # is encountered.
  # @param [Integer] max_length specifies the upper bound on random sentence
  # length
  # @return [String] a complete sentence according to the markov model
  def complete_sentence(sentence = '', min_length: 5, max_length: 20)
    tokens = tokenize(sentence)
    until sentence_complete?(tokens, min_length, max_length)
      markov_state = [tokens[-2], tokens[-1]]
      tokens << @markov_model[markov_state].sample
    end
    tokens.join(' ').strip
  end

  private
  ##
  # Breaks the sentence into words using spaces. Punctuation is retained as
  # parts of words so that conjunctions and sentence endings retain data.
  #
  # @param [String] sentence to tokenize
  # @return [Array<Symbol>] the tokens in the sentence
  def tokenize(sentence)
    return [] if sentence.nil? || sentence.length == 0

    sentence.split(' ').map { |word| word.downcase.to_sym }
  end

  ##
  # Checks a token list to see if it forms a proper complete sentence
  #
  # @param [Array<symbol>] tokens to consider
  # @param [Integer] minimun length that qualifies a complete sentence
  # @param [Integer] maximum length of any acceptable sentence
  # @return [Boolean] wether the sentence is complete
  def sentence_complete?(tokens, min_length, max_length)
    tokens.length >= max_length || tokens.length >= min_length && (
      tokens.last.nil? || tokens.last =~ /[\!\?\.]\z/
      )
  end
end
end
