algorithm - corasick - Algoritmo para encontrar los 10 mejores términos de búsqueda

aho corasick algorithm (16)

Solución exacta

Primero, una solución que garantiza resultados correctos, pero que requiere mucha memoria (un gran mapa).

Variante "de todos los tiempos"

Mantenga un mapa hash con consultas como claves y sus recuentos como valores. Además, conserve una lista de las 10 consultas más frecuentes hasta el momento y el recuento del décimo recuento más frecuente (un umbral).

Actualice constantemente el mapa a medida que se lee el flujo de consultas. Cada vez que un conteo excede el umbral actual, haga lo siguiente: elimine la 10ma consulta de la lista "Top 10", reemplácela con la consulta que acaba de actualizar y actualice también el umbral.

Variante "mes pasado"

Mantenga la misma lista de los "10 principales" y actualícela de la misma manera que arriba. Además, mantenga un mapa similar, pero esta vez almacena los vectores de 30 * 24 = 720 (uno por cada hora) como valores. Cada hora haga lo siguiente para cada tecla: elimine el contador más antiguo del vector y agregue uno nuevo (inicializado a 0) al final. Retire la clave del mapa si el vector es cero. Además, cada hora debe calcular la lista de las "10 principales" desde cero.

Nota: Sí, esta vez almacenamos 720 enteros en lugar de uno, pero hay muchas menos teclas (la variante de todos los tiempos tiene una cola muy larga).

Aproximaciones

Estas aproximaciones no garantizan la solución correcta, pero consumen menos memoria.

Procese cada enésima consulta, omitiendo el resto.
(Solo para variante de todos los tiempos) Mantenga como máximo M pares clave-valor en el mapa (M debe ser tan grande como pueda). Es una especie de caché LRU: cada vez que lee una consulta que no está en el mapa, elimine la consulta utilizada menos recientemente con el recuento 1 y reemplácela con la consulta procesada actualmente.

Actualmente me estoy preparando para una entrevista y me recordó una pregunta que me hicieron una vez en una entrevista anterior que decía algo como esto:

"Se le ha pedido que diseñe algún software para mostrar continuamente los 10 términos principales de búsqueda en Google. Se le concede acceso a un feed que proporciona una secuencia infinita de términos de búsqueda que se buscan actualmente en Google. Describa qué algoritmo y estructuras de datos usarías para implementar esto. Debes diseñar dos variaciones:

(i) Muestre los 10 mejores términos de búsqueda de todos los tiempos (es decir, desde que comenzó a leer el feed).

(ii) Mostrar solo los 10 mejores términos de búsqueda del último mes, actualizados por hora.

Puedes usar una aproximación para obtener la lista de los 10 mejores, pero debes justificar tus elecciones ".
Bombardeé en esta entrevista y aún no tengo idea de cómo implementar esto.

La primera parte pregunta por los 10 elementos más frecuentes en una subsecuencia de crecimiento continuo de una lista infinita. Busqué algoritmos de selección, pero no pude encontrar ninguna versión en línea para resolver este problema.

La segunda parte usa una lista finita, pero debido a la gran cantidad de datos que se procesan, no se puede almacenar todo el mes de términos de búsqueda en la memoria y calcular un histograma cada hora.

El problema se hace más difícil por el hecho de que la lista de los 10 principales se actualiza continuamente, por lo que de alguna manera debe calcular su top 10 en una ventana deslizante.

¿Algunas ideas?

Resumen de estimación de frecuencia

Existen algunos algoritmos bien conocidos que pueden proporcionar estimados de frecuencia para tal flujo usando una cantidad fija de almacenamiento. Uno es frecuente, por Misra y Gries (1982). De una lista de n elementos, encuentra todos los elementos que ocurren más de n / k veces, usando k - 1 contadores. Esta es una generalización del algoritmo de mayoría de Boyer y Moore (Fischer-Salzberg, 1982), donde k es 2. Los algoritmos de ahorro y almacenamiento de Manku y Motwani LossyCounting (2002) y Metwally''s SpaceSaving (2005) tienen requisitos de espacio similares, pero pueden proporcionar estimaciones más precisas bajo ciertos condiciones

