Fréquence D'Estimation De La "Vue D'Ensemble De 151910920"

il existe des algorithmes bien connus qui peuvent fournir des estimations de fréquence pour un tel flux en utilisant une quantité fixe de stockage. L'une est Frequent, de Misra et Gries (1982). À partir d'une liste de n articles, il trouver tous les éléments qui se produisent plus de n / k temps, en utilisant k - 1 compteurs. Il s'agit d'une généralisation de Boyer et Moore "151930920 de la" Majorité algorithme (Fischer-Salzberg, 1982), où k est de 2. Les algorithmes de Manku et Motwani LossyCounting (2002) et de Metwally SpaceSaving (2005) ont des besoins d'espace similaires, mais peuvent fournir des estimations plus précises sous certaines conditions.

il est important de se rappeler que ces algorithmes ne peuvent fournir que des estimations de fréquence. Plus précisément, l' L'estimation de Misra-Gries peut sous-compter la fréquence réelle par (n / k) items.

supposons que vous ayez un algorithme qui pourrait identifier positivement un article seulement si cela se produit plus de 50% du temps. Nourrir cet algorithme un flux de N articles distincts, puis ajouter un autre N - 1 des copies d'un article, x , pour un total de 2N - 1 articles. Si l'algorithme vous dit que x dépasse 50% du total, il doit avoir été dans le premier flux; si ce n'est pas le cas, x n'était pas dans le flux initial. Pour que l'algorithme puisse faire cette détermination, il doit stocker le flux initial (ou un résumé proportionnel à sa longueur)! Ainsi, nous pouvons nous prouver que l'espace requis par un tel algorithme "exact" serait Ω( N ).

au lieu de cela, ces algorithmes de fréquence décrits ici fournissent une estimation, identifiant tout élément qui dépasse le seuil, ainsi que certains éléments qui tombent en dessous de celui-ci d'une certaine marge. Par exemple, l'algorithme Majority , utilisant un seul compteur, donnera toujours un résultat; si un élément dépasse 50% du flux, il sera trouvé. Mais il pourrait également vous donner un élément qui se produit une seule fois. Vous ne le sauriez pas sans faire un second passage au-dessus des données (en utilisant, encore une fois, un seul comptoir, mais à la recherche seulement de cet article).

L'Algorithme Fréquent

Voici une description simple de L'algorithme Frequent de Misra-Gries. Demaine (2002) et d'autres ont optimisé l'algorithme, mais cela vous donne l'essentiel.

spécifier la fraction de seuil, 1 / k ; tout élément qui apparaît plus de n / k fois sera trouvé. Créer un carte vide (comme un arbre rouge-noir); les clés seront des termes de recherche, et les valeurs seront un compteur pour ce terme.

1. regardez chaque élément du flux.
2. Si le terme existe dans la carte, incrémenter les associés compteur.
3. Sinon, si la carte est inférieure aux entrées k - 1 , ajouter le terme à la carte avec un compteur de un.
4. cependant, si la carte a k - 1 entrées déjà, décrémenter le compteur dans chaque entrée. Si un compteur atteint zéro pendant ce processus, retirez-le de la carte.

notez que vous pouvez traiter une quantité infinie de données avec une quantité fixe de stockage (juste la carte de taille fixe). La quantité de stockage requise dépend uniquement du seuil d'intérêt, et la taille du flux n'a pas d'importance.

Compter Les Recherches

dans ce contexte, peut-être que vous amortissez une heure de recherches, et effectuez ce processus sur les données de cette heure. Si vous pouvez passer une seconde passe au-dessus du journal de recherche de cette heure, vous pouvez obtenir un compte exact des occurrences des "candidats" supérieurs identifiés dans la première passe. Ou, peut-être est-il acceptable de faire un seul passage, et de signaler tous les candidats, sachant que tout élément qui devrait être là est inclus, et tous les extras sont juste du bruit qui disparaîtra dans la prochaine heure.

