15

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

我对正则表达式感到不舒服：我无法想出一段起始代码，但我只是想到了一个使用 TList 作为基类并使用过滤器（正则表达式）来对抗“蛮力”生成的字符串的幼稚实现。

其他最佳选择是什么？

  • 排序：首先按长度（最短的优先），然后按字典顺序。
  • 指定要在生成中使用的字符范围：所有可打印或 [AZ]、[az]、数字、特殊符号和最终空格（正则表达式？）的任何可能组合。
  • 字符串长度以给定的最小值/最大值为界。
  • 搜索空间受边界限制：开始字符串和结束字符串，可以过滤（正则表达式？）

上次编辑

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

我正在考虑修改第一个要求，因为它是一扇敞开的大门，可能会导致难以解决的问题。

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

第二个想法要求编辑完成。仍然对改进建议持开放态度。

4

2 回答 2

4

老问题，但没有人回答，赏金仍然有效，我已经准备好解决方案，所以这里有一个可能的答案：

我曾经写过一个小程序来做到这一点。然而，它是在 C++/Qt 中的（虽然我几乎所有的程序都是用 Delphi 编写的，其中一个是 C++ 的），不支持 Unicode 并且不保证顺序

它的工作原理如下：

  1. 全部 ？{} + * | () 运算符被扩展（到最大限制），因此只保留字符类和反向引用。

    例如[a-c]+|t*|([x-z]){2}foo\1|(a|b)(t|u) 变成[a-c]|[a-c][a-c]|[a-c][a-c][a-c]|[a-c][a-c][a-c][a-c]||t|tt|tt|ttt|ttt|([x-z][x-z])foo\1|at|au|bt|bu

    （后一个表达式中的 | 只是符号，程序将每个替代子正则表达式保存在一个列表中）

  2. 对多个字符的反向引用被对单个字符的反向引用替换。

    例如上面的表达式变成[a-c]|[a-c][a-c]|[a-c][a-c][a-c]|[a-c][a-c][a-c][a-c]||t|tt|tt|ttt|ttt|([x-z])([x-z])foo\1\2|at|au|bt|bu

    现在每个替代子正则表达式都匹配一个固定长度的字符串。

  3. 对于每个备选方案，都会打印从类中挑选字符的所有组合：

    例如上面的表达式变成a|b|c|aa|ba|..|cc|aaa|baa|...|ccc|aaaa|...|cccc||t|tt|tt|ttt|ttt|xxfooxx|yxfooyx|...|zzfoozz|at|au|bt|bu

您可能可以添加 shortlex 订单保证，如下所示：

  1. 按字母顺序对类中的字符进行排序

  2. 对上述第 2 步中获得的备选方案进行排序以获取长度

    （有成倍增加的替代方案，但与结果字符串的数量相比，它们的数量通常可以忽略不计）

  3. 对字符类和反向引用进行排序/交换，使每个引用向后指向

  4. 像以前一样枚举单个固定长度替代方案的可能字符串，但从最后一个字符类开始，而不是从第一个字符类开始以获得字母顺序。

    （如果有任何指向前方的反向引用，这将不起作用）

  5. 如果有多个相同长度的替代项，请以“并行”方式枚举它们，比较它们当前的字符串并按字母顺序打印最低的。（即合并每个备选方案的已排序列表。）

    这可以被优化，例如通过检测后缀中的不同前缀和安全字符类，可以在不影响排序的情况下进行枚举。（例如 a[az]|b[az] 具有不同的前缀，并且 [az] 可以在没有任何比较的情况下枚举）

于 2012-07-25T17:35:32.597 回答
3

我会通过为该语言构建最小确定性有限自动机来做到这一点。如果您从正则表达式开始，这可以通过 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();
    }
}
于 2012-07-30T19:21:08.453 回答