Lo importante para recordar es que estos algoritmos solo pueden proporcionar estimaciones de frecuencia. Específicamente, la estimación de Misra-Gries puede infravalorar la frecuencia real en (n / k) elementos.

Supongamos que tiene un algoritmo que podría identificar positivamente un elemento solo si ocurre más del 50% del tiempo. Alimente este algoritmo con una secuencia de N elementos distintos y luego agregue otro N - 1 copias de un elemento, x , para un total de 2N - 1 elementos. Si el algoritmo le dice que x excede el 50% del total, debe haber estado en la primera secuencia; si no lo hace, x no estaba en la secuencia inicial. Para que el algoritmo haga esta determinación, debe almacenar la secuencia inicial (¡o algún resumen proporcional a su longitud)! Entonces, podemos demostrarnos a nosotros mismos que el espacio requerido por tal algoritmo "exacto" sería Ω ( N ).

En cambio, estos algoritmos de frecuencia descritos aquí proporcionan una estimación, identificando cualquier artículo que excede el umbral, junto con algunos artículos que caen por debajo de ese margen. Por ejemplo, el algoritmo de Mayoría , usando un solo contador, siempre dará un resultado; si algún elemento excede el 50% de la secuencia, se encontrará. Pero también podría darle un artículo que ocurre solo una vez. No lo sabría sin hacer un segundo pase sobre los datos (utilizando, de nuevo, un único contador, pero buscando solo ese elemento).

El algoritmo frecuente

Aquí hay una descripción simple del algoritmo frecuente de Misra-Gries. Demaine (2002) y otros han optimizado el algoritmo, pero esto le da la esencia.

Especifique la fracción umbral, 1 / k ; cualquier artículo que ocurra más de n / k veces se encontrará. Cree un mapa vacío (como un árbol rojo-negro); las claves serán términos de búsqueda, y los valores serán un contador para ese término.

Mire cada artículo en la secuencia.
Si el término existe en el mapa, incremente el contador asociado.
De lo contrario, si el mapa tiene menos de k - 1 entradas, agregue el término al mapa con un contador de uno.
Sin embargo, si el mapa ya tiene k - 1 entradas, disminuya el contador en cada entrada. Si algún contador llega a cero durante este proceso, quítelo del mapa.

Tenga en cuenta que puede procesar una cantidad infinita de datos con una cantidad fija de almacenamiento (solo el mapa de tamaño fijo). La cantidad de almacenamiento requerida depende solo del umbral de interés, y el tamaño de la transmisión no importa.

Contando Búsquedas

En este contexto, tal vez almacenará una hora de búsquedas y realizará este proceso en los datos de esa hora. Si puede realizar un segundo pase en el registro de búsqueda de esta hora, puede obtener un conteo exacto de las ocurrencias de los "candidatos" principales identificados en el primer pase. O tal vez está bien hacer un solo pase, e informar a todos los candidatos, sabiendo que se incluye cualquier artículo que debería estar allí, y los extras son sólo ruido que desaparecerá en la próxima hora.

Cualquier candidato que realmente exceda el umbral de interés se almacena como un resumen. Mantenga un mes de estos resúmenes, descartando los más antiguos cada hora, y tendría una buena aproximación de los términos de búsqueda más comunes.

¿Qué hay de usar un Splay Tree con 10 nodos? Cada vez que intenta acceder a un valor (término de búsqueda) que no está contenido en el árbol, elimine cualquier hoja, inserte el valor en su lugar y acceda a él.

La idea detrás de esto es la misma que en mi otra answer . Bajo el supuesto de que los términos de búsqueda se acceden de manera uniforme / regular, esta solución debería funcionar muy bien.

editar

También se podrían almacenar más términos de búsqueda en el árbol (lo mismo vale para la solución que sugiero en mi otra respuesta) para no eliminar un nodo al que se pueda acceder muy pronto nuevamente. Cuantos más valores uno almacene en él, mejores serán los resultados.

¿Qué pasa con una adaptación del "algoritmo de reemplazo de página de reloj" (también conocido como "segunda oportunidad")? Me imagino que funcionará muy bien si las solicitudes de búsqueda se distribuyen de manera uniforme (eso significa que la mayoría de los términos buscados aparecen regularmente en lugar de 5 millones de veces seguidas y nunca más).

