База данных или структура, подходящая для соответствующих строк к regex шаблонам

Question

База данных или структура, подходящая для соответствующих строк к regex шаблонам

import numpy as np
import cv2

data = [1, 5, 3, 9 ,4] # fill in your data

size = 200, 300, 3
hist = np.zeros(size, dtype=np.uint8) + 255

interval = hist.shape[1] / (len(data) + 1)
width = interval * 0.7
max_height = hist.shape[0] * 0.9
max_data = max(data)

interval_count = 1
for value in data:
    height = max_height / max_data * value
    pt1 = (int(interval_count * interval - width / 2), int(hist.shape[0] - height))
    pt2 = (int(interval_count * interval + width / 2), int(hist.shape[0]))
    cv2.rectangle(hist, pt1, pt2, (255, 0, 0), -1)
    interval_count += 1

cv2.imwrite("hist.jpg", hist)

6

data-structures search regex database

задан Borodin 31 May 2016 в 14:52

2 ответа

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

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

Например, если Ваши входные строки могут быть чем-нибудь произвольно комплекс, и у Вас есть тысячи regexes, Вы могли организовать их в категориях как:

\d+ категория, которая протестировала бы шаблоны числа (SSN, номера телефона и т.д.)
<.*?> категория, которая протестировала бы присутствие HTML-тэгов
\w+@\w+ категория, которая могла протестировать присутствие почтовых адресов

и т.д.

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

Не знайте, соответствовало ли это Вашему точному домену, но это - возможная оптимизация.

2

ответ дан 17 December 2019 в 00:15

Другие вопросы по тегам:

data-structures search regex database

Похожие вопросы:

score 5 · Accepted Answer

Короткий ответ является 'Нет'. Нет никакой индексной структуры, в настоящее время доступной ни на какой платформе DBMS, которая индексирует частичные соответствия regex как это.

Длинный ответ то, что продвижение, постоянное на подстановочном соответствии (например. 'foo_') может использоваться в качестве префикса для индексных соответствий. Много платформ DBMS будут оптимизировать это и использовать индекс (при наличии) для разрешения префикса. Однако это - ничто как столь же умный как полный regex, и индексация может только использоваться, если у Вас есть постоянный префикс.

Еще более длинный ответ - то, что существуют алгоритмы, такие как СЕТЬ, которая оптимизирует частичные соответствия как это. Это могло бы быть применимо, если можно выразить соответствия как порождающие правила прямой цепочки рассуждений, а не регулярные выражения.

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