使用正则表达式标准生成字符串

Question

我不知道是否可以实现满足以下第二个思想要求的最佳字符串生成器类:

---

• 使用正则表达式生成标准
• 字典顺序列举.
• 伯爵计算
• 索引访问

我对正则表达式感到不舒服:我无法想出一段代码,但我只想到一个使用TList作为基类的天真实现,并使用过滤器(Regex)来对抗"暴力"生成的字符串.

还有哪些其他最佳选择？

---

• 订购:首先按长度(最短的第一个),然后按字典顺序排列.
• 生成中使用的字符范围的规范:[AZ],[az],数字,特殊符号和最终空间(正则表达式？)的所有可打印或任何可能的组合.
• 字符串长度以给定的最小值/最大值为界.
• 搜索空间受边界限制:开始字符串结束字符串可能过滤(正则表达式？)

---

最后编辑

首先,我使用正则表达式而不是正则表达式来改写标题.

我正在考虑修改第一项要求,因为它是一扇敞开的门,可能导致难以解决的问题.

我需要建议和帮助正确的措辞.

第二个想法要求编辑完成.仍然愿意提出改进建议.

Answer 1

我将通过为该语言构建最小的确定性有限自动机来做到这一点。如果您从正则表达式开始，这可以通过 Thompson 构造自动完成，然后进行子集构造和最小化。例如，请参阅此描述。

有了 DFA，您可以使用类似以下的算法：

Let P = { < START, [""] > } be a set of pairs <State, list of strings>
for n = 0, 1, ... Max
  Let P' = {} be a new set 
  while P is not empty 
    Remove the pair <s, L> from P 
    For each transition s -- c --> t in alpha order of c
      if t is an accepting state,
          output l + c for each string l in L
      put <t, L + c> in P' (** i.e. append c to each string in L)
  end
  Set P = P'
end

请注意，标记的步骤**需要是真实集插入，因为很容易出现重复项。

这是一个核心算法。P可以随着输出长度呈指数增长，但这只是跟踪未来输出字符串的所有可能性的代价。您提到的顺序/大小/空间限制可以通过维护列表中的排序顺序L并在达到资源限制时切断搜索来确保。

编辑

这是一个玩具 Java 示例，其中我对带有可选减号的简单二进制浮点文字的 DFA 进行了硬编码。这使用与上面的伪代码略有不同的方案来获得严格的输出排序顺序并适应字符范围。

import java.util.Comparator;
import java.util.TreeSet;

public class Test{

    public static class DFA {

        public static class Transition  {

            final int to;
            final char lo, hi; // Character range.

            public Transition(int to, char lo, char hi) {
                this.to = to;
                this.lo = lo;
                this.hi = hi;
            }

            public Transition(int to, char ch) {
                this(to, ch, ch);
            }
        }

        // transitions[i] is a vector of transitions from state i.
        final Transition [] [] transitions;

        // accepting[i] is true iff state i is accepting
        final boolean [] accepting;

        // Make a fresh immutable DFA.
        public DFA(Transition [] [] transitions, boolean [] accepting) {
            this.transitions = transitions;
            this.accepting = accepting;
        }

        // A pair is a DFA state number and the input string read to get there.
        private static class Pair {
            final int at;
            final String s;

            Pair(int at, String s) {
                this.at = at;
                this.s = s;
            }
        }

        // Compare pairs ignoring `at` states, since 
        // they are equal iff the strings are equal.
        private Comparator<Pair> emitOrder = new Comparator<Pair>() {
            @Override
            public int compare(Pair a, Pair b) {
                return a.s.compareTo(b.s);
            }
        };

        // Emit all strings accepted by the DFA of given max length.
        // Output is in sorted order.
        void emit(int maxLength) {
            TreeSet<Pair> pairs = new TreeSet<Pair>(emitOrder);
            pairs.add(new Pair(0, ""));
            for (int len = 0; len <= maxLength; ++len) {
                TreeSet<Pair> newPairs = new TreeSet<Pair>(emitOrder);
                while (!pairs.isEmpty()) {
                    Pair pair = pairs.pollFirst();
                    for (Transition x : transitions[pair.at]) {
                        for (char ch = x.lo; ch <= x.hi; ch++) {
                            String s = pair.s + ch;
                            if (newPairs.add(new Pair(x.to, s)) && accepting[x.to]) {
                                System.out.println(s);
                            }
                        }
                    }
                }
                pairs = newPairs;
            }
        }
    }

    // Emit with a little DFA for floating point numbers.
    public void run() {
        DFA.Transition [] [] transitions = {
            {   // From 0
                new DFA.Transition(1, '-'),
                new DFA.Transition(2, '.'),
                new DFA.Transition(3, '0', '1'),
            },
            {   // From 1
                new DFA.Transition(2, '.'),
                new DFA.Transition(3, '0', '1'),
            },
            {   // From 2
                new DFA.Transition(4, '0', '1'),
            },
            {   // From 3
                new DFA.Transition(3, '0', '1'),
                new DFA.Transition(4, '.'),
            },
            {   // From 4
                new DFA.Transition(4, '0', '1'),
            }  
        };
        boolean [] accepting = { false, false, false, true, true };
        new DFA(transitions, accepting).emit(4);
    }

    public static void main (String [] args) {
        new Test().run();
    }
}