Aquí hay una representación visual del algoritmo:

Almacene el recuento de términos de búsqueda en una tabla hash gigante, donde cada búsqueda nueva hace que un elemento en particular se incremente en uno. Mantenga un registro de los mejores 20 términos de búsqueda; cuando el elemento en el lugar 11 se incrementa, verifique si necesita cambiar las posiciones con # 10 * (no es necesario mantener los 10 primeros clasificados, lo único que importa es establecer la distinción entre 10º y 11º).

* _{Se deben hacer comprobaciones similares para ver si un nuevo término de búsqueda está en el lugar 11, por lo que este algoritmo también se relaciona con otros términos de búsqueda, por lo que me estoy simplificando un poco.}

Bueno, parece una gran cantidad de datos, con un costo quizás prohibitivo para almacenar todas las frecuencias. Cuando la cantidad de datos es tan grande que no podemos esperar almacenarla todo, ingresamos al dominio de los algoritmos de flujo de datos .

Libro útil en esta área: Muthukrishnan - "Data Streams: Algorithms and Applications"

Referencia estrechamente relacionada con el problema en cuestión que elegí de lo anterior: Manku, Motwani - "La frecuencia aproximada cuenta sobre los flujos de datos" [pdf]

Por cierto, Motwani, de Stanford, (edit) fue autor del muy importante libro "Algoritmos aleatorios" . ~~El capítulo 11 de este libro trata este problema~~ . Editar: Lo siento, mala referencia, ese capítulo en particular es sobre un problema diferente. Después de verificar, recomiendo la sección 5.1.2 del libro de Muthukrishnan , disponible en línea.

Heh, buena pregunta de entrevista.

Este es uno de los proyectos de investigación por los que estoy pasando. El requisito es casi exactamente como el suyo, y hemos desarrollado buenos algoritmos para resolver el problema.

La entrada

La entrada es una secuencia interminable de palabras o frases en inglés (las referimos como tokens ).

La salida

Salida tokens N superiores que hemos visto hasta ahora (¡de todos los tokens que hemos visto!)
Muestra tokens N superiores en una ventana histórica, por ejemplo, el último día o la última semana.

Una aplicación de esta investigación es encontrar el tema candente o las tendencias del tema en Twitter o Facebook. Tenemos un rastreador que se arrastra en el sitio web, que genera una secuencia de palabras que alimentarán el sistema. Luego, el sistema generará las palabras o frases de mayor frecuencia en general o históricamente. Imagine que en las últimas semanas la frase "Copa del Mundo" aparezca muchas veces en Twitter. Lo mismo ocurre con "Paul the Octopus". :)

Cadena en enteros

El sistema tiene una identificación entera para cada palabra. Aunque hay casi infinitas palabras posibles en Internet, pero después de acumular un gran conjunto de palabras, la posibilidad de encontrar nuevas palabras se vuelve más y más baja. Ya hemos encontrado 4 millones de palabras diferentes y se les asignó una identificación única para cada una. Este conjunto completo de datos se puede cargar en la memoria como una tabla hash, consumiendo aproximadamente 300 MB de memoria. (Hemos implementado nuestra propia tabla hash. La implementación de Java requiere una gran cantidad de memoria)

Cada frase puede identificarse como una matriz de enteros.

Esto es importante porque la clasificación y las comparaciones en enteros es mucho más rápida que en cadenas.

Archivar datos

El sistema mantiene los datos de archivo para cada token. Básicamente son pares de (Token, Frequency) . Sin embargo, la tabla que almacena los datos sería tan grande que tendríamos que particionar la tabla físicamente. Una vez que el esquema de partición se basa en ngrams del token. Si el token es una sola palabra, es 1 gramo. Si el token es una frase de dos palabras, es 2gram. Y esto continúa. Aproximadamente a 4 gramos tenemos 1 mil millones de registros, con una tabla de alrededor de 60 GB.

Procesamiento de flujos entrantes

