Pandas filtrage pour plusieurs sous-chaînes en série
J'ai besoin de filtrer les lignes dans un dataframe pandas de sorte qu'une colonne de chaîne spécifique contienne au moins l'une d'une liste de sous-chaînes fournies. Les sous-chaînes peuvent avoir des caractères inhabituels / regex. La comparaison ne doit pas impliquer regex et est insensible à la casse.
Par exemple:
lst = ['kdSj;af-!?', 'aBC+dsfa?-', 'sdKaJg|dksaf-*']
J'applique actuellement le masque comme ceci:
mask = np.logical_or.reduce([df[col].str.contains(i, regex=False, case=False) for i in lst])
df = df[mask]
Mon dataframe est grand (~1mio lignes) et lst a la longueur 100. Est-il un moyen plus efficace? Par exemple, si le premier élément de lst est trouvé, nous ne devrions pas avoir à tester les chaînes suivantes pour cette ligne.
2 réponses
Si vous vous en tenez à l'utilisation de pandas purs, pour la performance et la praticité, je pense que vous devriez utiliser regex pour cette tâche. Cependant, vous devrez d'abord échapper correctement les caractères spéciaux dans les sous-chaînes pour vous assurer qu'ils correspondent littéralement (et ne sont pas utilisés comme méta-caractères regex).
C'est facile à faire en utilisant re.escape:
>>> import re
>>> esc_lst = [re.escape(s) for s in lst]
Ces sous-chaînes échappées peuvent ensuite être jointes à l'aide d'un tube regex |. Chacune des sous-chaînes peut être vérifiée contre une chaîne jusqu'à ce qu'une correspondance (ou ils ont tous été testés).
>>> pattern = '|'.join(esc_lst)
L'étape de masquage devient alors une seule boucle de bas niveau à travers les lignes:
df[col].str.contains(pattern, case=False)
Voici une configuration simple pour avoir une idée de la performance:
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)
La méthode proposée prend environ 1 seconde (donc peut-être jusqu'à 20 secondes pour 1 million de lignes):
%timeit col.str.contains(pattern, case=False)
1 loop, best of 3: 981 ms per loop
La méthode de la question a pris environ 5 secondes en utilisant les mêmes données d'entrée.
Il est intéressant de noter que ces temps sont "le pire des cas" dans le sens qu'il n'y avait pas de correspondances (donc toutes les sous-chaînes ont été vérifiées). S'il y a des matchs que le calendrier s'améliorera.
Vous pouvez essayer d'utiliser l'algorithme Aho-Corasick . Dans la moyenne des cas, il est O(n+m+p) où n est la longueur des chaînes de recherche et de m est la longueur du texte recherché et p est le nombre de sortie correspond.
L'algorithme Aho-Corasick est souvent utilisé pour trouver plusieurs motifs (aiguilles) dans un texte d'entrée (la botte de foin).
Pyahocorasick {[11] } est un wrapper Python autour d'une implémentation C de l'algorithme.
Allons-y. comparez à quelle vitesse il est par rapport à certaines alternatives. Ci-dessous est une référence
afficher using_aho_corasick Plus de 30 fois plus rapide que la méthode originale
(montré dans la question) sur un cas de test de DataFrame de 50K-row:
| | 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
Voici la configuration utilisée pour le benchmark. Il vérifie également que la sortie correspond au résultat renvoyé par 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))