Hashtable / словарь / поиск карты с регулярными выражениями - PullRequest
20 голосов
/ 04 ноября 2008

Я пытаюсь выяснить, есть ли достаточно эффективный способ выполнить поиск в словаре (или хэше, или карте, или как там ваш любимый язык называет это), где ключи являются регулярными выражениями, а строки ищутся против набора ключей. Например (в синтаксисе 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). Кроме того, базовая структура данных может быть любой, но я хотел бы описать базовое поведение, описанное выше: поиск строки и возврат значений, соответствующих ключам регулярного выражения.

Ответы [ 19 ]

1 голос
/ 04 ноября 2008

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

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

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

1 голос
/ 04 ноября 2008

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

1 голос
/ 06 ноября 2008

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

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

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

0 голосов
/ 04 ноября 2008

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

0 голосов
/ 04 ноября 2008

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

Например, что случилось бы, если бы кто-то сделал:

>>> regex_dict['FileNfoo']

Как такое может быть O (1)?

0 голосов
/ 17 апреля 2012

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

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

- DM

0 голосов
/ 29 апреля 2011

Хорошо, у меня очень похожие требования, у меня много строк с разным синтаксисом, в основном строки с пометками и строки с некоторыми кодами для использования в процессе формата смарт-карт, а также строки дескрипторов ключей и секретов. коды, в любом случае, я думаю, что «модель» шаблон / действие - это зверский подход для распознавания и обработки большого количества строк.
Я использую 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;
        }
    }
};

Теперь класс fastlex_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();
0 голосов
/ 04 ноября 2008

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

0 голосов
/ 04 ноября 2008

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

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

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