El sistema absorberá las oraciones entrantes hasta que la memoria se utilice por completo (Ya, necesitamos un MemoryManager). Después de tomar N frases y almacenarlas en la memoria, el sistema hace una pausa y comienza a convertir las frases en palabras y frases. Cada ficha (palabra o frase) se cuenta.

Para tokens altamente frecuentes, siempre se guardan en la memoria. Para los tokens menos frecuentes, se ordenan según los ID (recuerde que traducimos el String a una matriz de enteros) y se serializan en un archivo de disco.

(Sin embargo, para su problema, ya que está contando solo palabras, entonces puede poner todo el mapa de palabras en memoria solamente. Una estructura de datos cuidadosamente diseñada consumiría solo 300MB de memoria para 4 millones de palabras diferentes. Alguna pista: use ASCII char para representa cadenas), y esto es muy aceptable.

Mientras tanto, habrá otro proceso que se activará una vez que encuentre cualquier archivo de disco generado por el sistema, luego comenzará a fusionarlo. Dado que el archivo de disco está ordenado, la fusión tomaría un proceso similar al de fusión. Algunos diseños también deben tenerse en cuenta aquí, ya que queremos evitar demasiadas búsquedas de discos aleatorios. La idea es evitar la lectura (proceso de fusión) / escritura (salida del sistema) al mismo tiempo, y dejar que el proceso de fusión se lea desde un disco mientras se escribe en un disco diferente. Esto es similar a implementar un bloqueo.

Fin del día

Al final del día, el sistema tendrá muchos tokens frecuentes con frecuencia almacenada en la memoria, y muchos otros tokens menos frecuentes almacenados en varios archivos de disco (y cada archivo está ordenado).

El sistema vacía el mapa en memoria en un archivo de disco (ordene). Ahora, el problema se convierte en fusionar un conjunto de archivos de disco ordenados. Con un proceso similar, obtendríamos un archivo de disco ordenado al final.

Luego, la tarea final es fusionar el archivo de disco ordenado en la base de datos de archivo. Depende del tamaño de la base de datos de archivo, el algoritmo funciona de la siguiente manera si es lo suficientemente grande:

for each record in sorted disk file update archive database by increasing frequency if rowcount == 0 then put the record into a list end for for each record in the list of having rowcount == 0 insert into archive database end for

La intuición es que, después de algún tiempo, el número de insertos será cada vez más pequeño. Más y más operación estará en la actualización solamente. Y esta actualización no será penalizada por el índice.

Espero que toda esta explicación sea de ayuda. :)

No sé si entiendo bien o no. Mi solución está usando montón. Debido a los 10 principales elementos de búsqueda, construyo un montón con el tamaño 10. A continuación, actualice este montón con la nueva búsqueda. Si la frecuencia de una nueva búsqueda es mayor que la de Heap (Max Heap) arriba, actualícela. Abandona el que tiene la frecuencia más pequeña.

Pero, cómo calcular la frecuencia de la búsqueda específica se contará en otra cosa. Tal vez, como todos dijeron, el algoritmo del flujo de datos ...

Pensamiento áspero ...

Para los 10 primeros todos los tiempos

Usando una colección de hash donde se almacena un conteo para cada término (términos de desinfección, etc.)
Una matriz ordenada que contiene los 10 principales en curso, un término / conteo agregado a esta matriz siempre que el recuento de un término sea igual o mayor que el recuento más pequeño en la matriz

Para los 10 primeros mensuales actualizados por hora:

Usando una matriz indexada en el número de horas transcurridas desde el módulo de inicio 744 (el número de horas durante un mes), las entradas de la matriz consisten en la recolección de hash donde se almacena un recuento de cada término encontrado durante este intervalo de horas. Una entrada se restablece cada vez que cambia el contador de horas
las estadísticas de la matriz indexada en el intervalo de horas deben recopilarse cada vez que cambie el contador de horas actuales (una vez por hora como máximo) al copiar y alisar el contenido de esta matriz indexada en intervalos de horas

Errr ... ¿tiene sentido? No pensé en esto como lo haría en la vida real

