Acelera millones de reemplazos de expresiones regulares en Python 3

127

Estoy usando Python 3.5.2

Tengo dos listas

  • una lista de aproximadamente 750,000 "oraciones" (cadenas largas)
  • una lista de aproximadamente 20,000 "palabras" que me gustaría eliminar de mis 750,000 oraciones

Entonces, tengo que recorrer 750,000 oraciones y realizar alrededor de 20,000 reemplazos, pero SOLO si mis palabras son en realidad "palabras" y no son parte de una cadena de caracteres más grande.

Estoy haciendo esto al precompilar mis palabras para que estén flanqueadas por el \bmetacarácter

compiled_words = [re.compile(r'\b' + word + r'\b') for word in my20000words]

Luego recorro mis "oraciones"

import re

for sentence in sentences:
  for word in compiled_words:
    sentence = re.sub(word, "", sentence)
  # put sentence into a growing list

Este bucle anidado procesa alrededor de 50 oraciones por segundo , lo cual es bueno, pero aún tarda varias horas en procesar todas mis oraciones.

  • ¿Hay alguna manera de usar el str.replacemétodo (que creo que es más rápido), pero que aún requiere que los reemplazos solo sucedan en los límites de las palabras ?

  • Alternativamente, ¿hay alguna manera de acelerar el re.submétodo? Ya he mejorado la velocidad marginalmente saltando re.subsi la longitud de mi palabra es> que la longitud de mi oración, pero no es una gran mejora.

Gracias por cualquier sugerencia

python regex string performance replace pdanese
fuente
1
La primera respuesta aquí tiene un buen código de muestra: stackoverflow.com/questions/2846653/… solo divida su matriz de oraciones por el número de núcleos de CPU que luego ha ejecutado tantos hilos
Mohammad Ali
44
También puede probar una implementación sin expresiones regulares: recorra su entrada palabra por palabra y combine cada una con un conjunto. Esta es una sola pasada y las búsquedas de hash son bastante rápidas.
pvg
2
¿Cuánto tiempo duran estas oraciones, por cierto? Las líneas de 750k no suenan como un conjunto de datos que debería tardar horas en procesarse.
pvg
2
@MohammadAli: No te molestes con ese ejemplo para el trabajo vinculado a la CPU. Python tiene un gran bloqueo que se necesita al ejecutar bytecode (el bloqueo global del intérprete), por lo que no puede beneficiarse de los hilos para el trabajo de la CPU. Necesitaría usar multiprocessing(es decir, múltiples procesos de Python).
Kevin
1
Necesitas una herramienta de fuerza industrial para hacer esto. Un regex trie se genera a partir de un árbol ternario de una lista de cadenas. Nunca hay más de 5 pasos para fallar, por lo que este es el método más rápido para hacer este tipo de coincidencia. Ejemplos: 175,000 diccionario de palabras o similar a su lista prohibida solo las 20,000 palabras S
x15

Respuestas:

123

Una cosa que puedes probar es compilar un patrón único como "\b(word1|word2|word3)\b".

Debido a que se rebasa en el código C para hacer la coincidencia real, los ahorros pueden ser dramáticos.

Como @pvg señaló en los comentarios, también se beneficia de la coincidencia de un solo paso.

Si sus palabras no son expresiones regulares, la respuesta de Eric es más rápida.

Liteye
fuente
44
No es solo el C impl (que hace una gran diferencia) sino que también está haciendo coincidir con un solo pase. Las variantes de esta pregunta surgen con bastante frecuencia, es un poco extraño que no haya (¿o tal vez la hay, escondiéndose en algún lugar?) Una respuesta canónica de SO con esta idea bastante sensible.
pvg
40
¡@Liteye su sugerencia convirtió un trabajo de 4 horas en un trabajo de 4 minutos! Pude unir todas las más de 20,000 expresiones regulares en una única expresión regular gigantesca y mi computadora portátil no pestañeó. Gracias de nuevo.
pdanese
2
@Bakuriu: s/They actually use/They actually could in theory sometimes use/. ¿Tiene alguna razón para creer que la implementación de Python está haciendo algo más que un bucle aquí?
user541686
2
@Bakuriu: Me interesaría saber si ese es el caso, pero no creo que la solución de expresiones regulares tome tiempo lineal. Si no crea un Trie fuera del sindicato, no veo cómo podría suceder.
Eric Duminil
2
@Bakuriu: Esa no es una razón. Le preguntaba si tiene una razón para creer que la implementación realmente se comporta de esa manera, no si tiene una razón para creer que podría comportarse de esa manera. Personalmente, todavía tengo que encontrar la implementación de expresiones regulares de un solo lenguaje de programación convencional que funcione en tiempo lineal de la misma manera que esperarías que una expresión regular clásica, así que si sabes que Python hace esto, debes mostrar alguna evidencia.
user541686
123