tout candidat qui vraiment ne dépasser le seuil d'intérêt obtenir stocké comme un résumé. Gardez la valeur d'un mois de ces résumés, jeter les plus vieux chaque heure, et vous auriez une bonne approximation des termes de recherche les plus communs.

C'est un projet de recherche que je suis au courant. L'exigence est presque exactement comme la vôtre, et nous avons développé de beaux algorithmes pour résoudre le problème.

L'Entrée

l'entrée est un flot infini de mots ou de phrases en anglais (nous les appelons tokens ).

La Sortie

1. output n tokens nous avons vu jusqu' loin de tous les jetons que nous avons vu!)
2. tokens de sortie top N dans un fenêtre Historique, par exemple, dernier jour ou la semaine dernière.

une application de cette recherche est de trouver le sujet brûlant ou les tendances du sujet dans Twitter ou Facebook. Nous avons un reptile qui rampe sur le site web, qui génère un flux de mots, ce qui permettra d'alimenter le système. Ensuite, le système affichera les mots ou les phrases de haut en fréquence, soit en général ou historiquement. Imaginez qu'au cours des dernières semaines, L'expression "Coupe du monde" apparaîtrait plusieurs fois sur Twitter. Comme "Paul Le Poulpe". :)

chaîne en nombres entiers

le système a un entier ID pour chaque mot. Bien qu'il y ait presque une infinité de mots possibles sur Internet, mais après avoir accumulé un grand ensemble de mots, la possibilité de trouver de nouveaux mots devient de plus en plus faible. Nous avons déjà trouvé 4 millions de différent mots, et assigné un ID unique pour chacun. Cet ensemble de données peut être chargé dans la mémoire comme une table de hachage, consommant environ 300MO de mémoire. (Nous avons mis en place notre propre table de hachage. La Java de la mise en œuvre prend énorme surcharge de mémoire)

Chaque phrase peut alors être identifié comme un tableau d'entiers.

c'est important, parce que le tri et les comparaisons sur les entiers est beaucoup plus rapide que sur les chaînes.

Archivage Des Données

le système conserve des données d'archives pour chaque token. En gros, c'est des paires de (Token, Frequency) . Cependant, la table qui stocke les données serait si énorme telle que nous devons cloisonner la table physiquement. Une fois que le schéma de partition est basé sur les ngrams du token. Si le jeton est un seul mot, il est 1gram. Si le jeton est une phrase de deux mots, c'est 2gram. Et ce qui se passe. À peu près à 4gram nous avons 1 milliard de disques, avec une table de taille autour de 60 GO.

Traitement Des Flux Entrants

le système va absorber les phrases entrantes jusqu'à ce que la mémoire soit pleinement utilisée (Ya, nous avons besoin D'un MemoryManager). Après avoir pris N phrases et stocker dans la mémoire, le système marque une pause, et commence à tokenize chaque phrase en mots et phrases. Chaque jeton (mot ou phrase) est compté.

pour les jetons très fréquents, ils sont toujours gardés en mémoire. Pour moins les jetons fréquents, ils sont triés en fonction d'IDs (rappelez-vous que nous traduisons la chaîne dans un tableau d'entiers), et sérialisés dans un fichier disque.

(Cependant, pour votre problème, puisque vous ne comptez que les mots, alors vous pouvez mettre toute la carte de fréquence de mot dans la mémoire seulement. Une structure de données soigneusement conçue ne consommerait que 300 Mo de mémoire pour 4 millions de mots différents. Quelques conseils: utilisez ASCII char pour représenter les chaînes), et c'est très acceptable.

En attendant, il y aura un autre processus qui est activé une fois qu'il trouve n'importe quel dossier de disque généré par le système, puis commencer à le fusionner. Puisque le fichier disque est trié, la fusion prendrait un processus similaire comme le tri de fusion. Certains de conception doivent être pris en compte ici, car nous voulons éviter de trop aléatoire du disque cherche. L'idée est d'éviter de lire (processus de fusion)/écrire (sortie du système) en même temps, et de laisser le processus de fusion lire la forme d'un disque tout en écrivant dans un disque différent. C'est similaire à la mise en place d'un verrouillage.

