Поиск Hashtable/dictionary/map с регулярными выражениями

Ответ 1

То, что вы хотите сделать, очень похоже на то, что поддерживается xrdb. Тем не менее, они поддерживают только минимальное понятие глобуса.

Внутри вы можете реализовать большее количество обычных языков, чем их, сохраняя ваши регулярные выражения в качестве символа trie.

• отдельные символы просто становятся узлами.
• . становятся подстановочными вставками, охватывающими всех детей текущего trie node.
• * верните ссылки в trie на node в начале предыдущего элемента. Диапазоны
• [a-z] повторно вставляют одни и те же последующие дочерние узлы под каждым из символов в диапазоне. С осторожностью, в то время как вставки/обновления могут быть несколько дорогими, поиск может быть линейным по размеру строки. С некоторыми материалами-заполнителями общие случаи комбинаторного взрыва можно держать под контролем.
• (foo) | (bar) узлы становятся несколькими вставками

Это не обрабатывает регулярные выражения, которые встречаются в произвольных точках строки, но они могут быть смоделированы путем переноса вашего регулярного выражения с помощью. * с обеих сторон.

Perl имеет пару модулей Text:: Trie, которые вы можете совершать рейды для идей. (Хек, я думаю, что даже написал один из них назад, когда)

Ответ 2

Это невозможно сделать с обычной хэш-таблицей на любом языке. Вам придется либо перебирать весь набор ключей, пытаясь сопоставить ключ с вашим регулярным выражением, либо использовать другую структуру данных.

Вам следует выбрать структуру данных, соответствующую задаче, которую вы пытаетесь решить. Если вам нужно сопоставлять любые произвольные регулярные выражения, я не знаю о хорошем решении. Если класс регулярных выражений, которые вы используете, более ограничительный, вы можете использовать структуру данных, такую ​​как trie или дерево суффиксов.

Ответ 3

В общем случае вам нужен генератор лексеров. Он принимает кучу регулярных выражений и компилирует их в распознаватель. "lex" будет работать, если вы используете C. Я никогда не использовал генератор lexer в Python, но, похоже, есть несколько вариантов. Google показывает PLY, PyGgy и PyLexer.

Если регулярные выражения похожи друг на друга каким-то образом, вы можете сделать несколько ярлыков. Нам нужно будет узнать больше о конечной проблеме, которую вы пытаетесь решить, чтобы придумать какие-либо предложения. Можете ли вы поделиться некоторыми примерами регулярных выражений и некоторыми образцами данных?

Кроме того, сколько регулярных выражений вы имеете в виду здесь? Вы уверены, что наивный подход не сработает? Как сказал Роб Пайк сказал: "Необычные алгоритмы медленны, когда n мало, а n обычно мало" . Если у вас нет тысяч регулярных выражений и тысяч вещей, которые можно сопоставить с ними, и это интерактивное приложение, в котором пользователь ждет вас, вам может быть лучше всего просто сделать это простым способом и прокрутить регулярные выражения.

Ответ 4

Это определенно возможно, если вы используете "реальные" регулярные выражения. Регулярное выражение в учебнике - это то, что можно распознать с помощью детерминированного конечного автомата, что в первую очередь означает, что вы не можете иметь обратные ссылки там.

Существует свойство регулярных языков, что "объединение двух регулярных языков является регулярным", что означает, что вы можете сразу распознать произвольное количество регулярных выражений с помощью одного конечного автомата. Конечный автомат работает в O (1) раз по отношению к числу выражений (он работает в O (n) времени по отношению к длине входной строки, но также делают таблицы хэшей).

Как только конечный автомат завершится, вы узнаете, какие выражения совпали, и оттуда легко найти значения в O (1) раз.

Ответ 5

Как насчет следующего:

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)

В основном это подкласс типа dict в Python. С этим вы можете предоставить регулярное выражение в качестве ключа, а значения всех ключей, которые соответствуют этому регулярному выражению, возвращаются в итеративном режиме с использованием 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
>>>

Ответ 6

Здесь эффективный способ сделать это, объединив ключи в одном скомпилированном регулярном выражении и не требуя каких-либо циклов по шаблонам ключей. Он нарушает lastindex, чтобы узнать, какой ключ соответствует. (Это библиотеки regexp для стыда не позволяют вам тегировать состояние терминала 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']

Ответ 7

Что произойдет, если у вас есть словарь, например

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

В этом случае regex_dict["food"] может законно вернуть либо 5, либо 6.

Даже игнорируя эту проблему, возможно, нет возможности сделать это эффективно с помощью модуля regex. Вместо этого вам понадобится внутренний ориентированный граф или древовидная структура.

Ответ 8

Существует модуль 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};

Ответ 9

@rptb1 вам не нужно избегать захвата групп, потому что вы можете использовать группы regroups для их подсчета. Вот так:

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

Ответ 10

Как отмечают другие респонденты, это невозможно сделать с хеш-таблицей в постоянное время.

Одно приближение, которое может помочь, - использовать метод n-grams. Создайте инвертированный индекс из n-символьных фрагментов слова ко всему слову. Когда задан шаблон, разделите его на куски n-символа и используйте индекс для вычисления списка совпадающих слов.