Ah sí, se olvidó de mencionar, el "copiado / aplanamiento" por hora requerido para las estadísticas mensuales puede reutilizar el mismo código utilizado para los 10 mejores de todos los tiempos, un agradable efecto secundario.

Podría usar una tabla hash combinada con un árbol de búsqueda binario . Implemente un diccionario <search term, count> que le indica cuántas veces se ha buscado cada término de búsqueda.

Obviamente iterar toda la tabla hash cada hora para obtener los 10 primeros es muy malo. Pero estamos hablando de Google, por lo que puede suponer que obtendrán los diez primeros, digamos más de 10 000 visitas (aunque probablemente sea un número mucho mayor). Por lo tanto, cada vez que el recuento de un término de búsqueda supera los 10 000, insértelo en el BST. Luego, cada hora, solo tiene que obtener los primeros 10 de la BST, que debe contener relativamente pocas entradas.

Esto resuelve el problema de los 10 mejores de todos los tiempos.

La parte realmente difícil es lidiar con un término que ocupa el lugar del otro en el informe mensual (por ejemplo, "desbordamiento de pila" podría tener 50 000 visitas durante los últimos dos meses, pero solo 10 000 el mes pasado, mientras que "amazonas" podría tener 40 000 en los últimos dos meses pero 30 000 en el último mes. Desea que "amazon" aparezca antes del "desbordamiento de pila" en su informe mensual). Para hacer esto, almacenaría, para todas las principales (más de 10 000 búsquedas de todos los tiempos) términos de búsqueda, una lista de 30 días que le dice cuántas veces se buscó ese término en cada día. La lista funcionaría como una cola FIFO: elimina el primer día e inserta uno nuevo cada día (o cada hora, pero luego podría necesitar almacenar más información, lo que significa más memoria / espacio. Si la memoria no es un problema, haga de lo contrario, busque esa "aproximación" de la que están hablando).

Esto parece un buen comienzo. A continuación, puede preocuparse por eliminar los términos que tienen> 10 000 hits, pero no han tenido muchos en mucho tiempo y cosas por el estilo.

Una forma es que para cada búsqueda, usted almacena ese término de búsqueda y su marca de tiempo. De esta forma, encontrar los diez primeros para cualquier período de tiempo es simplemente una cuestión de comparar todos los términos de búsqueda dentro del período de tiempo dado.

El algoritmo es simple, pero el inconveniente sería un mayor consumo de memoria y tiempo.

Use cm-sketch para almacenar el recuento de todas las búsquedas desde el comienzo, mantenga un min-heap de tamaño 10 con el top 10. Para el resultado mensual, mantenga 30 cm-sketch / hash-table y min-heap con él, cada inicio contando y actualizando desde los últimos 30, 29 .., 1 día. As a day pass, clear the last and use it as day 1. Same for hourly result, keep 60 hash-table and min-heap and start counting for last 60, 59, ...1 minute. As a minute pass, clear the last and use it as minute 1.

Montly result is accurate in range of 1 day, hourly result is accurate in range of 1 min

a veces la mejor respuesta es "No sé".

Voy a tomar una puñalada más profunda. Mi primer instinto sería alimentar los resultados en una Q. Un proceso procesaría continuamente los elementos que entran en la Q. El proceso mantendría un mapa de

término -> recuento

cada vez que se procesa un elemento Q, simplemente busca el término de búsqueda e incrementa el recuento.

Al mismo tiempo, mantendría una lista de referencias a las 10 entradas principales en el mapa.

Para la entrada que se implementó actualmente, vea si su recuento es mayor que el recuento del recuento de la entrada más pequeña en el top 10. (si no está en la lista ya). Si es así, reemplace el más pequeño con la entrada.

Creo que eso funcionaría Ninguna operación requiere mucho tiempo. Debería encontrar una forma de administrar el tamaño del mapa de conteo. pero eso debería ser lo suficientemente bueno para una respuesta de entrevista.

No esperan una solución, quieren ver si puedes pensar. No tienes que escribir la solución en ese momento ...

Los 10 términos de búsqueda para el último mes

El uso de una estructura de datos / indexación eficiente de la memoria, como los intentos de empaquetado ajustado (de las entradas de wikipedia en los tries ), define aproximadamente cierta relación entre los requisitos de memoria y n - número de términos.

