21

我试图弄清楚是否有一种相当有效的方法来在字典(或哈希、映射或任何你喜欢的语言调用它)中执行查找,其中键是正则表达式,字符串是针对组键。例如(在 Python 语法中):

>>> regex_dict = { re.compile(r'foo.') : 12, re.compile(r'^FileN.*$') : 35 }
>>> regex_dict['food']
12
>>> regex_dict['foot in my mouth']
12
>>> regex_dict['FileNotFoundException: file.x does not exist']
35

(很明显,上面的例子不能像用 Python 写的那样工作,但这是我想做的事情。)

我可以想到一种天真的方法来实现这一点,其中我遍历字典中的所有键并尝试将传入的字符串与它们匹配,但随后我失去了哈希映射的 O(1) 查找时间和取而代之的是 O(n),其中 n 是我的字典中的键数。这可能是一件大事,因为我预计这本字典会变得非常大,我需要一遍又一遍地搜索它(实际上我需要为我在文本文件中读取的每一行迭代它,并且文件的大小可以是数百兆字节)。

有没有办法做到这一点,而不诉诸 O(n) 效率?

或者,如果您知道一种在数据库中完成此类查找的方法,那也很棒。

(任何编程语言都可以——我使用的是 Python,但我对这里的数据结构和算法更感兴趣。)

有人指出,不止一场比赛是可能的,这是绝对正确的。理想情况下,在这种情况下,我想返回一个包含所有匹配项的列表或元组。不过,我会满足于第一场比赛。

在那种情况下,我看不到 O(1) 是可能的;不过,我会满足于小于 O(n) 的任何东西。此外,底层数据结构可以是任何东西,但我想要的基本行为是我上面写的:查找一个字符串,并返回与正则表达式键匹配的值。

4

19 回答 19

4

这对于任何语言的常规哈希表都是不可能的。您要么必须遍历整个键集,尝试将键与正则表达式匹配,要么使用不同的数据结构。

您应该选择适合您要解决的问题的数据结构。如果您必须匹配任意正则表达式,我不知道有什么好的解决方案。如果您将要使用的正则表达式类更具限制性,您可以使用诸如triesuffix tree之类的数据结构。

于 2008-11-03T21:44:41.197 回答
4

在一般情况下,您需要的是词法分析器生成器。它需要一堆正则表达式并将它们编译成识别器。如果您使用 C,“lex”将起作用。我从未在 Python 中使用过词法分析器生成器,但似乎有一些可供选择。谷歌展示了PLYPyGgyPyLexer

如果正则表达式在某些方面都彼此相似,那么您可以采取一些捷径。我们需要更多地了解您试图解决的最终问题,以便提出任何建议。你能分享一些示例正则表达式和一些示例数据吗?

另外,您在这里处理多少个正则表达式?你确定天真的方法行不通吗?正如 Rob Pike曾经说过的那样,“当 n 很小时,花哨的算法很慢,而 n 通常也很小。” 除非你有成千上万的正则表达式,以及数以千计的东西要匹配它们,而且这是一个用户在等待你的交互式应用程序,否则你最好还是用简单的方法来循环使用正则表达式。

于 2008-11-03T21:53:03.880 回答
4

只要您使用“真正的”正则表达式,这绝对是可能的。教科书正则表达式是可以被确定性有限状态机识别的东西,这主要意味着你不能在那里有反向引用。

正则语言的一个属性是“两种正则语言的联合是正则的”,这意味着您可以使用单个状态机一次识别任意数量的正则表达式。相对于表达式的数量,状态机在 O(1) 时间内运行(相对于输入字符串的长度,它在 O(n) 时间内运行,但哈希表也是如此)。

一旦状态机完成,您将知道哪些表达式匹配,并且从那里很容易在 O(1) 时间内查找值。

于 2008-11-04T06:30:01.667 回答
4

您要做的与 xrdb 支持的非常相似。然而,它们只支持相当少的通配概念。

