python - split pandas

Filtrado de pandas para múltiples subcadenas en serie.

Question

Necesito filtrar filas en un marco de datos de pandas 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 marco de datos es grande (~ 1mio filas) y lst tiene una longitud de 100. ¿Hay alguna forma 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.

Answer 1

Podrías intentar usar el algoritmo de 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 se usa a menudo para encontrar múltiples patrones (agujas) en un texto de entrada (el pajar).

pyahocorasick es un envoltorio de Python alrededor de una implementación en C del algoritmo.

Vamos a comparar lo rápido que es frente a algunas alternativas. A continuación se muestra un punto de referencia que muestra que using_aho_corasick es más de using_aho_corasick más rápido que el método original (que se muestra en la pregunta) en un caso de prueba 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 punto de referencia. 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://.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))

Answer 2

Si te limitas a usar pandas puros, tanto para el rendimiento como para la practicidad, creo que deberías usar expresiones regulares para esta tarea. Sin embargo, primero tendrá que escapar de cualquier carácter especial en las subcadenas para asegurarse de que coincidan literalmente (y no se utilicen como metacaracteres 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 de expresiones regulares | . Cada una de las subcadenas se puede comparar con una cadena hasta que una coincida (o todas se hayan probado).

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

La etapa de enmascaramiento se convierte en un solo 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 toma aproximadamente 1 segundo (por lo tanto, 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 "peores casos" en el sentido de que no hubo coincidencias (por lo que se verificaron todas las subcadenas). Si hay coincidencias, el tiempo mejorará.