fin de journée

à la fin de la journée, le système aura beaucoup de jetons fréquents avec une fréquence stockée en mémoire, et beaucoup d'autres jetons moins fréquents stockés dans plusieurs fichiers disque (et chaque fichier est trié).

le système chasse la carte en mémoire dans un fichier disque (le trier). Maintenant, le problème devient la fusion d'un ensemble de fichier disque trié. En utilisant un processus similaire, nous obtenez un fichier disque trié à la fin.

ensuite, la tâche finale est de fusionner le fichier disque trié dans la base de données d'archives. Dépend de la taille de la base de données d'archives, l'algorithme fonctionne comme ci-dessous si elle est assez 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

l'intuition est qu'après un certain temps, le nombre d'insertion deviendra de plus en plus petit. De plus en plus d'opérations se limiteront à la mise à jour. Et cette mise à jour ne sera pas pénalisée par index.

J'espère que toute cette explication nous aidera. :)

, Vous pouvez utiliser un table de hachage combiné avec un arbre de recherche binaire . Mettez en place un dictionnaire <search term, count> qui vous indique combien de fois chaque terme de recherche a été recherché.

évidemment itérer la table entière de hachage chaque heure pour obtenir le top 10 est très mauvais. Mais c'est google dont nous parlons, donc vous pouvez supposer que les dix premiers obtiendront tous, disons plus de 10 000 visites (il est probablement un nombre beaucoup plus grand bien). Donc chaque fois que le nombre d'un terme de recherche dépasse 10 000, insérez-le dans le BST. Puis toutes les heures, vous n'avez qu'à obtenir le premier 10 de la BST, qui devrait contenir relativement peu d'entrées.

Ce qui résout le problème de la top 10 de tous les temps.

la partie la plus délicate est de traiter d'un terme en prenant la place d'un autre dans le rapport mensuel (par exemple, "stack overflow" pourrait avoir 50 000 hits pour les deux derniers mois, mais seulement 10 000 le mois dernier, tandis que "amazon" peut avoir les 40 000 pour les deux derniers mois, mais 30 000 pour le mois passé. Vous voulez "amazon" avant de "stack overflow" dans votre rapport mensuel). Pour ce faire, je stockerais, pour tous les termes de recherche importants (plus de 10 000 recherches de tous les temps), une liste de 30 jours qui indique le nombre de fois où ce terme a été recherché chaque jour. La liste fonctionnerait comme une file D'attente FIFO: vous retirez le premier jour et insérez un nouveau chaque jour (ou chaque heure, mais alors vous pourriez avoir besoin de stocker plus d'informations, ce qui signifie plus de mémoire / espace. Si la mémoire n'est pas un problème le faire, sinon aller pour cette "approximation" dont ils parlent).

C'est un bon début. Vous pouvez alors vous soucier d'élaguer les termes qui ont > 10 000 hits mais n'ont pas eu beaucoup depuis longtemps et des trucs comme ça.

cas i)

maintient un hashtable pour tous les termes de recherche, ainsi qu'une liste triée top-ten séparée du hashtable. Chaque fois qu'une recherche se produit, incrémenter l'élément approprié dans le hashtable et vérifier pour voir si cet élément devrait maintenant être commuté avec le 10ème élément dans le top-ten liste.

O( 1) Recherche de la liste des dix premières et insertion de max O(log(n)) dans le hashtable (en supposant que les collisions gérées par un auto-équilibrage arbre binaire).

cas ii) Au lieu de maintenir un énorme hashtable et une petite liste, nous maintenons un hashtable et une liste triée de tous les articles. Chaque fois qu'une recherche est faite, ce terme est incrémenté dans le hashtable, et dans la liste triée le terme peut être vérifié pour voir s'il devrait changer avec le terme après lui. Un auto-équilibrage arbre binaire pourrait fonctionnent bien pour cela, que nous devons également être en mesure d'interroger rapidement (plus sur cela plus tard).

