如何在Java中实现马尔可夫算法？

Question

我想实现找到的马尔可夫算法 here，但我没能实现。正如 wiki 所解释的那样，它是一种递归函数，可以替换语言中的模式。例如

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

必须在以下文本中实施这些规则：

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

规则：

按照从上到下的顺序检查规则，看看是否有这些模式可以在输入字符串中找到。
如果找到 none，则算法停止。
如果找到一个（或多个），请使用其中的第一个来替换输入字符串中最左边出现的匹配文本及其替换。
如果刚刚应用的规则是终止规则，算法将停止。
转到步骤 1。

我考虑创建两个类 Rule 和 RuleContainer。

Rule 有 3 个属性：String from、String To 和 Boolean terminating

RuleContainer 有一个动态列表，其中包含活动规则和逻辑函数 [我正在尝试创建的那个]。

我已经考虑了 String.replace() 函数，并尝试将其实现为递归函数。

实施马尔可夫算法的最佳方法是什么？

Answer 1

暂时忽略终止规则部分，递归函数的基本形状如下所示：

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;
}

这将一直调用自身，直到没有规则与当前输入字符串相匹配，此时它将展开 return调用堆栈中的结果。您只需要将以下方法添加到您的 Rule class:

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

这些可以只是简单的 String 函数（contains、replaceFirst 等），或者您可以使用 java.util.regex.Pattern 和 java.util.regex.Matcher 来保存重新编译每次的 recglar 表达式。

对于终止规则，如果匹配的规则是终止规则，则return直接temp结果而不进一步递归。

如何在Java中实现马尔可夫算法？

How to implement Markov's algorithm in Java?

java

algorithm

recursion

substitution

markov