使用正则表达式进行哈希表/字典/映射查找

• 单个字符只是成为trie节点。
• [a-z]范围在该范围内的每个字符下重复插入相同的后续子节点。小心,虽然插入/更新可能有点昂贵,但搜索可以是字符串大小的线性。使用一些占位符可以控制常见的组合爆炸情况。
• (foo)|(bar)节点成为多个插入

Perl有两个类似于Text::Trie的模块,您可以通过raid获取想法。(见鬼,我想我甚至在很久以前写过一篇)

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

在一般情况下,您需要的是lexer生成器。它需要一组正则表达式并将它们编译成识别器。如果您使用的是C语言,“lex”将起作用。我从未在Python中使用过lexer生成器,但似乎有一些可以选择。谷歌展示 PLY PyGgy 和 PyLexer

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

不会 工作罗布·派克 once said

这是绝对可能的,只要您使用的是“真正的”正则表达式。教科书中的正则表达式可以被 deterministic finite state machine ,这主要意味着您不能在其中包含反向引用。

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

如果你有一本字典,比如

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

在这种情况下 regex_dict["food"]

那么以下内容呢:

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
>>>

这里是一种有效的方法,它将键组合到一个编译的regexp中,因此不需要在键模式上进行任何循环。它滥用法律 lastindex

如果不重新编译regexp,这个映射是不可扩展的(不能定义新的键),但是在某些情况下它很方便。

# 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']

有一个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};

@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引擎真正将regexp编译成机器代码,尽管这并不特别困难。我怀疑有一个数量级的性能改进等待着有人制作一个真正好的RE-JIT库。

"n-grams" . 创建一个从单词的n个字符块到整个单词的倒排索引。当给定一个模式时,将其分成n个字符的块,并使用索引计算匹配单词的评分列表。

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

这个问题的一个特例出现在70年代面向演绎数据库的人工智能语言中。这些数据库中的键可以是带有变量的模式——就像没有*或|运算符的正则表达式一样。他们倾向于对索引使用trie结构的奇特扩展。参见诺维格的《克里普》*.lisp Paradigms of AI Programming

如果您有一小组可能的输入,您可以缓存第二个dict中出现的匹配项,并为缓存的值获取O(1)。

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

• 记忆散列查找
• 在备忘录表中预先设定种子(不确定该称为什么…正在预热缓存?)

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

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

>>> regex_dict['FileNfoo']

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

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

这实际上取决于这些正则表达式的外观。如果你没有太多的正则表达式,它们几乎可以匹配 .* \d+ '的正则表达式,而不是 包含 a*b*c “在 ^\d+a\*b\*c:\s+\w+

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

我正在使用 C++/CLI 用于开发名为 LanguageProcessor.dll ,此库的核心是一个lex_规则类,它基本上包含:

• 活动成员

构造函数加载正则表达式字符串并调用必要的代码,以便使用 DynamicMethod Emit 和 Reflexion ... 程序集中还存在其他类,如meta和object,它们通过发布者和接收者类的简单名称来构造和实例化对象,接收者类为每个匹配的规则提供操作处理程序。

fasterlex_engine 那就编一本字典 <Regex, action_delegate> 从要运行的数组中加载定义的。

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_引擎类:

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();
};

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

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;

}

这段代码附加了一个any处理函数(静态或非静态),用于处理由输入字符串匹配引发的回调

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();

这个问题与正则表达式无关——如果字典中的键与lambdas的函数相同,则会出现同样的问题。因此,您面临的问题是,是否有一种方法可以对函数进行分类,以确定其是否返回真值,这不是搜索问题,因为f(x)在之前通常是未知的。

--DM