regulares - regular expression python
Búsqueda Hashtable/diccionario/mapa con expresiones regulares (19)
Estoy tratando de averiguar si hay una forma razonablemente eficiente de realizar una búsqueda en un diccionario (o un hash, o un mapa, o como lo llame su idioma favorito) donde las claves son expresiones regulares y las cadenas se buscan contra el conjunto de llaves. Por ejemplo (en sintaxis de 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
(Obviamente, el ejemplo anterior no funcionará como está escrito en Python, pero ese es el tipo de cosas que me gustaría poder hacer).
Puedo pensar en una forma ingenua de implementar esto, en la que iterar sobre todas las claves del diccionario e intentar hacer coincidir la cadena pasada en contra de ellas, pero luego pierdo el tiempo de búsqueda O (1) de un mapa hash y en cambio, tiene O (n), donde n es el número de teclas en mi diccionario. Esto es potencialmente un gran problema, ya que espero que este diccionario crezca mucho, y tendré que buscarlo una y otra vez (en realidad tendré que repetirlo sobre cada línea que leo en un archivo de texto, y los archivos pueden tener cientos de megabytes de tamaño).
¿Hay alguna manera de lograr esto sin recurrir a la eficiencia O (n)?
Alternativamente, si conoce una forma de realizar este tipo de búsqueda en una base de datos, también sería genial.
(Cualquier lenguaje de programación está bien; estoy usando Python, pero estoy más interesado en las estructuras de datos y los algoritmos aquí).
Alguien señaló que es posible más de una coincidencia, y eso es absolutamente correcto. Idealmente en esta situación me gustaría devolver una lista o tupla que contenga todas las coincidencias. Me conformaría con el primer partido, sin embargo.
No puedo ver que O (1) sea posible en ese escenario; Me conformaría con algo menos que O (n), sin embargo. Además, la estructura de datos subyacente podría ser cualquier cosa, pero el comportamiento básico que me gustaría es el que he escrito anteriormente: buscar una cadena y devolver los valores que coinciden con las claves de expresión regulares.
¿Qué hay de lo siguiente?
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)
Básicamente es una subclase del tipo dict en Python. Con esto puede proporcionar una expresión regular como clave, y los valores de todas las claves que coinciden con esta expresión regular se devuelven de forma iterativa utilizando rendimiento.
Con esto puedes hacer lo siguiente:
>>> 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
>>>
¿Qué sucede si tienes un diccionario como
regex_dict = { re.compile("foo.*"): 5, re.compile("f.*"): 6 }
En este caso, regex_dict["food"] podría legítimamente devolver 5 o 6.
Incluso ignorando ese problema, probablemente no haya forma de hacerlo de manera eficiente con el módulo de expresiones regulares. En cambio, lo que necesitarías es un gráfico interno dirigido o una estructura de árbol.
@ rptb1 no tiene que evitar la captura de grupos, porque puede usar re.groups para contarlos. Me gusta esto:
# 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()
Lamentablemente, muy pocos motores de RE compilan las expresiones regulares hasta el código de máquina, aunque no es especialmente difícil de hacer. Sospecho que hay una mejora en el rendimiento del orden de magnitud esperando a que alguien haga una buena biblioteca RE JIT.
Como otros encuestados han señalado, no es posible hacer esto con una tabla hash en tiempo constante.
Una aproximación que podría ayudar es usar una técnica llamada "n-grams" . Crea un índice invertido de trozos de n caracteres de una palabra a la palabra completa. Cuando se le presente un patrón, divídalo en trozos de n caracteres y use el índice para calcular una lista de palabras coincidentes.
Incluso si no puede aceptar una aproximación, en la mayoría de los casos esto proporcionaría un mecanismo de filtrado preciso para que no tenga que aplicar la expresión regular a cada tecla.
Creé esta estructura de datos exacta para un proyecto una vez. Lo implementé ingenuamente, como sugirió. Hice dos optimizaciones inmensamente útiles, que pueden o no ser factibles para usted, dependiendo del tamaño de sus datos:
- Memorando las búsquedas de hash
- Preselección de la tabla de memorización (no estoy seguro de cómo llamar esto ... ¿se está calentando la memoria caché?)
Para evitar el problema de tener varias claves que coincidan con la entrada, le di a cada clave regex una prioridad y se utilizó la más alta prioridad.
El problema no tiene nada que ver con las expresiones regulares: tendrías el mismo problema con un diccionario con teclas como funciones de lambdas. Entonces, el problema al que se enfrenta es imaginar que hay una forma de clasificar sus funciones para calcular cuál será verdadera o no y eso no es un problema de búsqueda porque f (x) no se conoce en general de antemano.
La programación distribuida o los conjuntos de respuestas de caché suponiendo que hay valores comunes de x pueden ser útiles.
- DM
En el caso general, lo que necesita es un generador lexer. Toma un montón de expresiones regulares y las compila en un reconocedor. "lex" funcionará si está utilizando C. Nunca he usado un generador de lexer en Python, pero parece que hay algunos para elegir. Google muestra PLY , PyGgy y PyLexer .
Si las expresiones regulares se parecen entre sí de alguna manera, entonces puede tomar algunos atajos. Necesitaríamos saber más sobre el problema final que está tratando de resolver para encontrar cualquier sugerencia. ¿Puedes compartir algunas expresiones regulares de muestra y algunos datos de muestra?
Además, ¿con cuántas expresiones regulares estás tratando aquí? ¿Estás seguro de que el enfoque ingenuo no funcionará? Como dijo Rob Pike una vez , "los algoritmos de lujo son lentos cuando n es pequeño, y n es usualmente pequeño". A menos que tengas miles de expresiones regulares y miles de cosas para hacer coincidir con ellas, y esta es una aplicación interactiva en la que un usuario te está esperando, es mejor que lo hagas de la manera más fácil y repitiendo las expresiones regulares.
Es posible que el compilador de expresiones regulares haga la mayor parte del trabajo por usted al concatenar las expresiones de búsqueda en una gran expresión regular, separadas por "|". Un compilador de expresiones regulares inteligente podría buscar aspectos comunes en las alternativas en ese caso, y diseñar una estrategia de búsqueda más eficiente que simplemente verificar cada una por turno. Pero no tengo idea si hay compiladores que harán eso.
Esta es una forma eficiente de hacerlo combinando las claves en una sola expresión regular compilada, y por lo tanto no requiere ningún bucle sobre patrones clave. Abusa del lastindex para descubrir qué clave coincide. (Es una pena que las bibliotecas regexp no le permitan etiquetar el estado terminal del DFA en el que se compila una expresión regular, o esto sería menos pirateo).
La expresión se compila una vez y producirá un marcador rápido que no tiene que buscarse secuencialmente. Los prefijos comunes se compilan juntos en el DFA, por lo que cada carácter de la clave se combina una vez, no muchas veces, a diferencia de algunas de las otras soluciones sugeridas. Está compilando efectivamente un mini lexer para su espacio de claves.
Este mapa no es extensible (no puede definir nuevas claves) sin recompilar la expresión regular, pero puede ser útil para algunas situaciones.
# 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'']
Esto definitivamente es posible, siempre y cuando uses expresiones regulares ''reales''. Una expresión regular de libro de texto es algo que puede ser reconocido por una máquina determinista de estado finito , lo que significa principalmente que no puede haber referencias retrospectivas allí.
Existe la propiedad de los lenguajes comunes de que "la unión de dos idiomas regulares es regular", lo que significa que puede reconocer un número arbitrario de expresiones regulares a la vez con una máquina de estados única. La máquina de estados se ejecuta en O (1) tiempo con respecto al número de expresiones (se ejecuta en O (n) tiempo con respecto a la longitud de la cadena de entrada, pero las tablas hash también).
Una vez que la máquina de estado finalice, sabrá qué expresiones coinciden, y desde allí es fácil buscar valores en O (1) tiempo.
Esto no es posible con una tabla hash regular en ningún idioma. Deberá iterar a través de todo el conjunto de claves, intentar hacer coincidir la clave con su expresión regular o utilizar una estructura de datos diferente.
Debe elegir una estructura de datos que sea apropiada para el problema que está tratando de resolver. Si tiene que coincidir con cualquier expresión regular arbitraria, no sé de una buena solución. Si la clase de expresiones regulares que usará es más restrictiva, es posible que pueda usar una estructura de datos como un árbol trie o sufijo .
Hay un módulo Perl que hace justo esto 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};
La suposición fundamental es defectuosa, creo. no puede asignar hashes a expresiones regulares.
Lo que quiere hacer es muy similar a lo que es compatible con xrdb. Sin embargo, solo respaldan una noción bastante mínima de globbing.
Internamente puede implementar una familia más grande de idiomas regulares que los suyos almacenando sus expresiones regulares como un trie de personaje.
- los caracteres individuales se convierten en trie nodos.
- . se convierten en inserciones comodín que cubren todos los hijos del nodo trie actual.
- * se vuelven enlaces en el trie al nodo al inicio del artículo anterior.
- los intervalos [az] insertan los mismos nodos hijos subsiguientes repetidamente debajo de cada uno de los caracteres del rango. Con cuidado, aunque las inserciones / actualizaciones pueden ser algo costosas, la búsqueda puede ser lineal en el tamaño de la cadena. Con algunas cosas de marcador de posición, los casos comunes de explosión combinatoria pueden mantenerse bajo control.
- Los nodos (foo) | (barra) se convierten en varias inserciones
Esto no maneja las expresiones regulares que ocurren en puntos arbitrarios en la cadena, pero eso se puede modelar envolviendo su expresión regular con. * En cualquier lado.
Perl tiene un par de módulos similares a Text :: Trie que puedes atacar en busca de ideas. (Diablos, creo que incluso escribí uno de ellos mucho cuando)
No creo que sea teóricamente posible. ¿Qué sucede si alguien pasa una cadena que coincide con más de 1 expresión regular?
Por ejemplo, ¿qué pasaría si alguien lo hiciera?
>>> regex_dict[''FileNfoo'']
¿Cómo puede ser que algo así sea O (1)?
Ok, tengo requisitos muy similares, tengo muchas líneas de sintaxis diferente, básicamente líneas y líneas de observación con algunos códigos para usar en un proceso de formato de tarjeta inteligente, también, líneas descriptivas de claves y códigos secretos, en En cada caso, creo que el patrón / acción "modelo" es el enfoque bestial para reconocer y procesar muchas líneas.
Estoy usando C++/CLI para desarrollar mi ensamblado denominado LanguageProcessor.dll , el núcleo de esta biblioteca es una clase lex_rule que básicamente contiene:
- un miembro de Regex
- un miembro del evento
El constructor carga la cadena de expresiones regulares y llama a los códigos necesarios para construir el evento sobre la marcha usando DynamicMethod , Emit y Reflexion ... también en el ensamblado existe otra clase como meta y object que construye y ejemplifica los objetos por los simples nombres de el editor y la clase receptora, clase de receptor, proporciona los controladores de acción para cada regla coincidente.
Tarde, tengo una clase llamada fasterlex_engine que construye un diccionario <Regex, action_delegate> que carga las definiciones de una matriz para ejecutar.
El proyecto está en un punto avanzado, pero todavía estoy construyendo, hoy. Voy a tratar de mejorar el rendimiento de la ejecución que rodea el acceso secuencial a cada par de entrada de línea foreach, mediante el uso de algún mecanismo de búsqueda del diccionario directamente usando la expresión regular como:
map_rule[gcnew Regex("[a-zA-Z]")];
Aquí, algunos de los segmentos de mi código:
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;
}
}
};
Ahora la clase fasterlex_engine que ejecuta una gran cantidad de par patrón / acción:
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();
};
Y PARA DECORAR ESTE TEMA ... un código de mi archivo cpp:
este código crea un invocador de constructor por signo de parámetro
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;
}
Este código adjunta una función de controlador (estático o no) para tratar una devolución de llamada generada por la coincidencia de una cadena de entrada
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;
}
finalmente el código que llama al motor 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();
Realmente depende de cómo se vean estas expresiones regulares. Si no tiene muchas expresiones regulares que coincidan con casi cualquier cosa como '' .* '' O '' /d+ '', y en su lugar tiene expresiones regulares que contienen principalmente palabras y frases o cualquier patrón fijo de más de 4 caracteres (por ejemplo, '' a*b*c ''en ^/d+a/*b/*c:/s+/w+ ), como en sus ejemplos. Puedes hacer este truco común que se adapta bien a millones de expresiones regulares:
Construya un índice invertido para las expresiones regulares (rabin-karp-hash (''patrón fijo'') -> lista de expresiones regulares que contienen ''patrón fijo''). Luego, en el tiempo de coincidencia, usando hash Rabin-Karp para calcular hashes deslizantes y buscar el índice invertido, avanzando un carácter a la vez. Ahora tiene O (1) búsqueda de no-coincidencias de índice invertido y un tiempo de O (k) razonable para las coincidencias, k es la longitud promedio de las listas de expresiones regulares en el índice invertido. k puede ser bastante pequeño (menos de 10) para muchas aplicaciones. La calidad (falso positivo significa mayor k, falso negativo significa falta de coincidencia) del índice invertido depende de qué tan bien el indexador entiende la sintaxis de la expresión regular. Si los regexes son generados por expertos humanos, también pueden proporcionar pistas sobre patrones fijos contenidos.
Si tiene un pequeño conjunto de entradas posibles, puede almacenar en caché las coincidencias tal como aparecen en un segundo diccionario y obtener O (1) para los valores en caché.
Si el conjunto de posibles entradas es demasiado grande para almacenar en caché pero no infinito, puede mantener las últimas N coincidencias en la memoria caché (busque en Google "LRU maps", que se utilizó por lo menos recientemente).
Si no puede hacer esto, puede intentar reducir el número de expresiones regulares que debe probar marcando un prefijo o un poco.
Un caso especial de este problema surgió en los 70s lenguajes de IA orientados a bases de datos deductivas. Las claves en estas bases de datos podrían ser patrones con variables, como expresiones regulares sin * o | operadores. Tienden a usar extensiones de lujo de las estructuras para los índices. Vea krep * .lisp en Norvig''s Paradigms of AI Programming para la idea general.