Hashtable / словарь / поиск карты с регулярными выражениями

Question

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

Answer 1

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

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

Answer 2

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

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

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

Answer 3

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

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

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

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

В Perl есть пара Text :: Trie-подобных модулей, которые вы можете использовать для поиска идей. (Черт возьми, я даже написал одну из них когда-то)

Answer 4

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

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

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

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

Answer 6

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

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

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

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

Answer 7

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

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

Answer 9

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

Answer 10

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

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

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