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

Question

我想实现在这里找到的马尔可夫算法，但我没能做到。正如 wiki 解释的那样，它是一个递归函数，用于替换语言中的模式。例如

• “A”->“苹果”
• “B”->“包”
• “S”->“商店”
• “T”->“该”
• “商店”->“我的兄弟”
• “从未使用过”-> .“终止规则”

这些规则必须在以下文本上执行：

“我从 T S 买了一个 B of As。”

规则：

1. 按从上到下的顺序检查规则，看看是否可以在输入字符串中找到任何模式。
2. 如果没有找到，则算法停止。
3. 如果找到一个（或多个），则使用其中的第一个将输入字符串中最左边的匹配文本替换为其替换。
4. 如果刚刚应用的规则是终止规则，则算法停止。
5. 转到步骤 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;
}

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

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

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

对于终止规则，如果匹配的规则是终止规则，则temp直接返回结果，不再递归。