En outre, nous maintenons également une liste des "heures" sous la forme d'une liste FIFO (file d'attente). Chaque 'heure' élément doit contenir une liste de toutes les recherches effectuées au sein de cette heure. Ainsi, par exemple, notre liste d'heures pourrait ressembler à ceci:

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

puis, chaque heure: si la liste a au moins 720 heures (c'est le nombre d'heures en 30 jours), regardez le premier élément de la liste, et pour chaque terme de recherche, décrémentez cet élément dans le table de hachage par le montant approprié. Ensuite, supprimez cet élément de la première heure de la liste.

disons que nous en sommes à l'heure 721, et nous sommes prêts à regarder la première heure dans notre liste (ci-dessus). On décrémentait des trucs gratuits par 56 dans le hashtable, des photos drôles par 321,etc., et supprimerait alors hour 0 de la liste complètement puisque nous n'aurons plus jamais besoin de la regarder à nouveau.

la raison pour laquelle nous maintenons une liste triée de tous les termes qui permet des requêtes rapides c'est parce que chaque heure après en parcourant les termes de recherche d'il y a 720 heures, nous devons nous assurer que la liste des dix premiers reste triée. Alors que nous décrétons 'free stuff' par 56 dans le hashtable par exemple, nous vérifions pour voir où il appartient maintenant dans la liste. Parce que c'est un arbre binaire auto-équilibrant, tout cela peut être accompli en temps O(log(n)).

Edit: autant Sacrifier la précision de l'espace...

il pourrait être utile de aussi mettre en œuvre une grande liste dans le premier comme dans le second. Ensuite, nous pourrions appliquer l'optimisation de l'espace suivante sur les deux cas: exécuter une tâche cron pour supprimer tous les éléments sauf le haut x dans la liste. Cela permettrait de réduire l'espace requis (et, par conséquent, d'accélérer les requêtes sur la liste). Bien sûr, il en résulterait un résultat approximatif, mais c'est autorisé. x pourrait être calculé avant de déployer l'application sur la base des données disponibles mémoire, et ajustée dynamiquement si plus de mémoire devient disponible.

Rugueux de la pensée...

Pour le top 10 de tous les temps

• en utilisant une collection de hash où un nombre pour chaque terme est stocké (Termes d'assainissement, etc.)
• un tableau trié qui contient le top 10 en cours, un terme/count in ajouté à ce tableau chaque fois que le nombre d'un terme devient égal ou supérieur au plus petit nombre dans le tableau

Pour le mois top 10 mis à jour toutes les heures:

• utilisant un tableau indexé sur le nombre d'heures écoulées depuis le début modulo 744 (le nombre d'heures pendant un mois), les entrées de tableau se composent de collecte de hachage où un compte pour chaque terme rencontré au cours de cette heure-fente est stocké. Une entrée est réinitialisée chaque fois que le compteur de l'heure change
• les statistiques dans le tableau indexées sur Heure-slot doivent être recueillies chaque fois que le compteur heure-slot actuel change (une fois par heure au plus), en copiant et aplatir le contenu de ce tableau indexé sur les plages horaires

Errr... un sens? Je n'y ai pas réfléchi comme je le ferais dans la vraie vie

Ah oui, oublié de mentionner, la "copie/aplatissement" horaire requis pour les statistiques mensuelles peut effectivement réutiliser le même code utilisé pour le top 10 de tous les temps, un bel effet secondaire.

solution exacte

tout d'Abord, une solution qui garantit des résultats corrects, mais nécessite beaucoup de mémoire (une carte).

" tous les temps "variante

maintient une carte de hachage avec des requêtes comme clés et leurs comptes comme valeurs. En outre, gardez une liste des 10 requêtes les plus fréquentes jusqu'à présent et le compte du 10ème compte le plus fréquent (un seuil).

