Filtrage de Pandas pour les sous-chaînes multiples dans les séries

Question

J'ai besoin de filtrer les lignes dans un pandas de sorte qu'une colonne de chaîne spécifique contienne au moins une des sous-chaînes d'une liste fournie. Les sous-chaînes peuvent contenir des caractères inhabituels / regex. La comparaison ne doit pas faire intervenir de regex et n'est pas sensible à la casse.

Par exemple :

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

Actuellement, j'applique 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 cadre de données est de grande taille (~1 million de lignes) et lst a une longueur de 100. Existe-t-il une méthode plus efficace ? Par exemple, si le premier élément de lst est trouvée, nous ne devrions pas avoir à tester les chaînes suivantes pour cette ligne.

Answer 1

Si vous vous en tenez à l'utilisation de pandas purs, pour des raisons de performance et de praticité, je pense que vous devez debe utiliser les regex pour cette tâche. Cependant, vous devrez d'abord échapper correctement tout caractère spécial dans les sous-chaînes afin de vous assurer qu'ils sont pris en compte littéralement (et non utilisés comme métacaractères de la regex).

Il est facile de le 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 pipe regex. | . Chacune des sous-chaînes peut être vérifiée par rapport à une chaîne de caractères jusqu'à ce qu'une seule corresponde (ou qu'elles aient toutes été testées).

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

L'étape de masquage devient alors une seule boucle de bas niveau à travers les rangées :

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

---

Voici une configuration simple pour avoir une idée des performances :

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 présentée dans 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 où il n'y a pas eu de correspondance (donc todo ont été vérifiées). S'il y a des correspondances, la synchronisation s'améliorera.

Answer 2

Vous pouvez essayer d'utiliser le Algorithme d'Aho-Corasick . Dans le cas moyen, c'est O(n+m+p) donde n est la longueur des chaînes de recherche et m est la longueur du texte recherché et p est le nombre de correspondances en sortie.

L'algorithme d'Aho-Corasick est le suivant souvent utilisé pour trouver plusieurs motifs (aiguilles) dans un texte d'entrée (la botte de foin).

pyahocorasick est une enveloppe Python autour d'une implémentation C de l'algorithme.

---

Comparons sa rapidité à celle de quelques autres solutions. Voici un benchmark montrant using_aho_corasick pour être plus de 30x plus rapide que la méthode originale (indiquée dans la question) sur un cas de test DataFrame de 50 000 lignes :

|                    |     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 retourné 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))

Answer 3

Utilisation d'un exemple plus simple & ignorer le cas (majuscules ou minuscules)

Filtrage et obtention d'un vecteur binaire :

Je veux trouver tous les éléments d'un pd.Series , v qui contiennent "at" ou "Og". On obtient 1 si l'élément contient le motif ou 0 s'il ne le contient pas.

Je vais utiliser le re :

import re

Mon vecteur :

v=pd.Series(['cAt','dog','the rat','mouse','froG'])

[Out]:

0        cAt
1        dog
2    the rat
3      mouse
4       froG

Je veux trouver tous les éléments de v qui contiennent "at" ou "Og". Ainsi, je peux définir mon pattern como:

pattern='at|Og'

Puisque je veux un vecteur avec des 1 si l'article contient le motif ou 0 s'il ne le contient pas.

Je crée un vecteur unitaire de la même longueur que v :

v_binary=[1]*len(v)

J'obtiens un booléen s c'est-à-dire True si un élément de v contient le pattern ou False s'il ne le contient pas.

s=v.str.contains(pattern, flags=re.IGNORECASE, regex=True)

Pour obtenir le vecteur binaire, je multiplie le v_binary * s :

v_binary*s

[Out]

0    1
1    1
2    1
3    0
4    1