En caso de que la memoria requerida esté disponible ( suposición 1 ), puede mantener estadísticas mensuales exactas y agregarlas cada mes en estadísticas de todos los tiempos.

También hay una suposición aquí que interpreta el ''último mes'' como una ventana fija. Pero incluso si la ventana mensual se desliza, el procedimiento anterior muestra el principio (el deslizamiento se puede aproximar con ventanas fijas de un tamaño dado).

Esto me recuerda la base de datos round-robin con la excepción de que algunas estadísticas se calculan ''todo el tiempo'' (en un sentido que no se retienen todos los datos; rrd consolida períodos sin tener en cuenta los detalles al promediar, resumir o elegir valores máximo / mínimo, en una tarea determinada, el detalle que se pierde es información sobre elementos de baja frecuencia, lo que puede introducir errores).

Suposición 1

Si no podemos mantener las estadísticas perfectas para todo el mes, entonces deberíamos poder encontrar un período P determinado para el cual podamos mantener las estadísticas perfectas. Por ejemplo, suponiendo que tenemos estadísticas perfectas sobre un período de tiempo P, que va al mes n veces.
Las estadísticas perfectas definen la función f(search_term) -> search_term_occurance .

Si podemos mantener todas las n tablas de estadísticas perfectas en la memoria, las estadísticas mensuales deslizantes se pueden calcular así:

agregar estadísticas para el período más nuevo
eliminar estadísticas para el período más antiguo (así que tenemos que mantener n tablas de estadísticas perfectas)

Sin embargo, si solo mantenemos el top 10 en el nivel agregado (mensual), podremos descartar una gran cantidad de datos de las estadísticas completas del período fijo. Esto proporciona ya un procedimiento de trabajo que tiene fijos (suponiendo límite superior en la tabla de estadísticas perfecta para el período P) los requisitos de memoria.

El problema con el procedimiento anterior es que si mantenemos la información solo en los 10 términos principales para una ventana deslizante (de manera similar para todos los tiempos), entonces las estadísticas serán correctas para los términos de búsqueda que alcanzan el pico en un período, pero pueden no ver el estadísticas para los términos de búsqueda que se filtran constantemente en el tiempo.

Esto se puede compensar manteniendo la información en más de los 10 términos principales, por ejemplo, los 100 mejores términos, con la esperanza de que los 10 mejores estén correctos.

Creo que un análisis posterior podría relacionar el número mínimo de ocurrencias requeridas para que una entrada se convierta en una parte de las estadísticas (lo cual está relacionado con el error máximo).

(Al decidir qué entradas deberían formar parte de las estadísticas, también se podría monitorear y rastrear las tendencias, por ejemplo, si una extrapolación lineal de las ocurrencias en cada período P de cada término indica que el término será significativo en un mes o dos podría comenzar a rastrearlo. Se aplica un principio similar para eliminar el término de búsqueda del grupo rastreado).

El peor caso para lo anterior es cuando tiene muchos términos casi igualmente frecuentes y cambian todo el tiempo (por ejemplo, si solo realiza un seguimiento de 100 términos, si los 150 mejores se producen con la misma frecuencia, pero los primeros 50 son más frecuentes en el primer mes y no sea que a menudo algún tiempo después las estadísticas no se mantengan correctamente).

También podría haber otro enfoque que no está fijado en el tamaño de la memoria (en términos estrictos tampoco lo es el anterior), que definiría un significado mínimo en términos de ocurrencias / período (día, mes, año, de todos los tiempos) para mantener el estadísticas Esto podría garantizar un error máximo en cada una de las estadísticas durante la agregación (ver round robin nuevamente).

caso i)

Mantenga una tabla hash para todos los términos de búsqueda, así como una lista ordenada de los diez primeros, separada de la tabla hash. Siempre que ocurra una búsqueda, incremente el ítem apropiado en la tabla hash y verifique si ese ítem ahora debe cambiarse con el décimo ítem en la lista de los diez primeros.

O (1) busca la lista de los diez primeros, y la inserción máxima de O (log (n)) en la tabla hash (suponiendo que las colisiones sean administradas por un árbol binario autoequilibrado).