TLDR

Use este método (con búsqueda establecida) si desea la solución más rápida. Para un conjunto de datos similar a los OP, es aproximadamente 2000 veces más rápido que la respuesta aceptada.

Si insiste en usar una expresión regular para la búsqueda, use esta versión basada en trie , que aún es 1000 veces más rápida que una unión de expresión regular.

Teoría

Si sus oraciones no son cadenas enormes, probablemente sea factible procesar muchas más de 50 por segundo.

Si guarda todas las palabras prohibidas en un conjunto, será muy rápido verificar si se incluye otra palabra en ese conjunto.

Empaque la lógica en una función, asigne esta función como argumento para re.sub y listo!

Código

import re
with open('/usr/share/dict/american-english') as wordbook:
    banned_words = set(word.strip().lower() for word in wordbook)


def delete_banned_words(matchobj):
    word = matchobj.group(0)
    if word.lower() in banned_words:
        return ""
    else:
        return word

sentences = ["I'm eric. Welcome here!", "Another boring sentence.",
             "GiraffeElephantBoat", "sfgsdg sdwerha aswertwe"] * 250000

word_pattern = re.compile('\w+')

for sentence in sentences:
    sentence = word_pattern.sub(delete_banned_words, sentence)

Las oraciones convertidas son:

' .  !
  .
GiraffeElephantBoat
sfgsdg sdwerha aswertwe

Tenga en cuenta que:

  • la búsqueda no distingue entre mayúsculas y minúsculas (gracias a lower() )
  • reemplazando una palabra con "" podría dejar dos espacios (como en su código)
  • Con python3, \w+también coincide con los caracteres acentuados (p. Ej."ångström" . .).
  • Cualquier carácter que no sea de palabra (tabulación, espacio, nueva línea, marcas, ...) permanecerá intacto.

Actuación

Hay un millón de oraciones, banned_wordstiene casi 100000 palabras y el script se ejecuta en menos de 7 segundos.

En comparación, la respuesta de Liteye necesitaba 160 para 10 mil oraciones.

Al nser la cantidad total de palabras y mla cantidad de palabras prohibidas, los códigos de OP y Liteye sonO(n*m) .

En comparación, mi código debería ejecutarse O(n+m). Teniendo en cuenta que hay muchas más oraciones que palabras prohibidas, el algoritmo se convierte enO(n) .

Prueba de unión de expresiones regulares

¿Cuál es la complejidad de una búsqueda de expresiones regulares con un '\b(word1|word2|...|wordN)\b'patrón? Es O(N)oO(1) ?

Es bastante difícil comprender la forma en que funciona el motor de expresiones regulares, así que escribamos una prueba simple.

