Filtrado de pandas para múltiples subcadenas en serie

Question

Filtrado de pandas para múltiples subcadenas en serie

Necesito filtrar filas en un pandas dataframe para que una columna de cadena específica contenga al menos una de una lista de subcadenas proporcionadas. Las subcadenas pueden tener caracteres inusuales / regex. La comparación no debe incluir expresiones regulares y no distingue entre mayúsculas y minúsculas.

Por ejemplo:

lst = ['kdSj;af-!?', 'aBC+dsfa?\-', 'sdKaJg|dksaf-*']

Actualmente aplico la máscara de esta manera:

mask = np.logical_or.reduce([df[col].str.contains(i, regex=False, case=False) for i in lst])
df = df[mask]

Mi dataframe es grande (~filas 1mio) y lst tiene una longitud de 100. ¿Hay una manera más eficiente? Por ejemplo, si se encuentra el primer elemento en lst , no deberíamos tener que probar ninguna cadena posterior para esa fila.

23

python string dataframe pandas series

Author: jpp, 2018-01-31

Source

2 answers

Puedes intentar usar el algoritmo Aho-Corasick. En el caso promedio, es O(n+m+p) donde n es la longitud de las cadenas de búsqueda y m es la longitud del texto buscado y p es el número de coincidencias de salida.

El algoritmo Aho-Corasick es a menudo utilizado para encontrar múltiples patrones (agujas) en un texto de entrada (el pajar).

Pyahocorasick es un wrapper de Python alrededor de una implementación en C del algoritmo.

Vamos a compare qué tan rápido es versus algunas alternativas. A continuación se muestra un punto de referencia mostrando que using_aho_corasick es más de 30 veces más rápido que el método original (se muestra en la pregunta) en un caso de prueba de DataFrame de 50K filas:

|                    |     speed factor | ms per loop |
|                    | compared to orig |             |
|--------------------+------------------+-------------|
| using_aho_corasick |            30.7x |         140 |
| using_regex        |             2.7x |        1580 |
| orig               |             1.0x |        4300 |

In [89]: %timeit using_ahocorasick(col, lst)
10 loops, best of 3: 140 ms per loop

In [88]: %timeit using_regex(col, lst)
1 loop, best of 3: 1.58 s per loop

In [91]: %timeit orig(col, lst)
1 loop, best of 3: 4.3 s per loop

Aquí la configuración utilizada para el benchmark. También verifica que la salida coincida con el resultado devuelto por orig:

import numpy as np
import random
import pandas as pd
import ahocorasick
import re

random.seed(321)

def orig(col, lst):
    mask = np.logical_or.reduce([col.str.contains(i, regex=False, case=False) 
                                 for i in lst])
    return mask

def using_regex(col, lst):
    """https://stackoverflow.com/a/48590850/190597 (Alex Riley)"""
    esc_lst = [re.escape(s) for s in lst]
    pattern = '|'.join(esc_lst)
    mask = col.str.contains(pattern, case=False)
    return mask

def using_ahocorasick(col, lst):
    A = ahocorasick.Automaton(ahocorasick.STORE_INTS)
    for word in lst:
        A.add_word(word.lower())
    A.make_automaton() 
    col = col.str.lower()
    mask = col.apply(lambda x: bool(list(A.iter(x))))
    return mask

N = 50000
# 100 substrings of 5 characters
lst = [''.join([chr(random.randint(0, 256)) for _ in range(5)]) for _ in range(100)]

# N strings of 20 characters
strings = [''.join([chr(random.randint(0, 256)) for _ in range(20)]) for _ in range(N)]
# make about 10% of the strings match a string from lst; this helps check that our method works
strings = [_ if random.randint(0, 99) < 10 else _+random.choice(lst) for _ in strings]

col = pd.Series(strings)

expected = orig(col, lst)
for name, result in [('using_regex', using_regex(col, lst)),
                     ('using_ahocorasick', using_ahocorasick(col, lst))]:
    status = 'pass' if np.allclose(expected, result) else 'fail'
    print('{}: {}'.format(name, status))

31

Author: unutbu,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-02-07 22:21:51

score 29 · Accepted Answer

Si te apegas a usar pure-pandas, tanto para el rendimiento como para la practicidad creo que debería usar expresiones regulares para esta tarea. Sin embargo, primero deberá escapar correctamente cualquier carácter especial en las subcadenas para asegurarse de que coincidan literalmente (y no se usen como caracteres meta de expresiones regulares).

Esto es fácil de hacer usando re.escape:

>>> import re
>>> esc_lst = [re.escape(s) for s in lst]

Estas subcadenas escapadas se pueden unir usando una tubería regex |. Cada una de las subcadenas se puede comprobar contra una cadena hasta que una coincida (o todas hayan sido probadas).

>>> pattern = '|'.join(esc_lst)

La etapa de enmascaramiento se convierte entonces en un único bucle de bajo nivel a través de las filas:

df[col].str.contains(pattern, case=False)

Aquí hay una configuración simple para obtener una sensación de rendimiento:

from random import randint, seed

seed(321)

# 100 substrings of 5 characters
lst = [''.join([chr(randint(0, 256)) for _ in range(5)]) for _ in range(100)]

# 50000 strings of 20 characters
strings = [''.join([chr(randint(0, 256)) for _ in range(20)]) for _ in range(50000)]

col = pd.Series(strings)
esc_lst = [re.escape(s) for s in lst]
pattern = '|'.join(esc_lst)

El método propuesto tarda aproximadamente 1 segundo (así que tal vez hasta 20 segundos para 1 millón de filas):

%timeit col.str.contains(pattern, case=False)
1 loop, best of 3: 981 ms per loop

El método en la pregunta tomó aproximadamente 5 segundos usando los mismos datos de entrada.

Vale la pena señalar que estos tiempos son 'el peor de los casos' en el sentido de que no hubo coincidencias (por lo que todas las subcadenas fueron verificadas). Si hay partidos que el tiempo mejorará.