在内部,您可以通过将正则表达式存储为字符树来实现比他们更大的正则语言系列。

  • 单个字符只是成为特里节点。
  • .' 成为覆盖当前 trie 节点的所有子节点的通配符插入。
  • * 成为前一个项目开头的节点的尝试中的反向链接。
  • [az] 范围在范围内的每个字符下重复插入相同的后续子节点。小心,虽然插入/更新可能有点昂贵,但搜索可以是字符串大小的线性。使用一些占位符的东西,可以控制常见的组合爆炸案例。
  • (foo)|(bar) 节点变为多次插入

这不处理出现在字符串中任意点的正则表达式,但可以通过在任一侧用 .* 包装正则表达式来建模。

Perl 有几个类似 Text::Trie 的模块,您可以从中寻找灵感。(哎呀,我想我什至在很久以前就写过其中一个)

于 2008-11-05T20:52:08.743 回答
3

如果你有一本字典,比如

regex_dict = { re.compile("foo.*"): 5, re.compile("f.*"): 6 }

在这种情况下regex_dict["food"],可以合法地返回 5 或 6。

即使忽略这个问题,使用 regex 模块也可能无法有效地做到这一点。相反,您需要的是内部有向图或树结构。

于 2008-11-03T21:46:56.810 回答
3

以下情况如何:

class redict(dict):
def __init__(self, d):
    dict.__init__(self, d)

def __getitem__(self, regex):
    r = re.compile(regex)
    mkeys = filter(r.match, self.keys())
    for i in mkeys:
        yield dict.__getitem__(self, i)

它基本上是 Python 中 dict 类型的子类。有了这个,你可以提供一个正则表达式作为键,并且所有匹配这个正则表达式的键的值都使用 yield 以可迭代的方式返回。

有了这个,您可以执行以下操作:

>>> keys = ["a", "b", "c", "ab", "ce", "de"]
>>> vals = range(0,len(keys))
>>> red = redict(zip(keys, vals))
>>> for i in red[r"^.e$"]:
...     print i
... 
5
4
>>>
于 2009-05-03T01:18:14.650 回答
3

这是一种通过将键组合成单个编译的正则表达式的有效方法,因此不需要对键模式进行任何循环。它滥用lastindex找出匹配的密钥。(遗憾的是,正则表达式库不允许您标记正则表达式编译到的 DFA 的终端状态,否则这将不是一个黑客攻击。)

该表达式编译一次,将生成一个无需顺序搜索的快速匹配器。与其他一些建议的解决方案不同,公共前缀在 DFA 中一起编译,因此键中的每个字符匹配一次,而不是多次。您正在为您的键空间有效地编译一个迷你词法分析器。

如果不重新编译正则表达式,此映射不可扩展(无法定义新键),但在某些情况下它可能很方便。

# Regular expression map
# Abuses match.lastindex to figure out which key was matched
# (i.e. to emulate extracting the terminal state of the DFA of the regexp engine)
# Mostly for amusement.
# Richard Brooksby, Ravenbrook Limited, 2013-06-01

import re

class ReMap(object):

    def __init__(self, items):
        if not items:
            items = [(r'epsilon^', None)] # Match nothing
        key_patterns = []
        self.lookup = {}
        index = 1
        for key, value in items:
            # Ensure there are no capturing parens in the key, because
            # that would mess up match.lastindex
            key_patterns.append('(' + re.sub(r'\((?!\?:)', '(?:', key) + ')')
            self.lookup[index] = value
            index += 1
        self.keys_re = re.compile('|'.join(key_patterns))

    def __getitem__(self, key):
        m = self.keys_re.match(key)
        if m:
            return self.lookup[m.lastindex]
        raise KeyError(key)

if __name__ == '__main__':
    remap = ReMap([(r'foo.', 12), (r'FileN.*', 35)])
    print remap['food']
    print remap['foot in my mouth']
    print remap['FileNotFoundException: file.x does not exist']
于 2013-06-01T18:20:58.337 回答
2

有一个 Perl 模块可以做这个Tie::Hash::Regex

use Tie::Hash::Regex;
my %h;

tie %h, 'Tie::Hash::Regex';

$h{key}   = 'value';
$h{key2}  = 'another value';
$h{stuff} = 'something else';