Este código extrae 10**ipalabras inglesas al azar en una lista. Crea la unión regex correspondiente y la prueba con diferentes palabras:

  • uno claramente no es una palabra (comienza con #)
  • una es la primera palabra en la lista
  • una es la última palabra en la lista
  • uno parece una palabra pero no lo es


import re
import timeit
import random

with open('/usr/share/dict/american-english') as wordbook:
    english_words = [word.strip().lower() for word in wordbook]
    random.shuffle(english_words)

print("First 10 words :")
print(english_words[:10])

test_words = [
    ("Surely not a word", "#surely_NöTäWORD_so_regex_engine_can_return_fast"),
    ("First word", english_words[0]),
    ("Last word", english_words[-1]),
    ("Almost a word", "couldbeaword")
]


def find(word):
    def fun():
        return union.match(word)
    return fun

for exp in range(1, 6):
    print("\nUnion of %d words" % 10**exp)
    union = re.compile(r"\b(%s)\b" % '|'.join(english_words[:10**exp]))
    for description, test_word in test_words:
        time = timeit.timeit(find(test_word), number=1000) * 1000
        print("  %-17s : %.1fms" % (description, time))

Produce:

First 10 words :
["geritol's", "sunstroke's", 'fib', 'fergus', 'charms', 'canning', 'supervisor', 'fallaciously', "heritage's", 'pastime']

Union of 10 words
  Surely not a word : 0.7ms
  First word        : 0.8ms
  Last word         : 0.7ms
  Almost a word     : 0.7ms

Union of 100 words
  Surely not a word : 0.7ms
  First word        : 1.1ms
  Last word         : 1.2ms
  Almost a word     : 1.2ms

Union of 1000 words
  Surely not a word : 0.7ms
  First word        : 0.8ms
  Last word         : 9.6ms
  Almost a word     : 10.1ms

Union of 10000 words
  Surely not a word : 1.4ms
  First word        : 1.8ms
  Last word         : 96.3ms
  Almost a word     : 116.6ms

Union of 100000 words
  Surely not a word : 0.7ms
  First word        : 0.8ms
  Last word         : 1227.1ms
  Almost a word     : 1404.1ms

Parece que la búsqueda de una sola palabra con un '\b(word1|word2|...|wordN)\b'patrón tiene:

  • O(1) mejor caso
  • O(n/2) caso promedio, que todavía es O(n)
  • O(n) peor de los casos

Estos resultados son consistentes con una simple búsqueda de bucle.

Una alternativa mucho más rápida a una unión regex es crear el patrón regex a partir de un trie .

Eric Duminil
fuente
1
Estabas en lo correcto. Mi sangría estaba mal. Lo arreglé en la pregunta original. En cuanto al comentario de que 50 oraciones / segundo es lento, todo lo que puedo decir es que estoy proporcionando un ejemplo simplificado. El conjunto de datos real es más complicado de lo que estoy describiendo, pero no parecía relevante. Además, la concatenación de mis "palabras" en una sola expresión regular mejoró enormemente la velocidad. Además, estoy "exprimiendo" espacios dobles después de los reemplazos.
pdanese
1
@ user36476 Gracias por los comentarios, eliminé la parte correspondiente. ¿Podrías por favor probar mi sugerencia? Me atrevo a decir que es mucho más rápido que la respuesta aceptada.
Eric Duminil
1
Dado que eliminó esa O(1)afirmación engañosa , su respuesta definitivamente merece un voto positivo.
idmean
1
@idmean: Cierto, eso no estaba muy claro. Solo se refería a la búsqueda: "¿Es esta palabra una palabra prohibida?".
Eric Duminil
1
@EricDuminil: ¡Buen trabajo! Ojalá pudiera votar por segunda vez.
Matthieu M.
105

TLDR

Use este método si desea la solución más rápida basada en expresiones regulares. Para un conjunto de datos similar a los OP, es aproximadamente 1000 veces más rápido que la respuesta aceptada.

Si no le importa la expresión regular, use esta versión basada en conjuntos , que es 2000 veces más rápida que una unión de expresión regular.

Regex optimizado con Trie

Un enfoque simple de unión de Regex se vuelve lento con muchas palabras prohibidas, porque el motor de expresiones regulares no hace un muy buen trabajo al optimizar el patrón.

Es posible crear un Trie con todas las palabras prohibidas y escribir la expresión regular correspondiente. El trie o regex resultante no son realmente legibles para los humanos, pero permiten una búsqueda y coincidencia muy rápidas.

Ejemplo

['foobar', 'foobah', 'fooxar', 'foozap', 'fooza']

Unión de expresiones regulares

La lista se convierte en un trie:

{
    'f': {
        'o': {
            'o': {
                'x': {
                    'a': {
                        'r': {
                            '': 1
                        }
                    }
                },
                'b': {
                    'a': {
                        'r': {
                            '': 1
                        },
                        'h': {
                            '': 1
                        }
                    }
                },
                'z': {
                    'a': {
                        '': 1,
                        'p': {
                            '': 1
                        }
                    }
                }
            }
        }
    }
}

Y luego a este patrón regex:

r"\bfoo(?:ba[hr]|xar|zap?)\b"

Regex trie

La gran ventaja es que para probar si zoocoincide, el motor de expresiones regulares solo necesita comparar el primer carácter (no coincide), en lugar de probar las 5 palabras . Es una exageración previa al proceso de 5 palabras, pero muestra resultados prometedores para muchos miles de palabras.

Tenga en cuenta que (?:)los grupos sin captura se utilizan porque:

Código

Aquí hay una esencia ligeramente modificada , que podemos usar como trie.pybiblioteca:

import re


class Trie():
    """Regex::Trie in Python. Creates a Trie out of a list of words. The trie can be exported to a Regex pattern.
    The corresponding Regex should match much faster than a simple Regex union."""

    def __init__(self):
        self.data = {}

    def add(self, word):
        ref = self.data
        for char in word:
            ref[char] = char in ref and ref[char] or {}
            ref = ref[char]
        ref[''] = 1

    def dump(self):
        return self.data

    def quote(self, char):
        return re.escape(char)

    def _pattern(self, pData):
        data = pData
        if "" in data and len(data.keys()) == 1:
            return None

        alt = []
        cc = []
        q = 0
        for char in sorted(data.keys()):
            if isinstance(data[char], dict):
                try:
                    recurse = self._pattern(data[char])
                    alt.append(self.quote(char) + recurse)
                except:
                    cc.append(self.quote(char))
            else:
                q = 1
        cconly = not len(alt) > 0

        if len(cc) > 0:
            if len(cc) == 1:
                alt.append(cc[0])
            else:
                alt.append('[' + ''.join(cc) + ']')

        if len(alt) == 1:
            result = alt[0]
        else:
            result = "(?:" + "|".join(alt) + ")"

        if q:
            if cconly:
                result += "?"
            else:
                result = "(?:%s)?" % result
        return result

    def pattern(self):
        return self._pattern(self.dump())

Prueba

Aquí hay una pequeña prueba (la misma que esta ):

# Encoding: utf-8
import re
import timeit
import random
from trie import Trie

with open('/usr/share/dict/american-english') as wordbook:
    banned_words = [word.strip().lower() for word in wordbook]
    random.shuffle(banned_words)

test_words = [
    ("Surely not a word", "#surely_NöTäWORD_so_regex_engine_can_return_fast"),
    ("First word", banned_words[0]),
    ("Last word", banned_words[-1]),
    ("Almost a word", "couldbeaword")
]

def trie_regex_from_words(words):
    trie = Trie()
    for word in words:
        trie.add(word)
    return re.compile(r"\b" + trie.pattern() + r"\b", re.IGNORECASE)

def find(word):
    def fun():
        return union.match(word)
    return fun

for exp in range(1, 6):
    print("\nTrieRegex of %d words" % 10**exp)
    union = trie_regex_from_words(banned_words[:10**exp])
    for description, test_word in test_words:
        time = timeit.timeit(find(test_word), number=1000) * 1000
        print("  %s : %.1fms" % (description, time))

Produce:

TrieRegex of 10 words
  Surely not a word : 0.3ms
  First word : 0.4ms
  Last word : 0.5ms
  Almost a word : 0.5ms

TrieRegex of 100 words
  Surely not a word : 0.3ms
  First word : 0.5ms
  Last word : 0.9ms
  Almost a word : 0.6ms

TrieRegex of 1000 words
  Surely not a word : 0.3ms
  First word : 0.7ms
  Last word : 0.9ms
  Almost a word : 1.1ms

TrieRegex of 10000 words
  Surely not a word : 0.1ms
  First word : 1.0ms
  Last word : 1.2ms
  Almost a word : 1.2ms

TrieRegex of 100000 words
  Surely not a word : 0.3ms
  First word : 1.2ms
  Last word : 0.9ms
  Almost a word : 1.6ms

Para información, la expresión regular comienza así:

(?: a (?: (?: \ 's | a (?: \' s | chen | liyah (?: \ 's)? | r (?: dvark (?: (?: \' s | s ))? | on)) | b (?: \ 's | a (?: c (?: us (?: (?: \' s | es))? | [ik]) | ft | solitario (? : (?: \ 's | s))? | ndon (? :( ?: ed | ing | ment (?: \' s)? | s))? | s (?: e (? :( ?: ment (?: \ 's)? | [ds]))? | h (? :( ?: e [ds] | ing))? | ing) | t (?: e (? :( ?: ment ( ?: \ 's)? | [ds]))? | ing | toir (?: (?: \' s | s))?)) | b (?: as (?: id)? | e (? : ss (?: (?: \ 's | es))? | y (?: (?: \' s | s))?) | ot (?: (?: \ 's | t (?: \ 's)? | s))? | reviat (?: e [ds]? | i (?: ng | on (?: (?: \' s | s))?)) | y (?: \ ' s)? | \ é (?: (?: \ 's | s))?) | d (?: icat (?: e [ds]? | i (?: ng | on (?: (?: \ 's | s))?)) | om (?: en (?: (?: \' s | s))? | inal) | u (?: ct (? :( ?: ed | i (?: ng | on (?: (?: \ 's | s))?) | o (?: (?: \' s | s))? | s))? | l (?: \ 's)?) ) | e (?: (?: \ 's | am | l (?: (?: \' s | ard | son (?: \ 's)?))? | r (?: deen (?: \ 's)? | nathy (?: \' s)? | ra (?: nt | tion (?: (?: \ 's | s))?)) | t (? :( ?: t (?: e (?: r (?: (?: \ 's | s))? | d) | ing | o (?: (?: \'s | s))?) | s))? | yance (?: \ 's)? | d))? | hor (? :( ?: r (?: e (?: n (?: ce (? : \ 's)? | t) | d) | ing) | s))? | i (?: d (?: e [ds]? | ing | jan (?: \' s)?) | gail | l (?: ene | it (?: ies | y (?: \ 's)?))) | j (?: ect (?: ly)? | ur (?: ation (?: (?: \' s | s))? | e [ds]? | ing)) | l (?: a (?: tive (?: (?: \ 's | s))? | ze) | e (? :(? : st | r))? | oom | ution (?: (?: \ 's | s))? | y) | m \' s | n (?: e (?: gat (?: e [ds] ? | i (?: ng | on (?: \ 's)?)) | r (?: \' s)?) | ormal (? :( ?: it (?: ies | y (?: \ ' s)?) | ly))?) | o (?: ard | de (?: (?: \ 's | s))? | li (?: sh (? :( ?: e [ds] | ing ))? | ((:: (?: \ 's | ist (?: (?: \' s | s))?))?) | mina (?: bl [ey] | t (?: e [ ds]? | i (?: ng | on (?: (?: \ 's | s))?))) | r (?: igin (?: al (?: (?: \' s | s) )? | e (?: (?: \ 's | s))?) | t (? :( ?: ed | i (?: ng | on (?: (?: \' s | ist (?: (?: \ 's | s))? | s))? | ve) | s))?) | u (?: nd (? :( ?: ed | ing | s))? | t) | ve (?: (?: \ 's | board))?) | r (?: a (?: cadabra (?: \' s)? | d (?: e [ds]? | ing) | ham (? : \ 's)? | m (?: (?: \' s | s))? | si (?: on (?: (?: \ 's | s))? | ve (? :( ?:\ 's | ly | ness (?: \' s)? | s))?)) | east | idg (?: e (? :( ?: ment (?: (?: \ 's | s)) ? | [ds]))? | ing | ment (?: (?: \ 's | s))?) | o (?: ad | gat (?: e [ds]? | i (?: ng | on (?: (?: \ 's | s))?))) | upt (? :( ?: e (?: st | r) | ly | ness (?: \' s)?))?) | s (?: alom | c (?: ess (?: (?: \ 's | e [ds] | ing))? | issa (?: (?: \' s | [es]))? | ond (? :( ?: ed | ing | s))?) | en (?: ce (?: (?: \ 's | s))? | t (? :( ?: e (?: e ( ?: (?: \ 's | ism (?: \' s)? | s))? | d) | ing | ly | s))?) | inth (?: (?: \ 's | e ( ?: \ 's)?))? | o (?: l (?: ut (?: e (?: (?: \' s | ly | st?))? | i (?: on (?: \ 's)? | sm (?: \' s)?)) | v (?: e [ds]? | ing)) | r (?: b (? :( ?: e (?: n (? : cy (?: \ 's)? | t (?: (?: \' s | s))?) | d) | ing | s))? | pti ...s | [es]))? | ond (? :( ?: ed | ing | s))?) | en (?: ce (?: (?: \ 's | s))? | t (?: (?: e (?: e (?: (?: \ 's | ism (?: \' s)? | s))? | d) | ing | ly | s))?) | inth (?: (?: \ 's | e (?: \' s)?))? | o (?: l (?: ut (?: e (?: (?: \ 's | ly | st?))? | i (?: on (?: \ 's)? | sm (?: \' s)?)) | v (?: e [ds]? | ing)) | r (?: b (? :( ?: e (?: n (?: cy (?: \ 's)? | t (?: (?: \' s | s))?) | d) | ing | s))? | pti .. .s | [es]))? | ond (? :( ?: ed | ing | s))?) | en (?: ce (?: (?: \ 's | s))? | t (?: (?: e (?: e (?: (?: \ 's | ism (?: \' s)? | s))? | d) | ing | ly | s))?) | inth (?: (?: \ 's | e (?: \' s)?))? | o (?: l (?: ut (?: e (?: (?: \ 's | ly | st?))? | i (?: on (?: \ 's)? | sm (?: \' s)?)) | v (?: e [ds]? | ing)) | r (?: b (? :( ?: e (?: n (?: cy (?: \ 's)? | t (?: (?: \' s | s))?) | d) | ing | s))? | pti .. .

Es realmente ilegible, pero para una lista de 100000 palabras prohibidas, esta expresión regular de Trie es 1000 veces más rápida que una simple unión de expresiones regulares.

Aquí hay un diagrama del trie completo, exportado con trie-python-graphviz y graphviz twopi:

Ingrese la descripción de la imagen aquí

Eric Duminil
fuente
Parece que para el propósito original, no hay necesidad de un grupo que no capture. Al menos el significado del grupo que no captura debe ser mencionado
Xavier Combelle
3
@XavierCombelle: Tienes razón en mencionar el grupo de captura: la respuesta se ha actualizado. Sin embargo, lo veo al revés: se necesitan parens para alternar expresiones regulares, |pero no se necesitan grupos de captura para nuestro propósito. Simplemente ralentizarían el proceso y usarían más memoria sin beneficio.
Eric Duminil
3
@EricDuminil Esta publicación es perfecta, muchas gracias :)
Mohamed AL ANI
1
@MohamedALANI: ¿Comparado con qué solución?
Eric Duminil
1
@ PV8: solo debe coincidir con palabras completas, sí, gracias al \b( límite de palabras ). Si la lista es ['apple', 'banana'], reemplazará las palabras que son exactamente appleo banana, pero no nana, banao pineapple.
Eric Duminil
15

Una cosa que quizás desee probar es preprocesar las oraciones para codificar los límites de las palabras. Básicamente convierta cada oración en una lista de palabras dividiéndolas en los límites de las palabras.

Esto debería ser más rápido, porque para procesar una oración, solo tienes que pasar por cada una de las palabras y verificar si es una coincidencia.

Actualmente, la búsqueda de expresiones regulares tiene que pasar por toda la cadena nuevamente cada vez, buscando límites de palabras y luego "descartando" el resultado de este trabajo antes del próximo paso.

Denziloe
fuente
8

Bueno, aquí hay una solución rápida y fácil, con un conjunto de pruebas.

Estrategia ganadora:

re.sub ("\ w +", repl, oración) busca palabras.

"repl" puede ser un invocable. Usé una función que realiza una búsqueda dict, y el dict contiene las palabras para buscar y reemplazar.

Esta es la solución más simple y rápida (vea la función replace4 en el código de ejemplo a continuación).

Segundo mejor

La idea es dividir las oraciones en palabras, usando re.split, mientras conserva los separadores para reconstruir las oraciones más tarde. Luego, los reemplazos se realizan con una simple búsqueda dict.

(vea la función replace3 en el código de ejemplo a continuación).

Tiempos por ejemplo funciones:

replace1: 0.62 sentences/s
replace2: 7.43 sentences/s
replace3: 48498.03 sentences/s
replace4: 61374.97 sentences/s (...and 240.000/s with PyPy)

... y código:

#! /bin/env python3
# -*- coding: utf-8

import time, random, re

def replace1( sentences ):
    for n, sentence in enumerate( sentences ):
        for search, repl in patterns:
            sentence = re.sub( "\\b"+search+"\\b", repl, sentence )

def replace2( sentences ):
    for n, sentence in enumerate( sentences ):
        for search, repl in patterns_comp:
            sentence = re.sub( search, repl, sentence )

def replace3( sentences ):
    pd = patterns_dict.get
    for n, sentence in enumerate( sentences ):
        #~ print( n, sentence )
        # Split the sentence on non-word characters.
        # Note: () in split patterns ensure the non-word characters ARE kept
        # and returned in the result list, so we don't mangle the sentence.
        # If ALL separators are spaces, use string.split instead or something.
        # Example:
        #~ >>> re.split(r"([^\w]+)", "ab céé? . d2eéf")
        #~ ['ab', ' ', 'céé', '? . ', 'd2eéf']
        words = re.split(r"([^\w]+)", sentence)

        # and... done.
        sentence = "".join( pd(w,w) for w in words )

        #~ print( n, sentence )

def replace4( sentences ):
    pd = patterns_dict.get
    def repl(m):
        w = m.group()
        return pd(w,w)

    for n, sentence in enumerate( sentences ):
        sentence = re.sub(r"\w+", repl, sentence)



# Build test set
test_words = [ ("word%d" % _) for _ in range(50000) ]
test_sentences = [ " ".join( random.sample( test_words, 10 )) for _ in range(1000) ]

# Create search and replace patterns
patterns = [ (("word%d" % _), ("repl%d" % _)) for _ in range(20000) ]
patterns_dict = dict( patterns )
patterns_comp = [ (re.compile("\\b"+search+"\\b"), repl) for search, repl in patterns ]


def test( func, num ):
    t = time.time()
    func( test_sentences[:num] )
    print( "%30s: %.02f sentences/s" % (func.__name__, num/(time.time()-t)))

print( "Sentences", len(test_sentences) )
print( "Words    ", len(test_words) )

test( replace1, 1 )
test( replace2, 10 )
test( replace3, 1000 )
test( replace4, 1000 )

Editar: también puede ignorar las minúsculas cuando verifica si pasa una lista minúscula de oraciones y edita las respuestas

def replace4( sentences ):
pd = patterns_dict.get
def repl(m):
    w = m.group()
    return pd(w.lower(),w)
bobflux
fuente
1
Votación a favor de las pruebas. replace4y mi código tiene desempeños similares.
Eric Duminil
No estoy seguro de qué repl(m):está haciendo def y cómo está asignando men la función replace4
StatguyUser
También estoy recibiendo el error error: unbalanced parenthesisde la líneapatterns_comp = [ (re.compile("\\b"+search+"\\b"), repl) for search, repl in patterns ]
StatguyUser
Si bien las funciones replace3 y replace4 abordan el problema original (para reemplazar palabras), replace1 y replace2 son de uso más general, ya que funcionan incluso si la aguja es una frase (una secuencia de palabras) y no solo una sola palabra.
Zoltan Fedor
7

Quizás Python no es la herramienta correcta aquí. Aquí hay uno con la cadena de herramientas Unix

sed G file         |
tr ' ' '\n'        |
grep -vf blacklist |
awk -v RS= -v OFS=' ' '{$1=$1}1'

suponiendo que su archivo de lista negra esté preprocesado con los límites de palabras agregados. Los pasos son: convertir el archivo a doble espacio, dividir cada oración en una palabra por línea, eliminar en masa las palabras de la lista negra del archivo y fusionar las líneas.

Esto debería correr al menos un orden de magnitud más rápido.

Para preprocesar el archivo de la lista negra a partir de palabras (una palabra por línea)

sed 's/.*/\\b&\\b/' words > blacklist
karakfa
fuente
4

Qué tal esto:

#!/usr/bin/env python3

from __future__ import unicode_literals, print_function
import re
import time
import io

def replace_sentences_1(sentences, banned_words):
    # faster on CPython, but does not use \b as the word separator
    # so result is slightly different than replace_sentences_2()
    def filter_sentence(sentence):
        words = WORD_SPLITTER.split(sentence)
        words_iter = iter(words)
        for word in words_iter:
            norm_word = word.lower()
            if norm_word not in banned_words:
                yield word
            yield next(words_iter) # yield the word separator

    WORD_SPLITTER = re.compile(r'(\W+)')
    banned_words = set(banned_words)
    for sentence in sentences:
        yield ''.join(filter_sentence(sentence))


def replace_sentences_2(sentences, banned_words):
    # slower on CPython, uses \b as separator
    def filter_sentence(sentence):
        boundaries = WORD_BOUNDARY.finditer(sentence)
        current_boundary = 0
        while True:
            last_word_boundary, current_boundary = current_boundary, next(boundaries).start()
            yield sentence[last_word_boundary:current_boundary] # yield the separators
            last_word_boundary, current_boundary = current_boundary, next(boundaries).start()
            word = sentence[last_word_boundary:current_boundary]
            norm_word = word.lower()
            if norm_word not in banned_words:
                yield word

    WORD_BOUNDARY = re.compile(r'\b')
    banned_words = set(banned_words)
    for sentence in sentences:
        yield ''.join(filter_sentence(sentence))


corpus = io.open('corpus2.txt').read()
banned_words = [l.lower() for l in open('banned_words.txt').read().splitlines()]
sentences = corpus.split('. ')
output = io.open('output.txt', 'wb')
print('number of sentences:', len(sentences))
start = time.time()
for sentence in replace_sentences_1(sentences, banned_words):
    output.write(sentence.encode('utf-8'))
    output.write(b' .')
print('time:', time.time() - start)

Estas soluciones se dividen en los límites de las palabras y busca cada palabra en un conjunto. Deben ser más rápidos que los sustitutos de la segunda palabra (solución de Liteyes) ya que estas soluciones son O(n)donde n es el tamaño de la entrada debido aamortized O(1) búsqueda establecida, mientras que el uso de alternativas de expresiones regulares causaría que el motor de expresiones regulares tenga que verificar la coincidencia de palabras en todos los caracteres en lugar de solo en los límites de las palabras. Mi solución es tener mucho cuidado para preservar los espacios en blanco que se usaron en el texto original (es decir, no comprime los espacios en blanco y conserva las pestañas, las nuevas líneas y otros caracteres de espacios en blanco), pero si decide que no le importa, debería ser bastante sencillo eliminarlos de la salida.

Probé en corpus.txt, que es una concatenación de múltiples libros electrónicos descargados del Proyecto Gutenberg, y banned_words.txt es de 20000 palabras elegidas al azar de la lista de palabras de Ubuntu (/ usr / share / dict / american-english). Se necesitan alrededor de 30 segundos para procesar 862462 oraciones (y la mitad de eso en PyPy). He definido oraciones como cualquier cosa separada por ".".

$ # replace_sentences_1()
$ python3 filter_words.py 
number of sentences: 862462
time: 24.46173644065857
$ pypy filter_words.py 
number of sentences: 862462
time: 15.9370770454

$ # replace_sentences_2()
$ python3 filter_words.py 
number of sentences: 862462
time: 40.2742919921875
$ pypy filter_words.py 
number of sentences: 862462
time: 13.1190629005

PyPy se beneficia más del segundo enfoque, mientras que a CPython le fue mejor en el primer enfoque. El código anterior debería funcionar tanto en Python 2 como en 3.

Lie Ryan
fuente
Python 3 es un hecho en la pregunta. He votado a favor, pero creo que valdría la pena sacrificar algunos de los detalles y la implementación 'óptima' de este código para hacerlo menos detallado.
pvg
Si lo entiendo correctamente, es básicamente el mismo principio que mi respuesta, pero ¿más detallado? La división y unión de \W+es básicamente igual que suben \w+, ¿verdad?
Eric Duminil
Me pregunto si mi solución a continuación (función replace4) es más rápida que pypy;) ¡Me gustaría probar en sus archivos!
bobflux
3

Acercamiento práctico

Una solución que se describe a continuación utiliza mucha memoria para almacenar todo el texto en la misma cadena y reducir el nivel de complejidad. Si la RAM es un problema, piénselo dos veces antes de usarla.

Con join/ splittricks puedes evitar los bucles que deberían acelerar el algoritmo.

  • Concatenar oraciones con un delimitador especial que no está contenido en las oraciones:

    • merged_sentences = ' * '.join(sentences)

  • Recopile una expresión regular para todas las palabras que necesita eliminar de las oraciones usando la |declaración "o" expresión regular:

    • regex = re.compile(r'\b({})\b'.format('|'.join(words)), re.I) # re.I is a case insensitive flag

  • Subíndice las palabras con la expresión regular compilada y divídala por el carácter delimitador especial en oraciones separadas:

    • clean_sentences = re.sub(regex, "", merged_sentences).split(' * ')

    Actuación

    "".joinla complejidad es O (n). Esto es bastante intuitivo, pero de todos modos hay una cita abreviada de una fuente:

    for (i = 0; i < seqlen; i++) {
    [...]
    sz += PyUnicode_GET_LENGTH(item);

    Por lo tanto, con join/splitusted tiene O (palabras) + 2 * O (oraciones), que sigue siendo una complejidad lineal frente a 2 * O (N 2 ) con el enfoque inicial.

    por cierto, no use multihilo. GIL bloqueará cada operación porque su tarea está estrictamente vinculada a la CPU, por lo que GIL no tiene posibilidad de ser liberada, pero cada subproceso enviará tics al mismo tiempo que causan un esfuerzo adicional e incluso llevan la operación al infinito.

    I159
    fuente
    En caso de que las oraciones estén (fueron) almacenadas en un archivo de texto, ya están separadas por una nueva línea. Por lo tanto, todo el archivo podría leerse como una gran cadena (o búfer), eliminar palabras y luego volver a escribirse (o esto podría hacerse directamente en el archivo utilizando la asignación de memoria). Otoh, para eliminar una palabra, el resto de la cadena debe moverse hacia atrás para llenar el espacio, por lo que sería un problema con una cadena muy grande. Una alternativa sería volver a escribir las partes entre las palabras en otra cadena o archivo (que incluiría las nuevas líneas), o simplemente mover esas partes en un archivo mmapped (1) ..
    Danny_ds
    .. Ese último enfoque (mover / escribir las partes entre las palabras) combinado con la búsqueda de conjunto de Eric Duminil podría ser realmente rápido, tal vez sin siquiera usar expresiones regulares. (2)
    Danny_ds
    .. O tal vez regex ya está optimizado para mover solo esas partes al reemplazar varias palabras, no lo sé.
    Danny_ds
    0

    Concatena todas tus oraciones en un solo documento. Use cualquier implementación del algoritmo Aho-Corasick ( aquí hay uno ) para localizar todas sus palabras "malas". Recorre el archivo, reemplaza cada palabra incorrecta, actualiza las compensaciones de las palabras encontradas que siguen, etc.

    Edi Bice
    fuente