2

好吧......所以这可能是一个延伸。我想将一个 TextStrings 列表提供给一个函数，然后它将正则表达式语法返回给我。我正在使用要跟踪的项目的标签或标签模式。我希望能够检测到所有可能存在的模式。我认为可以总结它的正则表达式会很棒。

这是以前做过的事情吗。

我在 VB.NET C# 中工作，建议很好。

也许这是一个糟糕的编程设计。但最想现在从哪里开始搜索？我什至会在谷歌下查找什么？

或者你能给我一些关于如何设计这样一个功能的指导吗？

4

3 回答 3

1

非常有趣的问题。不确定是否有一个好的答案，但这是首先想到的：

Loop through each target string
    Loop through each character in each target string
       Categorize that character as precisely as possible.  7 = \d, f=[a-z] etc
       Create a list of the categories for each character in order.
       Add that list of categories to a list of lists
    End character loop
End target string loop

尝试使用您的类别列表列表来确定将匹配所有目标字符串的正则表达式。例如，如果您的类别列表列表如下所示：

\d,\d,\d,[a-z],[a-z]
\d,\d,\d,[a-z],[a-z]
\d,\d,[a-z],[a-z]

您可能能够确定您的正则表达式需要匹配两到三位数字，后跟两个小写字母。不是很多东西可以去，但也许是一个开始的地方？我很想看看你是否想出了一个可行的解决方案......

于 2012-08-24T22:52:33.673 回答
0

虽然这.*是一个有趣的评论，但如果您添加一个约束，即它是一个接受所有数据但不接受其他数据的最小正则表达式（对于每个运算符的某些成本指标），这个问题就会变得更加有趣。

这导致了下一个问题：您的数据可能并未反映所有示例，因此您真正要寻找的是按类（字符、数字、符号）划分数据。即便如此，这也很困难：如果你在一个实例中真正关心字符大小写，但在另一个实例中不关心字符大小写怎么办。如果某些符号是定界符，而另一些是分隔符，还有一些是数据的一部分，该怎么办。

换句话说，如果有足够的限制，您可以先对可能的正则表达式进行广度搜索（在您有限的语法中），当您找到一个有效的时，您可以停止。如果这在您的特定用例中是现实的，那么在很大程度上取决于这些限制......在一般正则表达式的不受限制的情况下是不现实的。

于 2012-08-24T23:32:34.713 回答
0

我对此事的看法：

问题陈述

给定一个有限字符串 S1..Sn 的有限集合 S，找到一个正则表达式与这些字符串完全匹配，而不是其他字符串，避免平凡解 ^S1|S2|S3|..|Sn$

观察

我们不能有'.' 字符类或“+”、“*”或“{x,}”量词，因为它们将允许匹配输入集之外的字符串。

算法

# strings and collections indexed from 1

regex := "^" + make_regex(S) + "$"

function make_regex(Ss)

    # string -> length
    Ls := { length Ss[i] | 1 <= i <= n } 

    # set of starting characters
    Cs := unique { Ss[i][1] | i in 1..n L[i] >= 1 } 
    cl := last in Cs

    ret := "("
    For c in Cs

        # substrings of all non-empty strings that start with c
        Scs := { S[i][2..] | i in 1..n, L[i] >= 1, S[i][j] = c }
        ret := ret + c + make_regex(Scs) 

        If c != cl
            ret := ret + "|"
        End

    End

    If Ss contains ""
        ret := ret + "|()"

    End
    ret := ret + ")"
    return ret
End

输入

abc
abcd
cde
cef

结果

^(a(b(c(d|())))|c(d(e)|e(f)))$

我相信这是 O(n*Lmax) 因为找到唯一字符串的正则表达式与其长度成线性关系。但是，输入集中的常见前缀越多，它就越接近 O(Lmax)，因此将与结果匹配 - 比 ^S1|S2|..|Sn$ 快得多，即 O(n*最大）。

于 2012-08-26T18:16:15.480 回答