print $h{key};  # prints 'value'
print $h{2};    # prints 'another value'
print $h{'^s'}; # prints 'something else'

print tied(%h)->FETCH(k); # prints 'value' and 'another value'

delete $h{k};   # deletes $h{key} and $h{key2};
于 2008-11-04T04:31:23.857 回答
2

@rptb1 您不必避免捕获组,因为您可以使用 re.groups 来计算它们。像这样:

# Regular expression map
# Abuses match.lastindex to figure out which key was matched
# (i.e. to emulate extracting the terminal state of the DFA of the regexp engine)
# Mostly for amusement.
# Richard Brooksby, Ravenbrook Limited, 2013-06-01

import re

class ReMap(object):
    def __init__(self, items):
        if not items:
            items = [(r'epsilon^', None)] # Match nothing
        self.re = re.compile('|'.join('('+k+')' for (k,v) in items))
        self.lookup = {}
        index = 1
        for key, value in items:
            self.lookup[index] = value
            index += re.compile(key).groups + 1

    def __getitem__(self, key):
        m = self.re.match(key)
        if m:
            return self.lookup[m.lastindex]
        raise KeyError(key)

def test():
    remap = ReMap([(r'foo.', 12),
                   (r'.*([0-9]+)', 99),
                   (r'FileN.*', 35),
                   ])
    print remap['food']
    print remap['foot in my mouth']
    print remap['FileNotFoundException: file.x does not exist']
    print remap['there were 99 trombones']
    print remap['food costs $18']
    print remap['bar']

if __name__ == '__main__':
    test()

遗憾的是,很少有 RE 引擎实际上将正则表达式编译为机器代码,尽管这并不是特别难做。我怀疑有一个数量级的性能改进等待某人制作一个非常好的 RE JIT 库。

于 2013-06-01T23:32:46.203 回答
1

正如其他受访者指出的那样,不可能在恒定时间内使用哈希表来做到这一点。

一种可能有帮助的近似方法是使用一种称为“n-gram”的技术。创建从单词的 n 个字符块到整个单词的倒排索引。当给定一个模式时,将其拆分为 n 个字符的块,并使用索引来计算匹配单词的评分列表。

即使您不能接受近似值,在大多数情况下,这仍然会提供准确的过滤机制,因此您不必将正则表达式应用于每个键。

于 2008-11-03T21:54:01.337 回答
1

这个问题的一个特例出现在 70 年代以演绎数据库为导向的 AI 语言中。这些数据库中的键可能是带有变量的模式——比如没有 * 或 | 的正则表达式。运营商。他们倾向于对索引使用花哨的 trie 结构扩展。请参阅 Norvig 的人工智能编程范式中的krep*.lisp 以了解总体思路。

于 2008-11-04T05:02:57.570 回答
1

如果您有一小部分可能的输入,则可以缓存匹配项,因为它们出现在第二个字典中,并为缓存的值获取 O(1)。

如果可能的输入集太大而无法缓存但不是无限的,您可以将最后 N 个匹配项保留在缓存中(查看 Google 的“LRU 地图” - 最近最少使用)。

如果你不能这样做,你可以尝试通过检查前缀或类似的东西来减少你必须尝试的正则表达式的数量。

于 2008-11-04T12:39:42.000 回答
1

我曾经为一个项目创建过这个精确的数据结构。正如你所建议的,我天真地实现了它。我确实做了两个非常有用的优化,这对你来说可能可行,也可能不可行,具体取决于你的数据大小:

  • 记忆哈希查找
  • 预先播种 memoization 表(不知道怎么称呼这个......预热缓存?)

为了避免多个键匹配输入的问题,我给每个正则表达式键一个优先级,并使用最高优先级。

于 2008-11-06T05:55:42.780 回答
0

我认为,基本假设是有缺陷的。您不能将哈希映射到正则表达式。

于 2008-11-03T21:44:21.870 回答
0

我什至认为这在理论上是不可能的。如果有人传入一个匹配超过 1 个正则表达式的字符串会发生什么。

