Поиск хеш-таблицы/словаря/карты с регулярными выражениями

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

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

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

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

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

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

>>> regex_dict['FileNfoo']

, Как чему-то может понравиться это возможно быть O (1)?

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

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

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

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

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

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

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

Существует модуль Perl, который делает просто этот Связь:: Хеш:: 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};

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

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

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

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

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

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

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

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

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

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

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

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

В общем случае, в чем Вы нуждаетесь, генератор лексического анализатора. Это берет набор регулярных выражений и компилирует их в устройство распознавания. "закон" будет работать при использовании C. Я никогда не использовал генератор лексического анализатора в Python, но там, кажется, некоторые для выбора из. Шоу Google СГИБ , PyGgy и PyLexer.

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

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

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

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