1

我一直在尝试实现马尔科夫算法，但我只取得了部分成功。该算法相当简单，可以在这里找到。

但是，我的项目有一个额外的困难，我必须使用包含标记和变量的规则。

变量代表字母表中的任何字母，标记只是一个字符，用作移动变量的参考（它没有实际值）。

此示例复制字符串中的每个字符：

字母：{a,b,c}

标记：{M}

变量：{x}

规则 1：Mx -> xxM

规则 2：xM -> x

规则 3：x -> Mx

输入： abc

abc //我们应用规则 3

Mabc //我们应用规则 1

aaMbc //我们应用规则 1

aabbMc //我们应用规则 1

aabbccM //我们应用规则 2

aabbcc

这是我的递归函数，它实现了仅适用于字符串输入的马尔可夫算法，例如：规则 1：“apple”->“orange”，输入：“apple”。

public static String markov(String input, LinkedList<Rule> rules) {
    for (Rule rule : rules) {
        if (!input.equals(input.replace(rule.getFrom(), rule.getTo()))) { //If the rule matches a substring
            if (rule.isTerminating()) { //If the rule is terminating
                input = input.replaceFirst(Pattern.quote(rule.getFrom()), rule.getTo());
                System.out.println(input); //Replace the first instance
                return input; //return and end the cycle
            } else {
                input = input.replaceFirst(Pattern.quote(rule.getFrom()), rule.getTo());
                System.out.println(input);
                return markov(input, rules); //Start looking again for matching rules
            }
        }
    }
    return input;
}

我不知道如何在这个逻辑中实现变量和标记，所以也许有人可以教育我实现这个逻辑的最佳方式？欢迎任何建议。

如果问题不符合 SO 准则，请在评论中告诉我原因，这样我就不会重复错误。

谢谢你！

GitHub

4

1 回答 1

0

我认为最简单的方法是使用 Java 正则表达式。一旦您了解了这些，那么以下规则应该适用于您的示例：

Rule 1: "M([a-c])" -> "$1$1M"
Rule 2: "([a-c])M" -> "$1" (terminating)
Rule 3: "([a-c])"  -> "M$1"

请注意，您需要对当前方法进行一些调整才能使其正常工作...

replace将文字字符串作为第一个参数，而replaceFirst使用正则表达式，因此：

replace: if (!input.equals(input.replace(rule.getFrom(), rule.getTo()))) {
with:    if (!input.equals(input.replaceFirst(rule.getFrom(), rule.getTo()))) {

您引用的rule.getFrom()字符串不适用于正则表达式，因此：

replace: input = input.replaceFirst(Pattern.quote(rule.getFrom()), rule.getTo());
with:    input = input.replaceFirst(rule.getFrom(), rule.getTo());

那时，您在调用replaceFirst两次的代码中有一些重复，因此您可以第一次将其粘贴在临时变量中并重用它：

String next = input.replace(rule.getFrom(), rule.getTo());
if (!input.equals(next)) {
  ...
  input = next;
  ...
}

由于您目前正在引用整个rule.getFrom()字符串，我猜您之前在此遇到过正则表达式特殊字符的问题。如果是这样，您需要在创建规则时单独解决它们。我真的不想在这里讨论正则表达式，因为它是一个巨大的领域，并且与马尔可夫算法完全分开，所以如果你对这些有问题，那么请在网上做一些研究（例如正则表达式和捕获组），或者在这里提出一个单独的问题，重点关注正则表达式的具体问题。

请注意，您仍然可以将这些与正常规则结合使用（将标记字符从M更改#为允许M在字母表中使用），这些规则：

"A"             -> "apple"
"B"             -> "bag"
"S"             -> "shop"
"T"             -> "the"
"the shop"      -> "my brother"
"#([a-zA-Z .])" -> "$1$1#"
"([a-zA-Z .])#" -> "$1" (terminating)
"([a-zA-Z .])"  -> "#$1"

将转换：

from: I bought a B of As from T S.
to:   II  bboouugghhtt  aa  bbaagg  ooff  aapppplleess  ffrroomm  mmyy  bbrrootthheerr..

希望这可以帮助。

于 2015-10-05T04:35:25.907 回答