caso ii) En lugar de mantener una enorme tabla hash y una pequeña lista, mantenemos una tabla hash y una lista ordenada de todos los artículos. Cada vez que se realiza una búsqueda, ese término se incrementa en la tabla hash, y en la lista ordenada se puede verificar el término para ver si debe cambiar con el término siguiente. Un árbol binario autoequilibrado podría funcionar bien para esto, ya que también debemos poder consultarlo rápidamente (más sobre esto más adelante).

Además, también mantenemos una lista de ''horas'' en forma de una lista FIFO (cola). Cada elemento de "hora" contendría una lista de todas las búsquedas realizadas dentro de esa hora en particular. Entonces, por ejemplo, nuestra lista de horas podría verse así:

Time: 0 hours -Search Terms: -free stuff: 56 -funny pics: 321 -: 1234 Time: 1 hour -Search Terms: -ebay: 12 -funny pics: 1 -: 522 -BP sucks: 92

Luego, cada hora: si la lista tiene al menos 720 horas de duración (es decir, el número de horas en 30 días), observe el primer elemento de la lista y, para cada término de búsqueda, disminuya dicho elemento en la tabla hash en la cantidad adecuada . Después, elimine ese elemento de la primera hora de la lista.

Entonces digamos que estamos a la hora 721, y estamos listos para ver la primera hora en nuestra lista (arriba). Reduciríamos las cosas gratis en 56 en la tabla hashtable, las imágenes divertidas en 321, etc., y eliminaríamos la hora 0 de la lista por completo, ya que nunca más tendremos que volver a mirarla.

La razón por la que mantenemos una lista ordenada de todos los términos que permite consultas rápidas es porque cada hora después, a medida que avanzamos en los términos de búsqueda de hace 720 horas, debemos asegurarnos de que la lista de los diez primeros permanezca ordenada. Así que a medida que decrementamos "cosas gratis" por 56 en la tabla hash por ejemplo, verificamos para ver dónde ahora pertenece en la lista. Debido a que es un árbol binario autoequilibrado, todo eso se puede lograr muy bien en el tiempo O (log (n)).

Edición: precisión sacrificatoria para el espacio ...

También podría ser útil implementar una lista grande en la primera, como en la segunda. Luego, podríamos aplicar la siguiente optimización del espacio en ambos casos: ejecutar un trabajo cron para eliminar todos los elementos excepto x de la lista. Esto mantendría el requisito de espacio bajo (y como resultado, haría las consultas en la lista más rápido). Por supuesto, resultaría en un resultado aproximado, pero esto está permitido. x podría calcularse antes de implementar la aplicación según la memoria disponible y ajustarse dinámicamente si hay más memoria disponible.

The problem is not universally solvable when you have a fixed amount of memory and an ''infinite'' (think very very large) stream of tokens.

A rough explanation...

To see why, consider a token stream that has a particular token (ie, word) T every N tokens in the input stream.

Also, assume that the memory can hold references (word id and counts) to at most M tokens.

With these conditions, it is possible to construct an input stream where the token T will never be detected if the N is large enough so that the stream contains different M tokens between T''s.

This is independent of the top-N algorithm details. It only depends on the limit M.

To see why this is true, consider the incoming stream made up of groups of two identical tokens:

T a1 a2 a3 ... a-M T b1 b2 b3 ... b-M ...

where the a''s, and b''s are all valid tokens not equal to T.

Notice that in this stream, the T appears twice for each ai and bi. Yet it appears rarely enough to be flushed from the system.

Starting with an empty memory, the first token (T) will take up a slot in the memory (bounded by M). Then a1 will consume a slot, all the way to a-(M-1) when the M is exhausted.

Cuando llega aM, el algoritmo debe soltar un símbolo para que sea el T. El siguiente símbolo será b-1, lo que hará que a-1 se vacíe, etc.

Entonces, el T no permanecerá residente en memoria lo suficiente como para acumular un recuento real. En resumen, cualquier algoritmo perderá un token de frecuencia local suficientemente baja pero con una frecuencia global alta (a lo largo de la secuencia).