Aquí hay un problema: digamos que estás ingiriendo aproximadamente 4 millones de comentarios de Reddit por día, y necesitas detectar la presencia de 10.000 palabras clave específicas en tiempo casi real. La respuesta ingenua es obvia: loop a través de cada comentario y palabra clave. for comment in reddit_comments:
    for keyword in keywords:
        if keyword in comment:
            # alert user
 Es sencillo. también visiblemente lento. Incluso si ignora la matemática, es (facilmente) hacer miles de millones de comparaciones de cuerdas.La complejidad es cuadrática, y no hay manera de que pueda ejecutarlo en un pequeño VPS. Ese es el problema con el que Lewis Van Winkle se encontró al construir F5Bot (un servicio de rascado gratuito de Reddit). Un algoritmo de 1975 llamado Permite buscar patrones en un solo paso. Corazón El problema de los 600 dólares bibliógrafos El problema surgió en Bell Labs (1975) cuando Margaret Corasick estaba trabajando en una herramienta para buscar palabras clave en cintas provistas por el gobierno.Un bibliógrafo golpeó los límites de uso de $600 mientras buscaba cientos de palabras clave a la vez (y el programa no había terminado). Corasick asistió a un seminario sobre el diseño de algoritmos de Alfred Aho, y ellos llegaron a lo que conocemos como el algoritmo Aho-Corasick. La búsqueda del bibliógrafo ahora corrió por $ 25. 24x speedup. ¿Por qué cuidar El Aho-corasick es en realidad un algoritmo muy popular.   Aho-Corasick. los escáneres de virus lo utilizan para escanear miles de firmas de malware. F5Bot lo utiliza para monitorear los comentarios de Reddit y Hacker News. fgrep Fuera Basta con mirar el índice de referencia de F5Bot. Loaded 3000 keywords to search on a text of 19377 chars

searching with strpos (naive):  0.384 seconds
searching with aho-corasick:    0.055 seconds (7x faster)
 Es una flexión que me gustaría tener en cualquier momento. Cómo funciona La idea básica es - si está buscando varias palabras clave, está haciendo trabajo redundante. Supongamos que estás buscando: , de , de Usando el enfoque ingenuo, escanearía su texto tres veces - una vez para cada palabra clave. "art" "cart" "ted" Si ya has buscado y sabes que está ahí, puedes empezar allí. Basta construir una máquina de estado finito y explotar sufixos compartidos. Básicamente, un árbol (de cuerdas) donde cada nodo representa un prefijo de una de tus palabras clave. A medida que escaneas a través de tu caracter de texto por caracteres, te mueves a través de este gráfico. Suena horriblemente similar a un trie? ¡Eso es porque es un trie! "art" Lo que es inteligente es que el algoritmo construye “enlaces de fracaso” entre nodos. En inglés, esto es - “si el siguiente personaje no coincide, no comience desde la raíz. Te mostramos un ejemplo, si estás buscando , el algoritmo construye un trie (árbol del prefijo) y agrega los enlaces adicionales que ve en azul/verde: {a, ab, b, bc, bca, c, ca, caa} Si usted está familiarizado con un Sólo añade a De esta manera, puede saltar instantáneamente al sufixo de correspondencia más largo en lugar de escanear la palabra de nuevo desde la raíz. El texto se escanea sólo una vez, así que terminas con una complejidad temporal de O(n); donde n es la longitud del texto. trie Fracaso en el enlace "abccab" Un enfoque ingenuo te haría escanear la palabra una y otra vez; O(n * m * k) donde m es el número de palabras clave y k es su longitud promedio. Aho-Corasick es O(n+m+z), donde z es el número de coincidencias. Incluso si buscas millones de palabras clave, Aho-Corasick lo maneja linealmente. Implementación Puedes encontrar una En mi reciente proyecto, donde lo adaptei para buscar 9 mutaciones (patrones) en un archivo del genoma (básicamente 4M caracteres), y buscó todo en 0.75s. Implementación simple Te doy un ejemplo sencillo para que veas cómo funciona.  
# naive approach
for comment in reddit_comments:
    for keyword in keywords:
        if keyword in comment:
            # alert user
 
# with aho-corasick
step 1: build an automaton (trie) using patterns
step 2: add failure links (with bfs)
step 3: search automaton by following failure links, and return patterns that matched
 Creo que la implementación es de aproximadamente 60 líneas de código real. También hay una biblioteca reciente - Es super fácil de usar. pyahocorasick Utilice esto cuando No tienes que hacer spam Cuando busques tres palabras clave en un párrafo, utilízalo cuando: ahocorasick 
 
 
 Estás buscando miles de palabras clave que no cambian a menudo (F5Bot usecase) Necesita correr con frecuencia (pensar los flujos) Cierra los pensamientos El Aho-Corasick fue inventado por Margaret con una pluma y papel hace 50 años, sin ninguna IA. Los ordenadores de hoy en día son millones de veces más rápidos, y el problema de búsqueda de $ 600 sería trivial hoy en día. pero si está procesando millones de comentarios de Reddit por día en un pequeño VPS, no puede simplemente arrojar hardware al problema. Alimento para pensar, probablemente haya un algoritmo de 50 años que resuelva su problema mejor que cualquier cosa que esté a punto de implementar. Footnotes: 
 
 
 
 
 
 El artículo original de 1975 Efficient string matching: An aid to bibliographic search es sorprendentemente legible. La tesis de doctorado de Margaret J. Corasick (1974) era “asegurar datos propietarios dentro de sistemas abiertos” - seguridad de la información temprana. triste que ella no tenga su propia página de Wikipedia, a pesar de su algoritmo y Alfred Aho (él es el “A” en AWK - Aho, Weinberger, Kernighan) ambos tienen sus propias páginas de Wikipedia. Hay una biblioteca de Python llamada pyahocorasick que se implementa en C para uso de producción. estoy seguro de que es mucho más rápido que mi versión, pero los principios son idénticos. KMP (Knuth-Morris-Pratt) utiliza un enfoque similar para compilar patrones en una automata finita. Básicamente ahocorasick para un patrón único. Ambos precomputan una estructura y explotan los prefixos que aparecen. El automático Aho-Corasick puede convertirse en masivo - O (total de caracteres en todas las palabras clave). Si tiene millones de patrones, puede necesitar una memoria significativa.

This story contains new, firsthand information uncovered by the writer.

Walkthroughs, tutorials, guides, and tips. This story will teach you how to do something new or how to do something better.

Read My Stories

Este audio es producido en el idioma original de la historia!

Un algoritmo de 1975 sigue derrotando la fuerza bruta en la búsqueda de palabras clave modernas

About Author

COMENTARIOS

ETIQUETAS

ESTE ARTÍCULO FUE PRESENTADO EN

Related Stories

State of the Noonion: Green Clock Strikes Noon

Creación de productos criptográficos centrados en el usuario: la importancia de los comentarios de los clientes

Crecimiento de las criptomonedas: creación de perfiles de usuarios eficaces

Cómo mejorar su flujo de trabajo 10 veces: 17 aplicaciones esenciales

State of the Noonion: Green Clock Strikes Noon

Creación de productos criptográficos centrados en el usuario: la importancia de los comentarios de los clientes

Crecimiento de las criptomonedas: creación de perfiles de usuarios eficaces

Cómo mejorar su flujo de trabajo 10 veces: 17 aplicaciones esenciales

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps