How to implement Markov's algorithm in Java?

Question

I want to implement Markov's algorithm found here, but I haven't been able to. As the wiki explains it's a recursive function that replaces patterns within a language. For example

• "A" -> "apple"
• "B" -> "bag"
• "S" -> "shop"
• "T" -> "the"
• "the shop" -> "my brother"
• "a never used" -> ."terminating rule"

These rules must be implemented on the following text:

"I bought a B of As from T S."

Rules:

1. Check the Rules in order from top to bottom to see whether any of the patterns can be found in the input string.
2. If none is found, the algorithm stops.
3. If one (or more) is found, use the first of them to replace the leftmost occurrence of matched text in the input string with its replacement.
4. If the rule just applied was a terminating one, the algorithm stops.
5. Go to step 1.

I thought about creating two classes Rule and RuleContainer.

Rule has 3 attributes: String from, String To and Boolean terminating

RuleContainer has a dynamic list containing the active rules and the logic function [The one I' trying to create].

I already took into consideration the String.replace() function and I tried to implement it into a recursive function.

What's the best way to implement Markov's algorithm?

Answer 1

Ignoring the terminating rule part for a second, the basic shape of your recursive function would be something like the following:

String markov(String input, List<Rule> rules) {

  // find the first matching rule, apply it and recurse 
  for (Rule rule : rules) {
    if (rule.matches(input)) {
      String temp = rule.apply(input);
      return markov(temp, rules);
    }
  }

  // no rule matched so just return the input text
  // - this is the terminating case for the recursion
  return input;
}

This will just keep calling itself until no rule matches the current input string, at which point it will unwind returning the result all the way up the call stack. You just need to add the following methods to your Rule class:

public boolean matches(String input) { ... }
public String apply(String input) { ... }

These could just be simple String functions (contains, replaceFirst etc.), or you could use java.util.regex.Pattern and java.util.regex.Matcher to save recompling the recglar expressions each time.

For terminating rules, if the rule which matched is a terminating one, just return the temp result directly without recursing any further.