mettre à jour constamment la carte comme le flux de requêtes est lire. Chaque fois qu'un nombre dépasse le seuil actuel, faites ce qui suit: supprimez la 10ème requête de la liste "Top 10", remplacez-la par la requête que vous venez de mettre à jour, et mettez à jour le seuil aussi.

"variante du dernier mois

garder la même Liste" Top 10 " et la mettre à jour de la même façon que ci-dessus. Aussi, Gardez une carte similaire, mais ce temps stockent des vecteurs de 30*24 = 720 Compter (un pour chaque heure) comme des valeurs. Toutes les heures faites ce qui suit pour chaque clé: supprimer le compteur le plus ancien du vecteur ajouter un nouveau compteur (initialisé à 0) à la fin. Supprimer la touche de la carte si le vecteur est tout-Zéro. De plus, chaque heure, vous devez calculer la liste "Top 10" à partir de zéro.

Note: oui, cette fois nous stockons 720 entiers au lieu d'un, mais il y a beaucoup moins de clés (la variante de tous les temps a une vraiment longue queue).

Approximations

ces les approximations ne garantissent pas la solution correcte, mais consomment moins de mémoire.

1. traite chaque requête N-th, sautant le reste.
2. (pour la variante de tous les temps seulement) garder au plus m les paires de valeurs clés dans la carte (M devrait être aussi grand que vous pouvez vous permettre). C'est une sorte de cache LRU: chaque fois que vous lisez une requête qui n'est pas dans la carte, supprimez la requête la moins récente utilisée avec le compte 1 et remplacez-la par la requête actuellement traitée.

le Top 10 des termes de recherche pour le mois passé

utilisant une structure d'indexation/de données efficace en mémoire, telle que essais serrés (à partir des entrées Wikipédia sur essais ) définit approximativement une certaine relation entre les exigences de mémoire et n - nombre de termes.

dans le cas où la mémoire nécessaire est disponible ( hypothèse 1 ), vous pouvez garder exacte mensuelle statistique et agréger tous les mois dans la statistique de tous les temps.

il y a, aussi, une hypothèse ici qui interprète le 'dernier mois' comme fenêtre fixe. Mais même si la fenêtre mensuelle glisse la procédure ci-dessus montre le principe (glissement peut être approximé avec des fenêtres fixes de taille donnée).

cela me rappelle round-robin database à l'exception que certaines statistiques sont calculées sur "tout le temps" (dans un sens que toutes les données ne sont pas conservées; rrd consolide les périodes sans tenir compte des détails en faisant la moyenne, en faisant la somme ou en choisissant des valeurs max/min, dans une tâche donnée le détail qui est perdu est de l'information sur des éléments de basse fréquence, ce qui peut introduire des erreurs).

hypothèse 1

si nous ne pouvons pas tenir des statistiques parfaites pour tout le mois, alors nous devrions être en mesure de trouver une certaine période P pour laquelle nous devrions être en mesure de tenir des statistiques parfaites. Exemple, en supposant que nous avons des statistiques parfaites sur une certaine période de temps P, qui va dans le mois n fois.

Perfect stats définit la fonction f(search_term) -> search_term_occurance .

si nous pouvons garder toutes les tables n perfect stat en mémoire, alors les statistiques mensuelles glissantes peuvent être calculées comme ceci:

• ajouter des statistiques pour la nouvelle période
• supprimer les statistiques pour la période la plus ancienne (nous devons donc garder n parfait stat tableaux)

cependant, si nous ne conservons que le top 10 au niveau agrégé (mensuel), nous serons en mesure de rejeter une grande quantité de données provenant des statistiques complètes de la période fixe. Cela donne déjà une procédure de travail qui a fixé (en supposant limite supérieure sur la table de stat parfaite pour la période P) les exigences de mémoire.