例如,如果有人这样做会发生什么:

>>> regex_dict['FileNfoo']

这样的事情怎么可能是 O(1)?

于 2008-11-03T21:44:49.247 回答
0

通过将搜索表达式连接成一个大的正则表达式,由“|”分隔,可以让正则表达式编译器为您完成大部分工作在这种情况下,一个聪明的正则表达式编译器可能会搜索备选方案中的共性,并设计一种比简单地依次检查每个选项更有效的搜索策略。但我不知道是否有编译器可以做到这一点。

于 2008-11-04T00:13:40.163 回答
0

这真的取决于这些正则表达式的样子。如果您没有很多正则表达式几乎可以匹配“ .*”或“ \d+”之类的任何内容,而是您的正则表达式主要包含单词和短语或任何长度超过 4 个字符的固定模式(例如 ' a*b*c' in ^\d+a\*b\*c:\s+\w+),如您的例子。您可以使用这个可以很好地扩展到数百万个正则表达式的常用技巧:

为正则表达式构建倒排索引(rabin-karp-hash('fixed pattern') -> 包含'fixed pattern'的正则表达式列表)。然后在匹配时,使用 Rabin-Karp 散列计算滑动散列并查找倒排索引,一次推进一个字符。您现在有 O(1) 查找倒排索引不匹配和一个合理的 O(k) 匹配时间,k 是倒排索引中正则表达式列表的平均长度。对于许多应用程序,k 可能非常小(小于 10)。倒排索引的质量(误报意味着更大的 k,误报意味着错过匹配)取决于索引器对正则表达式语法的理解程度。如果正则表达式是由人类专家生成的,它们也可以为包含的固定模式提供提示。

于 2008-11-04T01:57:30.657 回答
0

好的,我有一个非常相似的需求,我有很多不同语法的行,基本上是用一些代码来注释行和行,以便在智能卡格式的过程中使用,还有密钥和密码的描述符行,在在每种情况下,我认为“模型”模式/动作是识别和处理大量线条的野兽方法。
我正在使用C++/CLIfor 开发名为 的程序集LanguageProcessor.dll,该库的核心是一个 lex_rule 类,它基本上包含:

  • 正则表达式成员
  • 活动成员

构造函数加载正则表达式字符串并调用必要的代码来动态构建事件DynamicMethodEmit并且Reflexion......在程序集中还存在其他类,如构建 ans 的元和对象,并通过发布者的简单名称和接收器类,接收器类为每个匹配的规则提供动作处理程序。

晚了,我有一个名为的类fasterlex_engine,它构建了一个字典,该字典<Regex, action_delegate> 从数组中加载定义以供运行。

该项目处于高级阶段,但我今天仍在建设中。我将尝试通过使用一些直接使用正则表达式查找字典的机制来提高围绕对每一对 foreach 行输入的顺序访问的运行性能,例如:

map_rule[gcnew Regex("[a-zA-Z]")];

在这里,我的代码的一些片段:

public ref class lex_rule: ILexRule
{
private:
    Exception           ^m_exception;
    Regex               ^m_pattern;

    //BACKSTORAGE delegates, esto me lo aprendi asiendo la huella.net de m*e*da JEJE
    yy_lexical_action   ^m_yy_lexical_action; 
    yy_user_action      ^m_yy_user_action;

public: 
    virtual property    String ^short_id; 
private:
    void init(String ^_short_id, String ^well_formed_regex);
public:

    lex_rule();
    lex_rule(String ^_short_id,String ^well_formed_regex);
    virtual event    yy_lexical_action ^YY_RULE_MATCHED
    {
        virtual void add(yy_lexical_action ^_delegateHandle)
        {
            if(nullptr==m_yy_lexical_action)
                m_yy_lexical_action=_delegateHandle;
        }
        virtual void remove(yy_lexical_action ^)
        {
            m_yy_lexical_action=nullptr;
        }

        virtual long raise(String ^id_rule, String ^input_string, String ^match_string, int index) 
        {
            long lReturn=-1L;
            if(m_yy_lexical_action)
                lReturn=m_yy_lexical_action(id_rule,input_string, match_string, index);
            return lReturn;
        }
    }
};

