比O（n）glob匹配器好吗？

问题：给定一个globs的列表，我需要从列表中找到（并返回）一个给定字符串匹配或确定无匹配的glob。排除安装时间，性能必须优于线性搜索所有水珠的：比O（n）glob匹配器好吗？

foreach glob in list: 
    if glob.matches(string): 
    return glob 
return None

问题：是否有任何可用的库（C++首选）这个？

编辑：多一点思考后，我在想我可以说，这是可以做到。考虑到globs或多或少具有不同语法的正则表达式，使用glob语法的lex的运行时版本将适合账单。

鉴于问题可以简单地归结为一个已知问题，我只对实施的解决方案感兴趣。

来源

2011-03-25 BCS

它甚至有可能？鉴于26个水珠（'* A *'，'* B *'，'* C *'...'* Z *'）是有可能不检查所有26个水珠（因此为O（n）） – xanatos 2011-03-25 15:04:40

萨那托斯：考虑到这一点，你应该期望在一场比赛之前只需要检查少量球。或者你可以将它压缩到正则表达式'。* [A-Z]。*'并运行它。 – BCS 2011-03-25 15:08:27

Glob是正则表达式的子集（关于表达力，而不是确切的语法）。因此Globs可以转换为确定性有限自动机（DFA），并且可以组合形成单个DFA，以识别单个DFA的联合。 DAs具有O（n）的复杂度，其中n是字符串的长度。自动机的构造数量仅影响建立时间（即创建自动机），而不影响运行时间。

来源

2011-03-25 15:06:33 Oswald

我不包括设置时间。 – BCS 2011-03-25 15:09:28

我刚刚注意到，改变了我的答案。 – Oswald 2011-03-25 15:15:00

我不认为有可能有比线性时间更好的球体数量。为了证明一个字符串与任何一个字符串都不匹配，你必须检查每一个匹配，否则你永远不会知道你是否跳过匹配。

编辑：在一般情况下，这是不可能使用globs。正如在评论中指出的那样，可以组合一些球体的组合（首先猜测一个体系可能是有用的，其中每个节点指示要匹配的下一个字母以及您仍需要检查的球体），导致工作量较少搜索。

在一般情况下，也可以将一组球体转换为相应的正则表达式。

表现这种匹配真的是这样一个问题，你需要改进它？你有没有考虑过一个更基本的算法重写可能会更好？

来源

2011-03-25 15:09:51

假设您无法将某些匹配工作与某些设置工作结合使用：例如如果'/富/酒吧/ *'不匹配，5位，'/富/巴兹/ *'不必进行检查，如果第二位，失败后'/咸菜/ *'可以跳过。 – BCS 2011-03-25 15:16:05

从技术上讲，您可以尝试创建一个“不匹配”的“否定”表达式。它可以是简单的，但我不知道......我一直在寻找两个非simplifiable和不negatable表情......虽然水珠的结合显然是为O（n），也许是负水珠的交集是少一点。 – xanatos 2011-03-25 15:22:34

可能只是在某些特定情况下。如果你能以某种方式预测某些球体不符合你的弦线。

来源

2011-03-25 15:10:20 cprogrammer

将你的球体转换成正则表达式（一系列简单的字符串操作可以实现这一点 - *成为.*等）。将它们组合成一个正则表达式，使用|并将结果分配给每个glob的不同捕获组，以便您可以确定匹配时匹配哪个glob。依靠您最喜欢的正则表达式将正则表达式编译为DFA，该DFA有希望更好地处理，而不是组成部分的线性步骤，但在最常见的情况下，速度不会更快。

来源

2011-03-25 15:15:28 moonshadow

Wha？如果给定足够的免费启动时间，任何正则表达式都可以在'lenght（input）'时间内匹配，所以在多于一个glob的情况下，它应该更快。我错过了什么？ – BCS 2011-03-25 15:20:42

你如何找到哪个捕获组被填充小于'O（n）'？ – BCS 2011-03-25 15:25:20

@BCS：任何特定的正则表达式（这是真正的“正规军”;有的Perl的“正则表达式”语法不符合条件）可以在O匹配（长度（输入））的时间，是的。但是，当正则表达式的长度也是一个相关变量时，您需要一个不同的计算复杂度模型。 – aschepler 2011-03-25 15:27:25

我想看看你的申请是否适合shift-reduce parser如bison。他们使用查找表，这是一个痛苦的设置或更改并使用更多的内存，但速度非常快。从技术上讲，它不是身体可能比O（N）最坏的情况下，但根据您的水珠，你的字符串，你的分词做的更好，使用这样的技术可以让你的平均情况比这更好，因为它消除了不匹配匹配的模式，而不必每次都检查每个模式。

来源

2011-03-25 15:31:43

查看本文的回答：http://stackoverflow.com/问题/ 5434209 /好于上水珠匹配器/ 5434304＃5434304 – BCS 2011-03-26 16:09:10

比O（n）glob匹配器好吗？

回答

相关问题