C'est l'un des projet de recherche que je suis au courant. L'exigence est presque exactement comme le vôtre, et nous avons développé de nice algorithmes pour résoudre le problème.
L'Entrée
L'entrée est un flux sans fin de l'anglais des mots ou des phrases (nous nous référons comme tokens).
La Sortie
- Sortie top N jetons que nous avons vu jusqu'
loin de tous les jetons que nous avons
vu!)
- Sortie top N jetons dans un
historique de la fenêtre, disons, dernier jour ou
la semaine dernière.
Une application de cette recherche est de trouver le sujet d'actualité et les tendances de 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 fréquence supérieure soit globale ou historique. Imaginez dans les deux dernières semaines, le membre de phrase "Coupe du Monde" seraient apparaît de nombreuses fois dans Twitter. Ne sorte de "Paul le poulpe". :)
Chaîne de caractères en nombres Entiers
Le système a un nombre entier ID pour chaque mot. Bien qu'il est presque infini de mots possibles sur Internet, mais après avoir accumulé un grand nombre de mots, la possibilité de trouver de nouveaux mots devient de plus en plus bas. Nous avons déjà trouvé 4 millions de mots différents, et d'attribuer un IDENTIFIANT unique pour chaque. 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 la mémoire)
Chaque phrase peut alors être identifié comme un tableau d'entiers.
Ceci est important, car de tri et de comparaisons sur des entiers est beaucoup plus rapide que sur les cordes.
L'Archivage De Données
Le système permet d'archiver des données pour chaque jeton. En gros, c'est des paires d' (Token, Frequency). Toutefois, la table qui stocke les données seraient énormes, tels que nous avons à la partition de la table physiquement. Une fois que la partition système est fondé sur ngrams du jeton. Si le jeton est un seul mot, il est 1gram. Si le jeton est de deux mots de la phrase, il est 2gram. Et ce qui se passe. À peu près à 4gram nous avons 1 milliard d'enregistrements, avec une table de taille moyenne autour de 60 GO.
Le Traitement Des Flux Entrants
Le système absorbe entrant phrases jusqu'à ce que la mémoire devient pleinement utilisé (Ya, nous avons besoin d'un MemoryManager). Après la prise de la N des phrases et de la stocker dans la mémoire, le système s'arrête, et commence à marquer chaque phrase en mots et en phrases. Chaque jeton (mot ou phrase) est compté.
Pour les très fréquentes jetons, ils sont toujours gardés en mémoire. Pour les moins fréquentes jetons, ils sont triés en fonction Id (souvenez-vous de nous traduire la Chaîne dans un tableau de nombres entiers), et sérialisée dans un fichier sur disque.
(Cependant, pour votre problème, puisque vous comptez uniquement sur les mots, alors vous pouvez mettre tous les mot-fréquence de la carte dans la mémoire. Soigneusement conçu la structure de données de la consommer seulement 300 MO de mémoire pour 4 millions de mots différents. Un indice: utiliser des caractères ASCII dans le fichier pour représenter des Chaînes de caractères), et c'est tout à fait acceptable.
Pendant ce temps, il y aura un autre processus qui est activé une fois qu'il trouve un fichier de disque généré par le système, puis commencer à fusionner. Depuis le disque fichier est trié, la fusion prendrait un processus similaire comme la fusion de tri. 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)/write (sortie du système) en même temps, et de laisser le processus de fusion de lire un disque lors de l'écriture sur un disque différent. C'est comme pour la mise en œuvre d'un verrouillage.
En fin de Journée
À la fin de la journée, le système aura beaucoup de fréquentes jetons avec la fréquence enregistrée dans la mémoire, et beaucoup d'autres moins fréquentes jetons stockées dans plusieurs fichiers de disque (et chaque fichier est trié).
La purge du système de la carte mémoire dans un fichier de disque (tri). Maintenant, le problème devient de la fusion d'un ensemble de triés fichier de disque. A l'aide du même processus, on obtient une triés fichier de disque à la fin.
Ensuite, la tâche finale consiste à fusionner la triées disque fichier dans l'archive de la base de données.
Dépend de la taille de l'archive de la base de données, 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 que, après un certain temps, le nombre d'insertion va devenir de plus en plus petites. De plus en plus et de l'opération de mise à jour uniquement. Et cette mise à jour ne sera pas pénalisé par l'index.
Espérons que toute cette explication pourrait l'aider. :)