le problème avec la procédure ci-dessus est que si nous gardons l'information sur seulement les 10 premiers termes pour une fenêtre coulissante (de même pour tout le temps), alors les statistiques vont être correctes pour les termes de recherche qui culminent dans une période, mais pourraient ne pas voir les statistiques pour les termes de recherche qui coulent dans constamment au fil du temps.

ceci peut être compensé en gardant l'information sur plus de 10 Top terms, par exemple top 100 terms, en espérant que le top 10 sera correct.

je pense qu'une analyse plus poussée pourrait établir un lien entre le nombre minimum d'événements requis pour qu'une entrée fasse partie des statistiques (ce qui est lié au nombre maximum erreur.)

(en décidant quelles entrées devraient faire partie des statistiques, on pourrait également surveiller et suivre les tendances; par exemple, si une extrapolation linéaire des événements dans chaque période P pour chaque terme vous dit que le terme deviendra significatif dans un mois ou deux, vous pourriez déjà commencer à le suivre. Un principe similaire s'applique pour supprimer le terme de recherche du groupe de suivi.)

le pire cas pour ce qui précède est quand vous avez beaucoup de presque termes tout aussi fréquents et ils changent tout le temps (par exemple si le suivi de seulement 100 Termes, puis si les 150 premiers termes se produisent également fréquemment, mais les 50 premiers sont plus souvent dans le premier mois et de peur souvent plus tard, alors les statistiques ne seraient pas tenues correctement).

il pourrait également y avoir une autre approche qui n'est pas fixe dans la taille de la mémoire (bien à proprement parler ni est le ci-dessus), qui définirait la signification minimale en termes d'occurrences / période (Jour, Mois, Année, tous les temps) pour lequel garder les statistiques. Cela pourrait garantir une erreur maximale dans chacune des statistiques au cours de l'agrégation (voir à nouveau round robin).

Qu'en est-il d'une adaptation de "algorithme de remplacement de la page d'horloge" (également connu sous le nom de "deuxième chance")? Je peux imaginer que cela fonctionne très bien si les requêtes de recherche sont réparties uniformément (Cela signifie que la plupart des termes recherchés apparaissent régulièrement plutôt que 5mio fois d'affilée et puis jamais plus).

Voici une représentation visuelle de l'algorithme:

stocke le nombre de termes de recherche dans une table de hachage géante, où chaque nouvelle recherche provoque un élément particulier d'être incrémenté par un. Gardez la trace des 20 premiers termes de recherche; lorsque l'élément à la 11ème place est incrémenté, Vérifiez s'il a besoin d'échanger des positions avec le #10* (il n'est pas nécessaire de garder les 10 premiers triés; tout ce qui vous intéresse est de faire la distinction entre la 10ème et la 11ème place).

* _{des contrôles similaires doivent être effectués pour voir si une nouvelle recherche le terme est à la 11ème place, donc cet algorithme descend à d'autres termes de recherche aussi -- donc je simplifie un peu.}

parfois, la meilleure réponse est "je ne sais pas".

je vais prendre un coup plus profond. Mon premier instinct serait de nourrir les résultats dans un Q. un processus traiterait continuellement des articles entrant dans le Q. le processus maintiendrait une carte de

terme -> count

chaque fois qu'un élément Q est traité, il vous suffit de chercher le terme de recherche et incrémenter le nombre.

en même temps, je maintiendrais une liste de références aux 10 premières entrées de la carte.

pour l'entrée qui a été actuellement mise en œuvre, voir si son nombre est supérieur au nombre de la plus petite entrée dans le top 10.(si pas dans la liste déjà). Si c'est, remplacer le plus petit avec l'entrée.

je pense que ça marcherait. Aucune opération n'exige beaucoup de temps. Vous devez trouver un moyen de gérer la taille de l'compter de la carte. mais ça devrait bien assez pour une entrevue réponse.

ils ne s'attendent pas à une solution, qui veulent voir si vous pouvez penser. Vous n'avez pas à écrire la solution....

une façon est que pour chaque recherche, vous stockez ce terme de recherche et son horodatage. De cette façon, il suffit de comparer tous les termes de recherche au cours d'une période donnée pour trouver les dix premiers.

l'algorithme est simple, mais l'inconvénient serait une plus grande consommation de mémoire et de temps.

Qu'en est-il de l'utilisation d'un Splay Tree avec 10 noeuds? Chaque fois que vous essayez d'accéder à une valeur (terme de recherche) qui n'est pas contenu dans l'arbre, jeter une feuille, insérer la valeur à la place et y accéder.

l'idée derrière ceci est la même que dans mon autre réponse . Sous l'hypothèse que les termes de recherche sont accessibles uniformément/régulièrement cette solution doit effectuer très bien.

modifier

on pourrait également stocker quelques termes de recherche supplémentaires dans l'arbre (la même chose vaut pour la solution que je suggère dans mon autre réponse) afin de ne pas supprimer un noeud qui pourrait être accédé très bientôt à nouveau. Plus on y stocke de valeurs, meilleurs sont les résultats.

Je ne sais pas si je le comprends bien ou pas. Ma solution est d'utiliser heap. À cause du top 10 des objets de recherche, je construis un tas avec la taille 10. Puis mettez à jour ce tas avec une nouvelle recherche. Si la fréquence d'une nouvelle recherche est supérieure à heap(Max Heap) top, mettez-la à jour. Abandonner celui avec la plus petite fréquence.

Mais, comment calculer la fréquence de la recherche spécifique sera compté sur quelque chose d'autre. Peut-être, comme tout le monde l'a dit, l'algorithme du flux de données....

utiliser cm-sketch pour stocker le compte de toutes les recherches depuis le début, garder un Min-tas de taille 10 avec elle pour le top 10. Pour le résultat mensuel, garder 30 cm-croquis / hachoir-table et min-tas avec elle, chacun commence à compter et à mettre à jour à partir de 30, 29 derniers .. 1 journée. Comme un passage de jour, le dernier et l'utiliser comme le jour 1. Idem pour le résultat horaire, garder 60 table de hachage et min-heap et commencer à compter pour les derniers 60, 59,...1 minute. Une minute passe, le dernier et l'utiliser comme 1 minute.

Le résultat mensuel est précis dans l'intervalle de 1 jour, le résultat horaire est précis dans l'intervalle de 1 min 151910920"

le problème n'est pas universellement résolu lorsque vous avez une quantité fixe de mémoire et un flux infini (pensez très grand) de jetons.

une explication grossière...

pour voir pourquoi, considérez un flux de tokens qui a un token particulier (i.e., mot) T Chaque n tokens dans le flux d'entrée.

aussi, supposons que la mémoire puisse contenir des références (mot id et compte) au plus des jetons M.

avec dans ces conditions, il est possible de construire un flux d'entrée où le token T ne sera jamais détecté si N est assez grand pour que le flux contienne des tokens m différents entre les T.

ceci est indépendant des détails de l'algorithme top-N. Elle dépend seulement de la limite M.

pour voir pourquoi c'est vrai, considérez le flux entrant composé de groupes de deux jetons identiques:

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

où les a, et les b sont tous les jetons valides ne sont pas égaux à T.

notez que dans ce flux, le T apparaît deux fois pour chaque a-i et b-I. Pourtant, il semble rarement suffisant pour être évacué du système.

à partir d'une mémoire vide, le premier token (T) occupera une fente dans la mémoire (délimitée par M). Alors a1 consommera une fente, tout le chemin à a-(M-1) Quand le M est épuisé.

quand a-M arrive l'algorithme doit laisser tomber un symbole alors que ce soit le T. Le le symbole suivant sera b-1 qui fera rougir a-1, etc.

donc, le T ne restera pas en mémoire assez longtemps pour construire un vrai compte. En bref, tout algorithme manquera un jeton de fréquence locale assez basse mais de fréquence globale élevée (sur la longueur du flux).