现在执行大量模式/动作对的 fasterlex_engine 类:

public ref class fasterlex_engine 
{
private: 
    Dictionary<String^,ILexRule^> ^m_map_rules;
public:
    fasterlex_engine();
    fasterlex_engine(array<String ^,2>^defs);
    Dictionary<String ^,Exception ^> ^load_definitions(array<String ^,2> ^defs);
    void run();
};

并且为了装饰这个主题..我的 cpp 文件的一些代码:

此代码通过参数符号创建构造函数调用程序

inline Exception ^object::builder(ConstructorInfo ^target, array<Type^> ^args)
{
try
{
    DynamicMethod ^dm=gcnew DynamicMethod(
        "dyna_method_by_totem_motorist",
        Object::typeid,
        args,
        target->DeclaringType);
    ILGenerator ^il=dm->GetILGenerator();
    il->Emit(OpCodes::Ldarg_0);
    il->Emit(OpCodes::Call,Object::typeid->GetConstructor(Type::EmptyTypes)); //invoca a constructor base
    il->Emit(OpCodes::Ldarg_0);
    il->Emit(OpCodes::Ldarg_1);
    il->Emit(OpCodes::Newobj, target); //NewObj crea el objeto e invoca al constructor definido en target
    il->Emit(OpCodes::Ret);
    method_handler=(method_invoker ^) dm->CreateDelegate(method_invoker::typeid);
}
catch (Exception ^e)
{
    return  e;
}
return nullptr;

}

此代码附加任何处理程序函数(静态或非静态)以处理通过匹配输入字符串引发的回调

Delegate ^connection_point::hook(String ^receiver_namespace,String ^receiver_class_name, String ^handler_name)
{
Delegate ^d=nullptr;
if(connection_point::waitfor_hook<=m_state) // si es 0,1,2 o mas => intenta hookear
{ 
    try 
    {
        Type ^tmp=meta::_class(receiver_namespace+"."+receiver_class_name);
        m_handler=tmp->GetMethod(handler_name);
        m_receiver_object=Activator::CreateInstance(tmp,false); 

        d=m_handler->IsStatic?
            Delegate::CreateDelegate(m_tdelegate,m_handler):
            Delegate::CreateDelegate(m_tdelegate,m_receiver_object,m_handler);

        m_add_handler=m_connection_point->GetAddMethod();
        array<Object^> ^add_handler_args={d};
        m_add_handler->Invoke(m_publisher_object, add_handler_args);
        ++m_state;
        m_exception_flag=false;
    }
    catch(Exception ^e)
    {
        m_exception_flag=true;
        throw gcnew Exception(e->ToString()) ;
    }
}
return d;       
}

最后是调用词法分析引擎的代码:

array<String ^,2> ^defs=gcnew array<String^,2>  {/*   shortID    pattern         namespc    clase           fun*/
                                                    {"LETRAS",  "[A-Za-z]+"     ,"prueba",  "manejador",    "procesa_directriz"},
                                                    {"INTS",    "[0-9]+"        ,"prueba",  "manejador",    "procesa_comentario"},
                                                    {"REM",     "--[^\\n]*"     ,"prueba",  "manejador",    "nullptr"}
                                                }; //[3,5]

//USO EL IDENTIFICADOR ESPECIAL "nullptr" para que el sistema asigne el proceso del evento a un default que realice nada
fasterlex_engine ^lex=gcnew fasterlex_engine();
Dictionary<String ^,Exception ^> ^map_error_list=lex->load_definitions(defs);
lex->run();
于 2011-04-29T17:50:33.013 回答
0

这个问题与正则表达式无关 - 你会遇到与作为 lambda 函数的键的字典相同的问题。因此,您面临的问题是确定是否有一种方法可以对您的函数进行分类以计算是否返回真值,这不是搜索问题,因为通常事先不知道 f(x)。

假设有共同的 x 值,分布式编程或缓存答案集可能会有所帮助。

-- DM

于 2012-04-17T11:51:38.903 回答