java - 根据预定义的规则集将输入集分类为类别

Question

我试图解决一个有两个输入文件的问题，
输入1：
格式中的一组字符串所有的字符串都以“a”开头。
A-B-C-D型
A-B-C-3号
A-X-Y-Z-4型
A-X-5型
A-X-P-Q-R型
A-X-P-Q-S型
A-M-9-P公司
A-M-10-Q型
A-M-N-G-3号
A-V-B-H-3型
A-J-K-L-3-S-Y型
A-U-3-W-E型
这里是A，B，C，D，X，Y，Z，M（所有字母都是关键字，整数是占位符）
输入2：
一组规则和每组规则的名称每个规则集可以有一个或多个规则。所有规则集都以“a”开头
规则1:（名称：红色）
A-X型-^
规则2:（姓名：蓝色）
A-X-P-Q-R型
A-X-P-Q-S型
规则三：（姓名：黄色）
A-X-P-Q-S型
A-X-P-Q-R型
规则4:（名称：绿色）
上午-$-P
上午-@-Q
上午--P
规则五：（姓名：紫色）
A-V-B-H型-$
A-J-K-L-$-S-Y
A-U-$-W-E型
其中字母表是关键字，其他（如^，$，@，#…）是占位符在给定的规则集中，如果占位符相同（如规则5所示），则表示占位符值必须相同，只有这样它才属于此类别。如果它们是不同的占位符，则值可能不同。
问题陈述：
获取输入1（一组字符串）并根据输入2中的规则集查找该输入所属的类别输出可以是一个或多个类别此外，规则集中的规则可能不会一个接一个地出现在输入中。
两者之间可能还有其他多种规则。例如，在规则2中，a-x-p-q-r后面必须跟着a-x-p-q-s，这并不意味着这两个规则之间不可能有其他规则。
例子：
输入文件可以是
A-X-P-Q-R型
A-Q-W型
A-Y-T-H型
A-X-P-Q-S型
它仍然符合规则2，属于“蓝色”
我的方法：
我在想两种方法
使用决策树（或）
将输入1表示为图，将输入2中的每个单独规则集表示为单独的图，并查找图同构。
有什么想法吗？

Answer 1

这个问题没有完全说明，但是可以给出一个一般的解决方案。
假设规则是由模式组成的，我们希望使模式匹配（有序）的所有行组合。
然后，可以给出一个简单的解决方案（具有二次成本）（注意：这不考虑相同模式中相同的占位符）：

package com.so;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import static com.so.Matching.Pattern.pattern;
import static java.util.stream.Collectors.joining;

public class Matching {

    private static boolean isPlaceholder(char c) {
        return c != '-' && !Character.isAlphabetic(c);
    }

    public static void main(String... args) {

        String[] lines = {
                "A-B-C-D",
                "A-B-C-3",
                "A-X-Y-Z-4",
                "A-X-5",
                "A-X-P-Q-R",
                "A-X-P-Q-S",
                "A-M-9-P",
                "A-M-10-Q",
                "A-M-N-G-3",
                "A-V-B-H-3",
                "A-J-K-L-3-S-Y",
                "A-U-3-W-E"
        };

        Rule[] rules = {
                new Rule("Red", pattern("A-X-^")),
                new Rule("Blue", pattern("A-X-P-Q-R"), pattern("A-X-P-Q-S")),
                new Rule("Yellow", pattern("A-X-P-Q-S"), pattern("A-X-P-Q-R")),
                new Rule("Green", pattern("A-M-$-P"), pattern("A-M-@-Q"), pattern("A-M-#-P")),
                new Rule("Purple", pattern("A-V-B-H-$"), pattern("A-J-K-L-$-S-Y"), pattern("A-U-$-W-E")),
        };

        Arrays.stream(rules)
                .parallel()
                .flatMap(r -> r
                        .matches(lines)
                        .stream()
                        .map(s -> String.format("%s: %s",
                                r.getName(),
                                Arrays.stream(s).boxed().map(Object::toString).collect(joining(", ")))))
                .forEach(System.out::println);

    }

    static class Pattern {
        private final String pattern;

        Pattern(String pattern) {
            this.pattern = pattern;
        }

        static Pattern pattern(String pattern) {
            return new Pattern(pattern);
        }

        boolean match(String input) {
            if (pattern.length() != input.length())
                return false;
            for (int i = 0; i < pattern.length(); i++)
                if (!isPlaceholder(pattern.charAt(i)) && pattern.charAt(i) != input.charAt(i))
                    return false;
            return true;
        }
    }

    static class Rule {
        private final Pattern[] patterns;
        private final String name;

        Rule(String name, Pattern... patterns) {
            this.name = name;
            this.patterns = patterns;
        }

        List<int[]> matches(String[] lines) {
            List<int[]> solutions = new ArrayList<>();
            int[] solution = new int[patterns.length];
            search(lines, solutions, solution, 0, 0);
            return solutions;
        }

        private void search(String[] lines, List<int[]> solutions, int[] solution, int curIndex, int curLine) {
            if (curIndex == solution.length) {
                solutions.add(Arrays.stream(solution).toArray());
            } else {
                for (int i = curLine; i < lines.length; i++)
                    if (patterns[curIndex].match(lines[i])) {
                        solution[curIndex] = i;
                        search(lines, solutions, solution, curIndex + 1, i + 1);
                    }
            }
        }

        public String getName() {
            return name;
        }
    }

}

输出：

Blue: 4, 5
Purple: 9, 10, 11
Red: 3

现在，让我们证明（一般来说）它不能比二次成本做得更好。
给定以下规则和以下条目，解为：1-2、1-3、1-4、…、2-3、2-4、2-5、…、3-4、3-5、3-6、这意味着二次成本。
规则：

A-$

输入：

A-B
A-B
A-B
....

但是如果我们压缩解决方案，我们可以改进它，最简单的形式是只给出索引，而不是组合在前面的示例中，规则的唯一模式适合以下行：1、2、3、…我们可以知道它的线性成本。
如果占位符可以被一个固定字符（例如“*”）替换，那么您可以使用摊销的固定成本（散列）匹配模式搜索每个输入行。
因此，您只需将模式保存在内存中（在哈希表中），就可以线性地遍历输入文件（它可能比可用内存大得多），并只返回已装配在一起的模式集。
但是由于“这意味着占位符的值必须是相同的”，所以不能使用任何有效的搜索算法，而是使用固定成本（散列），必须支付线性成本（对于每个输入行）。不管怎样，比输入行数的二次型要好。
当然，您不会完全给出解决方案，有了这些索引，您可以按顺序对它们进行二次遍历。
我把这一有效战略的实施留给你们作为练习；）