Даже если вы не можете принять приближение, в большинстве случаев это все равно обеспечит точный механизм фильтрации, так что вам не нужно применять регулярное выражение к каждому ключу.

Ответ 11

Частный случай этой проблемы возник в 70-х годах на языках AI, ориентированных на дедуктивные базы данных. Ключами в этих базах данных могут быть шаблоны с переменными - как регулярные выражения без * или | операторы. Они, как правило, использовали причудливые расширения трех структур для индексов. См. Krep *.lisp в Norvig Парадигмы программирования ИИ для общей идеи.

Ответ 12

Если у вас есть небольшой набор возможных входов, вы можете кэшировать совпадения, как они появляются во втором dict, и получить O (1) для кешированных значений.

Если набор возможных входов слишком велик для кеширования, но не бесконечен, вы можете просто сохранить последние N совпадений в кеше (проверьте Google для "карт LRU" - в последнее время используется).

Если вы не можете этого сделать, вы можете попытаться сократить количество регулярных выражений, которые вы должны попробовать, проверив префикс или немного.

Ответ 13

Я создал эту точную структуру данных для проекта один раз. Я реализовал это наивно, как вы предложили. Я сделал две чрезвычайно полезные оптимизации, которые могут быть или не могут быть осуществимы для вас, в зависимости от размера ваших данных:

• Запоминание поиска хешей
• Предварительная загрузка таблицы memoization (не уверен, что назвать это... разогрев кеш?)

Чтобы избежать проблемы с несколькими ключами, соответствующими входу, я дал каждому регулярному выражению приоритет и был использован самый высокий приоритет.

Ответ 14

Я думаю, фундаментальное предположение является ошибочным. вы не можете отображать хеши в регулярные выражения.

Ответ 15

Я не думаю, что это даже теоретически возможно. Что происходит, если кто-то передает строку, которая соответствует более чем одному регулярному выражению.

Например, что произойдет, если кто-то сделает:

>>> regex_dict['FileNfoo']

Как может быть что-то вроде O (1)?

Ответ 16

Возможно, компилятор regex может выполнить большую часть работы для вас, объединив выражения поиска в одно большое регулярное выражение, разделенное символом "|". Умный компилятор регулярных выражений может искать общности в альтернативах в таком случае и разрабатывать более эффективную стратегию поиска, чем просто проверять каждый по очереди. Но я понятия не имею, есть ли компиляторы, которые это сделают.

Ответ 17

Это зависит от того, как выглядят эти регулярные выражения. Если у вас нет много регулярных выражений, которые будут соответствовать почти любому типу ".*" или "\d+", и вместо этого у вас есть регулярные выражения, содержащие в основном слова и фразы или любые фиксированные шаблоны длиной более 4 символов (например, "a*b*c 'в ^\d+a\*b\*c:\s+\w+), как в ваших примерах. Вы можете сделать этот общий трюк, который хорошо масштабируется для миллионов регулярных выражений:

Создайте инвертированный индекс для регулярных выражений (rabin-karp-hash ('fixed pattern') → список регулярных выражений, содержащих "фиксированный шаблон" ). Затем в подходящее время, используя хеширование Рабина-Карпа, чтобы вычислить скользящие хэши и посмотреть инвертированный указатель, продвигая по одному символу за раз. Теперь у вас есть O (1) поиск обратных индексов без совпадений и разумное время O (k) для совпадений, k - средняя длина списков регулярных выражений в инвертированном индексе. k может быть довольно небольшим (менее 10) для многих приложений. Качество (ложное значение означает больший k, false negative означает пропущенные совпадения) инвертированного индекса зависит от того, насколько хорошо индексир понимает синтаксис регулярного выражения. Если регулярные выражения генерируются человеческими экспертами, они могут также давать подсказки для содержащихся фиксированных шаблонов.

Ответ 18

Хорошо, у меня очень похожие требования, у меня много строк различного синтаксиса, в основном строки замечаний и строк с некоторыми кодами для использования в процессе использования смарт-карт, а также дескрипторные строки ключей и секрет кодов, в каждом случае, я думаю, что "модель" /действие - это зверский подход, чтобы распознавать и обрабатывать множество строк.
Я использую C++/CLI для разработки моей сборки с именем LanguageProcessor.dll, ядром этой библиотеки является класс lex_rule, который в основном содержит:

• член Regex
• участник события

Конструктор загружает строку регулярного выражения и вызывает необходимые коды для создания события "на лету" с использованием DynamicMethod, Emit и Reflexion... также в сборке существует другой класс, например мета и объект, который создает ans создает объекты с помощью простых имен издателя и класса получателя, класс приемника предоставляет обработчики действий для каждого согласованного правила.

Позднее, у меня есть класс с именем 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;
        }
    }
};

Теперь класс quicklex_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:

этот код создает конструктор invoker по знаку параметра

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

наконец, код, вызывающий движок lexer:

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

Ответ 19

Проблема не имеет ничего общего с регулярными выражениями - у вас будет такая же проблема со словарем с ключами как функции lambdas. Таким образом, проблема, с которой вы сталкиваетесь, заключается в том, что вы можете классифицировать свои функции на фигуре, которая вернет true или нет, и это не проблема поиска, потому что f (x) не известно вообще в руке.

Распределенное программирование или кеширование наборов ответов, предполагающих наличие общих значений x.

- DM