C'est peut-être l'un des défis de codage classiques qui ont trouvé un écho en 1986, lorsque le chroniqueur Jon Bentley a demandé à Donald Knuth d'écrire un programme qui trouverait k mots les plus fréquents dans un fichier. Knuth a implémenté une solution rapide utilisant des tentatives de hachage dans un programme de 8 pages pour illustrer sa technique de programmation lettrée. Douglas McIlroy de Bell Labs a critiqué la solution de Knuth comme ne pouvant même pas traiter un texte intégral de la Bible, et a répondu avec une seule ligne, ce n'est pas aussi rapide, mais fait le travail:

tr -cs A-Za-z '\n' | tr A-Z a-z | sort | uniq -c | sort -rn | sed 10q

En 1987, un article de suivi été publié avec encore une autre solution, cette fois par un professeur de Princeton. Mais cela ne pouvait même pas retourner le résultat d'une seule Bible!

Description du problème

Description originale du problème:

Étant donné un fichier texte et un entier k, vous devez imprimer les k mots les plus courants dans le fichier (et le nombre de leurs occurrences) en fréquence décroissante.

Clarifications supplémentaires sur les problèmes:

• Knuth a défini un mot comme une chaîne de lettres latines: [A-Za-z]+
• tous les autres personnages sont ignorés
• les lettres majuscules et minuscules sont considérées comme équivalentes ( WoRd== word)
• pas de limite de taille de fichier ni de longueur de mot
• les distances entre les mots consécutifs peuvent être arbitrairement grandes
• le programme le plus rapide est celui qui utilise le moins de temps CPU total (le multithreading n'aidera probablement pas)

Exemples de cas de test

Test 1: Ulysse de James Joyce concaténé 64 fois (fichier de 96 Mo).

• Téléchargez Ulysse depuis le projet Gutenberg:wget http://www.gutenberg.org/files/4300/4300-0.txt
• Concaténer 64 fois: for i in {1..64}; do cat 4300-0.txt >> ulysses64; done
• Le mot le plus fréquent est «le» avec 968832 apparitions.

Test 2: texte aléatoire spécialement généré giganovel(environ 1 Go).

• Script du générateur Python 3 ici .
• Le texte contient 148391 mots distincts apparaissant de manière similaire aux langues naturelles.
• Mots les plus fréquents: «e» (11309 apparitions) et «ihit» (11290 apparitions).

Test de généralité: mots arbitrairement grands avec des écarts arbitrairement grands.

Implémentations de référence

Après avoir examiné le code Rosetta pour ce problème et réalisé que de nombreuses implémentations sont incroyablement lentes (plus lentes que le script shell!), J'ai testé quelques bonnes implémentations ici . Vous trouverez ci-dessous les performances ulysses64ainsi que la complexité du temps:

                                     ulysses64      Time complexity
C++ (prefix trie + heap)             4.145          O((N + k) log k)
Python (Counter)                     10.547         O(N + k log Q)
AWK + sort                           20.606         O(N + Q log Q)
McIlroy (tr + sort + uniq)           43.554         O(N log N)

Pouvez-vous battre ça?

Essai

Les performances seront évaluées à l'aide du MacBook Pro 13 pouces 2017 avec le standard Unix time commande (heure "utilisateur"). Si possible, utilisez des compilateurs modernes (par exemple, utilisez la dernière version de Haskell, pas la version héritée).

Classements jusqu'à présent

Horaires, y compris les programmes de référence:

                                              k=10                  k=100K
                                     ulysses64      giganovel      giganovel
C++ (trie) by ShreevatsaR            0.671          4.227          4.276
C (trie + bins) by Moogie            0.704          9.568          9.459
C (trie + list) by Moogie            0.767          6.051          82.306
C++ (hash trie) by ShreevatsaR       0.788          5.283          5.390
C (trie + sorted list) by Moogie     0.804          7.076          x
Rust (trie) by Anders Kaseorg        0.842          6.932          7.503
J by miles                           1.273          22.365         22.637
C# (trie) by recursive               3.722          25.378         24.771
C++ (trie + heap)                    4.145          42.631         72.138
APL (Dyalog Unicode) by Adám         7.680          x              x
Python (dict) by movatica            9.387          99.118         100.859
Python (Counter)                     10.547         102.822        103.930
Ruby (tally) by daniero              15.139         171.095        171.551
AWK + sort                           20.606         213.366        222.782
McIlroy (tr + sort + uniq)           43.554         715.602        750.420

Classement cumulatif * (%, meilleur score possible - 300):

#     Program                         Score  Generality
 1  C++ (trie) by ShreevatsaR           300     Yes
 2  C++ (hash trie) by ShreevatsaR      368      x
 3  Rust (trie) by Anders Kaseorg       465     Yes
 4  C (trie + bins) by Moogie           552      x
 5  J by miles                         1248     Yes
 6  C# (trie) by recursive             1734      x
 7  C (trie + list) by Moogie          2182      x
 8  C++ (trie + heap)                  3313      x
 9  Python (dict) by movatica          6103     Yes
10  Python (Counter)                   6435     Yes
11  Ruby (tally) by daniero           10316     Yes
12  AWK + sort                        13329     Yes
13  McIlroy (tr + sort + uniq)        40970     Yes

* Somme des performances temporelles par rapport aux meilleurs programmes dans chacun des trois tests.

Meilleur programme à ce jour: ici (deuxième solution)

[C]

Ce qui suit s'exécute en moins de 1,6 seconde pour le test 1 sur mon 2.8 Ghz Xeon W3530. Construit à l'aide de MinGW.org GCC-6.3.0-1 sur Windows 7:

Il prend deux arguments en entrée (chemin vers le fichier texte et pour k nombre de mots les plus fréquents à lister)

Il crée simplement un arbre ramifié sur des lettres de mots, puis au niveau des lettres foliaires, il incrémente un compteur. Vérifie ensuite si le compteur de feuilles actuel est supérieur au plus petit mot le plus fréquent dans la liste des mots les plus fréquents. (la taille de la liste est le nombre déterminé via l'argument de la ligne de commande) Si c'est le cas, promouvez le mot représenté par la lettre feuille comme l'un des plus fréquents. Tout cela se répète jusqu'à ce qu'aucune autre lettre ne soit lue. Après quoi la liste des mots les plus fréquents est sortie via une recherche itérative inefficace du mot le plus fréquent dans la liste des mots les plus fréquents.

Par défaut, il affiche actuellement le temps de traitement, mais à des fins de cohérence avec les autres soumissions, désactivez la définition de TIMING dans le code source.

De plus, je l'ai soumis à partir d'un ordinateur de travail et je n'ai pas pu télécharger le texte du test 2. Il devrait fonctionner avec ce test 2 sans modification, mais la valeur MAX_LETTER_INSTANCES devra peut-être être augmentée.

// comment out TIMING if using external program timing mechanism
#define TIMING 1

// may need to increase if the source text has many unique words
#define MAX_LETTER_INSTANCES 1000000

// increase this if needing to output more top frequent words
#define MAX_TOP_FREQUENT_WORDS 1000

#define false 0
#define true 1
#define null 0

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifdef TIMING
#include <sys/time.h>
#endif

struct Letter
{
    char mostFrequentWord;
    struct Letter* parent;
    char asciiCode;
    unsigned int count;
    struct Letter* nextLetters[26];
};
typedef struct Letter Letter;

int main(int argc, char *argv[]) 
{
#ifdef TIMING
    struct timeval tv1, tv2;
    gettimeofday(&tv1, null);
#endif

    int k;
    if (argc !=3 || (k = atoi(argv[2])) <= 0 || k> MAX_TOP_FREQUENT_WORDS)
    {
        printf("Usage:\n");
        printf("      WordCount <input file path> <number of most frequent words to find>\n");
        printf("NOTE: upto %d most frequent words can be requested\n\n",MAX_TOP_FREQUENT_WORDS);
        return -1;
    }

    long  file_size;
    long dataLength;
    char* data;

    // read in file contents
    FILE *fptr;
    size_t read_s = 0;  
    fptr = fopen(argv[1], "rb");
    fseek(fptr, 0L, SEEK_END);
    dataLength = ftell(fptr);
    rewind(fptr);
    data = (char*)malloc((dataLength));
    read_s = fread(data, 1, dataLength, fptr);
    if (fptr) fclose(fptr);

    unsigned int chr;
    unsigned int i;

    // working memory of letters
    Letter* letters = (Letter*) malloc(sizeof(Letter) * MAX_LETTER_INSTANCES);
    memset(&letters[0], 0, sizeof( Letter) * MAX_LETTER_INSTANCES);

    // the index of the next unused letter
    unsigned int letterMasterIndex=0;

    // pesudo letter representing the starting point of any word
    Letter* root = &letters[letterMasterIndex++];

    // the current letter in the word being processed
    Letter* currentLetter = root;
    root->mostFrequentWord = false;
    root->count = 0;

    // the next letter to be processed
    Letter* nextLetter = null;

    // store of the top most frequent words
    Letter* topWords[MAX_TOP_FREQUENT_WORDS];

    // initialise the top most frequent words
    for (i = 0; i<k; i++)
    {
        topWords[i]=root;
    }

    unsigned int lowestWordCount = 0;
    unsigned int lowestWordIndex = 0;
    unsigned int highestWordCount = 0;
    unsigned int highestWordIndex = 0;

    // main loop
    for (int j=0;j<dataLength;j++)
    {
        chr = data[j]|0x20; // convert to lower case

        // is a letter?
        if (chr > 96 && chr < 123)
        {
            chr-=97; // translate to be zero indexed
            nextLetter = currentLetter->nextLetters[chr];

            // this is a new letter at this word length, intialise the new letter
            if (nextLetter == null)
            {
                nextLetter = &letters[letterMasterIndex++];
                nextLetter->parent = currentLetter;
                nextLetter->asciiCode = chr;
                currentLetter->nextLetters[chr] = nextLetter;
            }

            currentLetter = nextLetter;
        }
        // not a letter so this means the current letter is the last letter of a word (if any letters)
        else if (currentLetter!=root)
        {

            // increment the count of the full word that this letter represents
            ++currentLetter->count;

            // ignore this word if already identified as a most frequent word
            if (!currentLetter->mostFrequentWord)
            {
                // update the list of most frequent words
                // by replacing the most infrequent top word if this word is more frequent
                if (currentLetter->count> lowestWordCount)
                {
                    currentLetter->mostFrequentWord = true;
                    topWords[lowestWordIndex]->mostFrequentWord = false;
                    topWords[lowestWordIndex] = currentLetter;
                    lowestWordCount = currentLetter->count;

                    // update the index and count of the next most infrequent top word
                    for (i=0;i<k; i++)
                    {
                        // if the topword  is root then it can immediately be replaced by this current word, otherwise test
                        // whether the top word is less than the lowest word count
                        if (topWords[i]==root || topWords[i]->count<lowestWordCount)
                        {
                            lowestWordCount = topWords[i]->count;
                            lowestWordIndex = i;
                        }
                    }
                }
            }

            // reset the letter path representing the word
            currentLetter = root;
        }
    }

    // print out the top frequent words and counts
    char string[256];
    char tmp[256];

    while (k > 0 )
    {
        highestWordCount = 0;
        string[0]=0;
        tmp[0]=0;

        // find next most frequent word
        for (i=0;i<k; i++)
        {
            if (topWords[i]->count>highestWordCount)
            {
                highestWordCount = topWords[i]->count;
                highestWordIndex = i;
            }
        }

        Letter* letter = topWords[highestWordIndex];

        // swap the end top word with the found word and decrement the number of top words
        topWords[highestWordIndex] = topWords[--k];

        if (highestWordCount > 0)
        {
            // construct string of letters to form the word
            while (letter != root)
            {
                memmove(&tmp[1],&string[0],255);
                tmp[0]=letter->asciiCode+97;
                memmove(&string[0],&tmp[0],255);
                letter=letter->parent;
            }

            printf("%u %s\n",highestWordCount,string);
        }
    }

    free( data );
    free( letters );

#ifdef TIMING   
    gettimeofday(&tv2, null);
    printf("\nTime Taken: %f seconds\n", (double) (tv2.tv_usec - tv1.tv_usec)/1000000 + (double) (tv2.tv_sec - tv1.tv_sec));
#endif
    return 0;
}

Pour le test 1, et pour les 10 premiers mots fréquents et avec le temps activé, il devrait imprimer:

 968832 the
 528960 of
 466432 and
 421184 a
 322624 to
 320512 in
 270528 he
 213120 his
 191808 i
 182144 s

 Time Taken: 1.549155 seconds

Rouille

Sur mon ordinateur, cela exécute giganovel 100000 environ 42% plus rapidement (10,64 s contre 18,24 s) que la solution C de Moogie «préfixe d'arbre + bacs». De plus, il n'a pas de limites prédéfinies (contrairement à la solution C qui prédéfinit les limites sur la longueur des mots, les mots uniques, les mots répétés, etc.).

src/main.rs

use memmap::MmapOptions;
use pdqselect::select_by_key;
use std::cmp::Reverse;
use std::default::Default;
use std::env::args;
use std::fs::File;
use std::io::{self, Write};
use typed_arena::Arena;

#[derive(Default)]
struct Trie<'a> {
    nodes: [Option<&'a mut Trie<'a>>; 26],
    count: u64,
}

fn main() -> io::Result<()> {
    // Parse arguments
    let mut args = args();
    args.next().unwrap();
    let filename = args.next().unwrap();
    let size = args.next().unwrap().parse().unwrap();

    // Open input
    let file = File::open(filename)?;
    let mmap = unsafe { MmapOptions::new().map(&file)? };

    // Build trie
    let arena = Arena::new();
    let mut num_words = 0;
    let mut root = Trie::default();
    {
        let mut node = &mut root;
        for byte in &mmap[..] {
            let letter = (byte | 32).wrapping_sub(b'a');
            if let Some(child) = node.nodes.get_mut(letter as usize) {
                node = child.get_or_insert_with(|| {
                    num_words += 1;
                    arena.alloc(Default::default())
                });
            } else {
                node.count += 1;
                node = &mut root;
            }
        }
        node.count += 1;
    }

    // Extract all counts
    let mut index = 0;
    let mut counts = Vec::with_capacity(num_words);
    let mut stack = vec![root.nodes.iter()];
    'a: while let Some(frame) = stack.last_mut() {
        while let Some(child) = frame.next() {
            if let Some(child) = child {
                if child.count != 0 {
                    counts.push((child.count, index));
                    index += 1;
                }
                stack.push(child.nodes.iter());
                continue 'a;
            }
        }
        stack.pop();
    }

    // Find frequent counts
    select_by_key(&mut counts, size, |&(count, _)| Reverse(count));
    // Or, in nightly Rust:
    //counts.partition_at_index_by_key(size, |&(count, _)| Reverse(count));

    // Extract frequent words
    let size = size.min(counts.len());
    counts[0..size].sort_by_key(|&(_, index)| index);
    let mut out = Vec::with_capacity(size);
    let mut it = counts[0..size].iter();
    if let Some(mut next) = it.next() {
        index = 0;
        stack.push(root.nodes.iter());
        let mut word = vec![b'a' - 1];
        'b: while let Some(frame) = stack.last_mut() {
            while let Some(child) = frame.next() {
                *word.last_mut().unwrap() += 1;
                if let Some(child) = child {
                    if child.count != 0 {
                        if index == next.1 {
                            out.push((word.to_vec(), next.0));
                            if let Some(next1) = it.next() {
                                next = next1;
                            } else {
                                break 'b;
                            }
                        }
                        index += 1;
                    }
                    stack.push(child.nodes.iter());
                    word.push(b'a' - 1);
                    continue 'b;
                }
            }
            stack.pop();
            word.pop();
        }
    }
    out.sort_by_key(|&(_, count)| Reverse(count));

    // Print results
    let stdout = io::stdout();
    let mut stdout = io::BufWriter::new(stdout.lock());
    for (word, count) in out {
        stdout.write_all(&word)?;
        writeln!(stdout, " {}", count)?;
    }

    Ok(())
}

Cargo.toml

[package]
name = "frequent"
version = "0.1.0"
authors = ["Anders Kaseorg <[email protected]>"]
edition = "2018"

[dependencies]
memmap = "0.7.0"
typed-arena = "1.4.1"
pdqselect = "0.1.0"

[profile.release]
lto = true
opt-level = 3

Usage

cargo build --release
time target/release/frequent ulysses64 10

APL (Dyalog Unicode)

Les éléments suivants s'exécutent en moins de 8 secondes sur mon i7-4720HQ 2,6 GHz utilisant Dyalog APL 17.0 64 bits sous Windows 10:

⎕{m[⍺↑⍒⊢/m←{(⊂⎕UCS⊃⍺),≢⍵}⌸(⊢⊆⍨96∘<∧<∘123)83⎕DR 819⌶80 ¯1⎕MAP⍵;]}⍞

Il demande d'abord le nom du fichier, puis k. Notez qu'une partie importante du temps d'exécution (environ 1 seconde) ne fait que lire le fichier.

Pour le chronométrer, vous devriez pouvoir diriger ce qui suit dans votre dyalogexécutable (pour les dix mots les plus fréquents):

⎕{m[⍺↑⍒⊢/m←{(⊂⎕UCS⊃⍺),≢⍵}⌸(⊢⊆⍨96∘<∧<∘123)83⎕DR 819⌶80 ¯1⎕MAP⍵;]}⍞
/tmp/ulysses64
10
⎕OFF

Il devrait imprimer:

 the  968832
 of   528960
 and  466432
 a    421184
 to   322624
 in   320512
 he   270528
 his  213120
 i    191808
 s    182144

[C] Arbre de préfixe + bacs

NOTE: Le compilateur utilisé a un effet significatif sur la vitesse d'exécution du programme! J'ai utilisé gcc (MinGW.org GCC-8.2.0-3) 8.2.0. Lorsque vous utilisez lecommutateur -Ofast , le programme s'exécute presque 50% plus rapidement que le programme normalement compilé.

Complexité de l'algorithme

Depuis, je me rends compte que le tri des bacs que j'effectue est une forme de tri Pigeonhost, ce qui signifie que je peux déterminer la complexité Big O de cette solution.

Je le calcule:

Worst Time complexity: O(1 + N + k)
Worst Space complexity: O(26*M + N + n) = O(M + N + n)

Where N is the number of words of the data
and M is the number of letters of the data
and n is the range of pigeon holes
and k is the desired number of sorted words to return
and N<=M

La complexité de la construction de l'arbre est équivalente à la traversée de l'arbre, car à n'importe quel niveau le nœud correct à parcourir est O (1) (car chaque lettre est mappée directement sur un nœud et nous ne traversons toujours qu'un niveau de l'arbre pour chaque lettre)

Le tri des trous de pigeon est O (N + n) où n est la plage de valeurs clés, mais pour ce problème, nous n'avons pas besoin de trier toutes les valeurs, uniquement le nombre k, le pire des cas serait donc O (N + k).

La combinaison des deux donne O (1 + N + k).

La complexité spatiale pour la construction d'arbres est due au fait que le pire des cas est de 26 * M nœuds si les données se composent d'un mot avec M nombre de lettres et que chaque nœud a 26 nœuds (c'est-à-dire pour les lettres de l'alphabet). Ainsi O (26 * M) = O (M)

Pour le Pigeon Hole, le tri a une complexité spatiale de O (N + n)

La combinaison des rendements donne O (26 * M + N + n) = O (M + N + n)

Algorithme

Il prend deux arguments en entrée (chemin vers le fichier texte et pour k nombre de mots les plus fréquents à lister)

Sur la base de mes autres entrées, cette version a une très petite rampe de coût en temps avec des valeurs croissantes de k par rapport à mes autres solutions. Mais est sensiblement plus lent pour les faibles valeurs de k, mais il devrait être beaucoup plus rapide pour les grandes valeurs de k.

Il crée un arbre ramifié sur des lettres de mots, puis au niveau des lettres foliaires, il incrémente un compteur. Ajoute ensuite le mot à un groupe de mots de la même taille (après avoir d'abord supprimé le mot du groupe, il résidait déjà). Tout cela se répète jusqu'à ce qu'aucune autre lettre ne soit lue. Après quoi, les bacs sont inversés k fois à partir du plus grand bac et les mots de chaque bac sont sortis.

Par défaut, il affiche actuellement le temps de traitement, mais à des fins de cohérence avec les autres soumissions, désactivez la définition de TIMING dans le code source.

// comment out TIMING if using external program timing mechanism
#define TIMING 1

// may need to increase if the source text has many unique words
#define MAX_LETTER_INSTANCES 1000000

// may need to increase if the source text has many repeated words
#define MAX_BINS 1000000

// assume maximum of 20 letters in a word... adjust accordingly
#define MAX_LETTERS_IN_A_WORD 20

// assume maximum of 10 letters for the string representation of the bin number... adjust accordingly
#define MAX_LETTERS_FOR_BIN_NAME 10

// maximum number of bytes of the output results
#define MAX_OUTPUT_SIZE 10000000

#define false 0
#define true 1
#define null 0
#define SPACE_ASCII_CODE 32

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifdef TIMING
#include <sys/time.h>
#endif

struct Letter
{
    //char isAWord;
    struct Letter* parent;
    struct Letter* binElementNext;
    char asciiCode;
    unsigned int count;
    struct Letter* nextLetters[26];
};
typedef struct Letter Letter;

struct Bin
{
  struct Letter* word;
};
typedef struct Bin Bin;


int main(int argc, char *argv[]) 
{
#ifdef TIMING
    struct timeval tv1, tv2;
    gettimeofday(&tv1, null);
#endif

    int k;
    if (argc !=3 || (k = atoi(argv[2])) <= 0)
    {
        printf("Usage:\n");
        printf("      WordCount <input file path> <number of most frequent words to find>\n\n");
        return -1;
    }

    long  file_size;
    long dataLength;
    char* data;

    // read in file contents
    FILE *fptr;
    size_t read_s = 0;  
    fptr = fopen(argv[1], "rb");
    fseek(fptr, 0L, SEEK_END);
    dataLength = ftell(fptr);
    rewind(fptr);
    data = (char*)malloc((dataLength));
    read_s = fread(data, 1, dataLength, fptr);
    if (fptr) fclose(fptr);

    unsigned int chr;
    unsigned int i, j;

    // working memory of letters
    Letter* letters = (Letter*) malloc(sizeof(Letter) * MAX_LETTER_INSTANCES);
    memset(&letters[0], null, sizeof( Letter) * MAX_LETTER_INSTANCES);

    // the memory for bins
    Bin* bins = (Bin*) malloc(sizeof(Bin) * MAX_BINS);
    memset(&bins[0], null, sizeof( Bin) * MAX_BINS);

    // the index of the next unused letter
    unsigned int letterMasterIndex=0;
    Letter *nextFreeLetter = &letters[0];

    // pesudo letter representing the starting point of any word
    Letter* root = &letters[letterMasterIndex++];

    // the current letter in the word being processed
    Letter* currentLetter = root;

    // the next letter to be processed
    Letter* nextLetter = null;

    unsigned int sortedListSize = 0;

    // the count of the most frequent word
    unsigned int maxCount = 0;

    // the count of the current word
    unsigned int wordCount = 0;

////////////////////////////////////////////////////////////////////////////////////////////
// CREATING PREFIX TREE
    j=dataLength;
    while (--j>0)
    {
        chr = data[j]|0x20; // convert to lower case

        // is a letter?
        if (chr > 96 && chr < 123)
        {
            chr-=97; // translate to be zero indexed
            nextLetter = currentLetter->nextLetters[chr];

            // this is a new letter at this word length, intialise the new letter
            if (nextLetter == null)
            {
                ++letterMasterIndex;
                nextLetter = ++nextFreeLetter;
                nextLetter->parent = currentLetter;
                nextLetter->asciiCode = chr;
                currentLetter->nextLetters[chr] = nextLetter;
            }

            currentLetter = nextLetter;
        }
        else
        {
            //currentLetter->isAWord = true;

            // increment the count of the full word that this letter represents
            ++currentLetter->count;

            // reset the letter path representing the word
            currentLetter = root;
        }
    }

////////////////////////////////////////////////////////////////////////////////////////////
// ADDING TO BINS

    j = letterMasterIndex;
    currentLetter=&letters[j-1];
    while (--j>0)
    {

      // is the letter the leaf letter of word?
      if (currentLetter->count>0)
      {
        i = currentLetter->count;
        if (maxCount < i) maxCount = i;

        // add to bin
        currentLetter->binElementNext = bins[i].word;
        bins[i].word = currentLetter;
      }
      --currentLetter;
    }

////////////////////////////////////////////////////////////////////////////////////////////
// PRINTING OUTPUT

    // the memory for output
    char* output = (char*) malloc(sizeof(char) * MAX_OUTPUT_SIZE);
    memset(&output[0], SPACE_ASCII_CODE, sizeof( char) * MAX_OUTPUT_SIZE);
    unsigned int outputIndex = 0;

    // string representation of the current bin number
    char binName[MAX_LETTERS_FOR_BIN_NAME];
    memset(&binName[0], SPACE_ASCII_CODE, MAX_LETTERS_FOR_BIN_NAME);


    Letter* letter;
    Letter* binElement;

    // starting at the bin representing the most frequent word(s) and then iterating backwards...
    for ( i=maxCount;i>0 && k>0;i--)
    {
      // check to ensure that the bin has at least one word
      if ((binElement = bins[i].word) != null)
      {
        // update the bin name
        sprintf(binName,"%u",i);

        // iterate of the words in the bin
        while (binElement !=null && k>0)
        {
          // stop if we have reached the desired number of outputed words
          if (k-- > 0)
          {
              letter = binElement;

              // add the bin name to the output
              memcpy(&output[outputIndex],&binName[0],MAX_LETTERS_FOR_BIN_NAME);
              outputIndex+=MAX_LETTERS_FOR_BIN_NAME;

              // construct string of letters to form the word
               while (letter != root)
              {
                // output the letter to the output
                output[outputIndex++] = letter->asciiCode+97;
                letter=letter->parent;
              }

              output[outputIndex++] = '\n';

              // go to the next word in the bin
              binElement = binElement->binElementNext;
          }
        }
      }
    }

    // write the output to std out
    fwrite(output, 1, outputIndex, stdout);
   // fflush(stdout);

   // free( data );
   // free( letters );
   // free( bins );
   // free( output );

#ifdef TIMING   
    gettimeofday(&tv2, null);
    printf("\nTime Taken: %f seconds\n", (double) (tv2.tv_usec - tv1.tv_usec)/1000000 + (double) (tv2.tv_sec - tv1.tv_sec));
#endif
    return 0;
}

EDIT: report maintenant le remplissage des bacs jusqu'à la construction de l'arbre et l'optimisation de la construction de la sortie.

EDIT2: utilise désormais l'arithmétique des pointeurs au lieu de l'accès aux tableaux pour optimiser la vitesse.

J

9!:37 ] 0 _ _ _

'input k' =: _2 {. ARGV
k =: ". k

lower =: a. {~ 97 + i. 26
words =: ((lower , ' ') {~ lower i. ]) (32&OR)&.(a.&i.) fread input
words =: ' ' , words
words =: -.&(s: a:) s: words
uniq =: ~. words
res =: (k <. # uniq) {. \:~ (# , {.)/.~ uniq&i. words
echo@(,&": ' ' , [: }.@": {&uniq)/"1 res

exit 0

Exécuter en tant que script avec jconsole <script> <input> <k>. Par exemple, la sortie du giganovelavec k=100K:

$ time jconsole solve.ijs giganovel 100000 | head 
11309 e
11290 ihit
11285 ah
11260 ist
11255 aa
11202 aiv
11201 al
11188 an
11187 o
11186 ansa

real    0m13.765s
user    0m11.872s
sys     0m1.786s

Il n'y a pas de limite, sauf pour la quantité de mémoire système disponible.

C ++ (à la Knuth)

J'étais curieux de savoir comment s'en sortirait le programme de Knuth, alors j'ai traduit son programme (à l'origine Pascal) en C ++.

Même si l'objectif principal de Knuth n'était pas la vitesse, mais pour illustrer son système WEB de programmation alphabétisée, le programme est étonnamment compétitif et conduit à une solution plus rapide que toutes les réponses jusqu'ici. Voici ma traduction de son programme (les numéros de "section" correspondants du programme WEB sont mentionnés dans des commentaires comme " {§24}"):

#include <iostream>
#include <cassert>

// Adjust these parameters based on input size.
const int TRIE_SIZE = 800 * 1000; // Size of the hash table used for the trie.
const int ALPHA = 494441;  // An integer that's approximately (0.61803 * TRIE_SIZE), and relatively prime to T = TRIE_SIZE - 52.
const int kTolerance = TRIE_SIZE / 100;  // How many places to try, to find a new place for a "family" (=bunch of children).

typedef int32_t Pointer;  // [0..TRIE_SIZE), an index into the array of Nodes
typedef int8_t Char;  // We only care about 1..26 (plus two values), but there's no "int5_t".
typedef int32_t Count;  // The number of times a word has been encountered.
// These are 4 separate arrays in Knuth's implementation.
struct Node {
  Pointer link;  // From a parent node to its children's "header", or from a header back to parent.
  Pointer sibling;  // Previous sibling, cyclically. (From smallest child to header, and header to largest child.)
  Count count;  // The number of times this word has been encountered.
  Char ch;  // EMPTY, or 1..26, or HEADER. (For nodes with ch=EMPTY, the link/sibling/count fields mean nothing.)
} node[TRIE_SIZE + 1];
// Special values for `ch`: EMPTY (free, can insert child there) and HEADER (start of family).
const Char EMPTY = 0, HEADER = 27;

const Pointer T = TRIE_SIZE - 52;
Pointer x;  // The `n`th time we need a node, we'll start trying at x_n = (alpha * n) mod T. This holds current `x_n`.
// A header can only be in T (=TRIE_SIZE-52) positions namely [27..TRIE_SIZE-26].
// This transforms a "h" from range [0..T) to the above range namely [27..T+27).
Pointer rerange(Pointer n) {
  n = (n % T) + 27;
  // assert(27 <= n && n <= TRIE_SIZE - 26);
  return n;
}

// Convert trie node to string, by walking up the trie.
std::string word_for(Pointer p) {
  std::string word;
  while (p != 0) {
    Char c = node[p].ch;  // assert(1 <= c && c <= 26);
    word = static_cast<char>('a' - 1 + c) + word;
    // assert(node[p - c].ch == HEADER);
    p = (p - c) ? node[p - c].link : 0;
  }
  return word;
}

// Increment `x`, and declare `h` (the first position to try) and `last_h` (the last position to try). {§24}
#define PREPARE_X_H_LAST_H x = (x + ALPHA) % T; Pointer h = rerange(x); Pointer last_h = rerange(x + kTolerance);
// Increment `h`, being careful to account for `last_h` and wraparound. {§25}
#define INCR_H { if (h == last_h) { std::cerr << "Hit tolerance limit unfortunately" << std::endl; exit(1); } h = (h == TRIE_SIZE - 26) ? 27 : h + 1; }

// `p` has no children. Create `p`s family of children, with only child `c`. {§27}
Pointer create_child(Pointer p, int8_t c) {
  // Find `h` such that there's room for both header and child c.
  PREPARE_X_H_LAST_H;
  while (!(node[h].ch == EMPTY and node[h + c].ch == EMPTY)) INCR_H;
  // Now create the family, with header at h and child at h + c.
  node[h]     = {.link = p, .sibling = h + c, .count = 0, .ch = HEADER};
  node[h + c] = {.link = 0, .sibling = h,     .count = 0, .ch = c};
  node[p].link = h;
  return h + c;
}

// Move `p`'s family of children to a place where child `c` will also fit. {§29}
void move_family_for(const Pointer p, Char c) {
  // Part 1: Find such a place: need room for `c` and also all existing children. {§31}
  PREPARE_X_H_LAST_H;
  while (true) {
    INCR_H;
    if (node[h + c].ch != EMPTY) continue;
    Pointer r = node[p].link;
    int delta = h - r;  // We'd like to move each child by `delta`
    while (node[r + delta].ch == EMPTY and node[r].sibling != node[p].link) {
      r = node[r].sibling;
    }
    if (node[r + delta].ch == EMPTY) break;  // There's now space for everyone.
  }

  // Part 2: Now actually move the whole family to start at the new `h`.
  Pointer r = node[p].link;
  int delta = h - r;
  do {
    Pointer sibling = node[r].sibling;
    // Move node from current position (r) to new position (r + delta), and free up old position (r).
    node[r + delta] = {.ch = node[r].ch, .count = node[r].count, .link = node[r].link, .sibling = node[r].sibling + delta};
    if (node[r].link != 0) node[node[r].link].link = r + delta;
    node[r].ch = EMPTY;
    r = sibling;
  } while (node[r].ch != EMPTY);
}

// Advance `p` to its `c`th child. If necessary, add the child, or even move `p`'s family. {§21}
Pointer find_child(Pointer p, Char c) {
  // assert(1 <= c && c <= 26);
  if (p == 0) return c;  // Special case for first char.
  if (node[p].link == 0) return create_child(p, c);  // If `p` currently has *no* children.
  Pointer q = node[p].link + c;
  if (node[q].ch == c) return q;  // Easiest case: `p` already has a `c`th child.
  // Make sure we have room to insert a `c`th child for `p`, by moving its family if necessary.
  if (node[q].ch != EMPTY) {
    move_family_for(p, c);
    q = node[p].link + c;
  }
  // Insert child `c` into `p`'s family of children (at `q`), with correct siblings. {§28}
  Pointer h = node[p].link;
  while (node[h].sibling > q) h = node[h].sibling;
  node[q] = {.ch = c, .count = 0, .link = 0, .sibling = node[h].sibling};
  node[h].sibling = q;
  return q;
}

// Largest descendant. {§18}
Pointer last_suffix(Pointer p) {
  while (node[p].link != 0) p = node[node[p].link].sibling;
  return p;
}

// The largest count beyond which we'll put all words in the same (last) bucket.
// We do an insertion sort (potentially slow) in last bucket, so increase this if the program takes a long time to walk trie.
const int MAX_BUCKET = 10000;
Pointer sorted[MAX_BUCKET + 1];  // The head of each list.

// Records the count `n` of `p`, by inserting `p` in the list that starts at `sorted[n]`.
// Overwrites the value of node[p].sibling (uses the field to mean its successor in the `sorted` list).
void record_count(Pointer p) {
  // assert(node[p].ch != HEADER);
  // assert(node[p].ch != EMPTY);
  Count f = node[p].count;
  if (f == 0) return;
  if (f < MAX_BUCKET) {
    // Insert at head of list.
    node[p].sibling = sorted[f];
    sorted[f] = p;
  } else {
    Pointer r = sorted[MAX_BUCKET];
    if (node[p].count >= node[r].count) {
      // Insert at head of list
      node[p].sibling = r;
      sorted[MAX_BUCKET] = p;
    } else {
      // Find right place by count. This step can be SLOW if there are too many words with count >= MAX_BUCKET
      while (node[p].count < node[node[r].sibling].count) r = node[r].sibling;
      node[p].sibling = node[r].sibling;
      node[r].sibling = p;
    }
  }
}

// Walk the trie, going over all words in reverse-alphabetical order. {§37}
// Calls "record_count" for each word found.
void walk_trie() {
  // assert(node[0].ch == HEADER);
  Pointer p = node[0].sibling;
  while (p != 0) {
    Pointer q = node[p].sibling;  // Saving this, as `record_count(p)` will overwrite it.
    record_count(p);
    // Move down to last descendant of `q` if any, else up to parent of `q`.
    p = (node[q].ch == HEADER) ? node[q].link : last_suffix(q);
  }
}

int main(int, char** argv) {
  // Program startup
  std::ios::sync_with_stdio(false);

  // Set initial values {§19}
  for (Char i = 1; i <= 26; ++i) node[i] = {.ch = i, .count = 0, .link = 0, .sibling = i - 1};
  node[0] = {.ch = HEADER, .count = 0, .link = 0, .sibling = 26};

  // read in file contents
  FILE *fptr = fopen(argv[1], "rb");
  fseek(fptr, 0L, SEEK_END);
  long dataLength = ftell(fptr);
  rewind(fptr);
  char* data = (char*)malloc(dataLength);
  fread(data, 1, dataLength, fptr);
  if (fptr) fclose(fptr);

  // Loop over file contents: the bulk of the time is spent here.
  Pointer p = 0;
  for (int i = 0; i < dataLength; ++i) {
    Char c = (data[i] | 32) - 'a' + 1;  // 1 to 26, for 'a' to 'z' or 'A' to 'Z'
    if (1 <= c && c <= 26) {
      p = find_child(p, c);
    } else {
      ++node[p].count;
      p = 0;
    }
  }
  node[0].count = 0;

  walk_trie();

  const int max_words_to_print = atoi(argv[2]);
  int num_printed = 0;
  for (Count f = MAX_BUCKET; f >= 0 && num_printed <= max_words_to_print; --f) {
    for (Pointer p = sorted[f]; p != 0 && num_printed < max_words_to_print; p = node[p].sibling) {
      std::cout << word_for(p) << " " << node[p].count << std::endl;
      ++num_printed;
    }
  }

  return 0;
}

Différences par rapport au programme de Knuth:

• I combiné 4 tableaux de Knuth link, sibling, countet chdans un tableau d'unstruct Node (est plus facile de comprendre cette façon).
• J'ai changé la transcription textuelle de programmation littéraire (style WEB) des sections en appels de fonction plus conventionnels (et quelques macros).
• Nous n'avons pas besoin d'utiliser les conventions / restrictions d'E / S étranges standard de Pascal, donc utiliser freadetdata[i] | 32 - 'a' comme dans les autres réponses ici, au lieu de la solution de contournement de Pascal.
• Dans le cas où nous dépassons les limites (à court d'espace) pendant que le programme est en cours d'exécution, le programme original de Knuth le traite avec grâce en supprimant les mots ultérieurs et en imprimant un message à la fin. (Il n'est pas tout à fait juste de dire que McIlroy "a critiqué la solution de Knuth comme ne pouvant même pas traiter un texte intégral de la Bible"; il faisait seulement remarquer que parfois des mots fréquents peuvent se produire très tard dans un texte, comme le mot "Jésus "dans la Bible, donc la condition d'erreur n'est pas inoffensive.) J'ai pris l'approche la plus bruyante (et de toute façon plus facile) de simplement mettre fin au programme.
• Le programme déclare une constante TRIE_SIZE pour contrôler l'utilisation de la mémoire, que j'ai augmentée. (La constante de 32767 avait été choisie pour les exigences d'origine - "un utilisateur devrait être capable de trouver les 100 mots les plus fréquents dans un document technique de vingt pages (environ un fichier de 50 Ko)" et parce que Pascal gère bien les nombres entiers à distance les taper et les emballer de manière optimale. Nous avons dû l'augmenter de 25x à 800 000, car l'entrée de test est maintenant 20 millions de fois plus importante.)
• Pour l'impression finale des chaînes, nous pouvons simplement parcourir le trie et faire un ajout de chaîne stupide (peut-être même quadratique).

En dehors de cela, c'est à peu près exactement le programme de Knuth (en utilisant sa structure de données de tri haché / trié et le tri de seau), et fait à peu près les mêmes opérations (comme le ferait le programme Pascal de Knuth) tout en parcourant tous les caractères en entrée; notez qu'il n'utilise aucun algorithme externe ni bibliothèque de structure de données, et que les mots de même fréquence seront imprimés par ordre alphabétique.

Horaire

Compilé avec

clang++ -std=c++17 -O2 ptrie-walktrie.cc 

Lorsqu'il est exécuté sur le plus grand testcase ici ( giganovelavec 100 000 mots demandés), et comparé au programme le plus rapide publié ici jusqu'à présent, je le trouve légèrement mais toujours plus rapide:

target/release/frequent:   4.809 ±   0.263 [ 4.45.. 5.62]        [... 4.63 ...  4.75 ...  4.88...]
ptrie-walktrie:            4.547 ±   0.164 [ 4.35.. 4.99]        [... 4.42 ...   4.5 ...  4.68...]

(La ligne du haut est la solution Rust d'Anders Kaseorg; la partie inférieure est le programme ci-dessus. Il s'agit des chronométrages de 100 exécutions, avec moyenne, min, max, médiane et quartiles.)

Une analyse

Pourquoi est-ce plus rapide? Ce n'est pas que C ++ est plus rapide que Rust, ni que le programme de Knuth est le plus rapide possible - en fait, le programme de Knuth est plus lent sur les insertions (comme il le mentionne) à cause du tri-pack (pour conserver la mémoire). Je soupçonne que la raison est liée à quelque chose dont Knuth s'est plaint en 2008 :

Une flamme sur les pointeurs 64 bits

Il est absolument idiot d'avoir des pointeurs 64 bits lorsque je compile un programme qui utilise moins de 4 gigaoctets de RAM. Lorsque de telles valeurs de pointeur apparaissent à l'intérieur d'une structure, elles gaspillent non seulement la moitié de la mémoire, mais elles jettent en fait la moitié du cache.

Le programme ci-dessus utilise des index de tableau 32 bits (pas des pointeurs 64 bits), donc la structure "Node" occupe moins de mémoire, donc il y a plus de Nodes sur la pile et moins de ratés de cache. (En fait, il y a eu un peu de travail à ce sujet en tant qu'ABI x32 , mais il ne semble pas être en bon état même si l'idée est évidemment utile, par exemple, voir l' annonce récente de la compression du pointeur dans V8 . Oh bien.) giganovel, ce programme utilise 12,8 Mo pour le trie (compressé), contre 32,18 Mo du programme Rust pour son trie (activé giganovel). Nous pourrions passer à l'échelle 1000x (de "giganovel" à "teranovel" par exemple) et ne pas dépasser les indices 32 bits, cela semble donc un choix raisonnable.

Variante plus rapide

Nous pouvons optimiser la vitesse et renoncer à l'emballage, de sorte que nous pouvons réellement utiliser le trie (non emballé) comme dans la solution Rust, avec des indices au lieu de pointeurs. Cela donne quelque chose de plus rapide et n'a pas de limites prédéfinies sur le nombre de mots, de caractères, etc.:

#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>

typedef int32_t Pointer;  // [0..node.size()), an index into the array of Nodes
typedef int32_t Count;
typedef int8_t Char;  // We'll usually just have 1 to 26.
struct Node {
  Pointer link;  // From a parent node to its children's "header", or from a header back to parent.
  Count count;  // The number of times this word has been encountered. Undefined for header nodes.
};
std::vector<Node> node; // Our "arena" for Node allocation.

std::string word_for(Pointer p) {
  std::vector<char> drow;  // The word backwards
  while (p != 0) {
    Char c = p % 27;
    drow.push_back('a' - 1 + c);
    p = (p - c) ? node[p - c].link : 0;
  }
  return std::string(drow.rbegin(), drow.rend());
}

// `p` has no children. Create `p`s family of children, with only child `c`.
Pointer create_child(Pointer p, Char c) {
  Pointer h = node.size();
  node.resize(node.size() + 27);
  node[h] = {.link = p, .count = -1};
  node[p].link = h;
  return h + c;
}

// Advance `p` to its `c`th child. If necessary, add the child.
Pointer find_child(Pointer p, Char c) {
  assert(1 <= c && c <= 26);
  if (p == 0) return c;  // Special case for first char.
  if (node[p].link == 0) return create_child(p, c);  // Case 1: `p` currently has *no* children.
  return node[p].link + c;  // Case 2 (easiest case): Already have the child c.
}

int main(int, char** argv) {
  auto start_c = std::clock();

  // Program startup
  std::ios::sync_with_stdio(false);

  // read in file contents
  FILE *fptr = fopen(argv[1], "rb");
  fseek(fptr, 0, SEEK_END);
  long dataLength = ftell(fptr);
  rewind(fptr);
  char* data = (char*)malloc(dataLength);
  fread(data, 1, dataLength, fptr);
  fclose(fptr);

  node.reserve(dataLength / 600);  // Heuristic based on test data. OK to be wrong.
  node.push_back({0, 0});
  for (Char i = 1; i <= 26; ++i) node.push_back({0, 0});

  // Loop over file contents: the bulk of the time is spent here.
  Pointer p = 0;
  for (long i = 0; i < dataLength; ++i) {
    Char c = (data[i] | 32) - 'a' + 1;  // 1 to 26, for 'a' to 'z' or 'A' to 'Z'
    if (1 <= c && c <= 26) {
      p = find_child(p, c);
    } else {
      ++node[p].count;
      p = 0;
    }
  }
  ++node[p].count;
  node[0].count = 0;

  // Brute-force: Accumulate all words and their counts, then sort by frequency and print.
  std::vector<std::pair<int, std::string>> counts_words;
  for (Pointer i = 1; i < static_cast<Pointer>(node.size()); ++i) {
    int count = node[i].count;
    if (count == 0 || i % 27 == 0) continue;
    counts_words.push_back({count, word_for(i)});
  }
  auto cmp = [](auto x, auto y) {
    if (x.first != y.first) return x.first > y.first;
    return x.second < y.second;
  };
  std::sort(counts_words.begin(), counts_words.end(), cmp);
  const int max_words_to_print = std::min<int>(counts_words.size(), atoi(argv[2]));
  for (int i = 0; i < max_words_to_print; ++i) {
    auto [count, word] = counts_words[i];
    std::cout << word << " " << count << std::endl;
  }

  return 0;
}

Ce programme, en dépit de faire quelque chose de beaucoup plus stupide pour le tri que les solutions ici, utilise (pour giganovel) seulement 12,2 Mo pour son tri et parvient à être plus rapide. Horaires de ce programme (dernière ligne), par rapport aux horaires précédents mentionnés:

target/release/frequent:   4.809 ±   0.263 [ 4.45.. 5.62]        [... 4.63 ...  4.75 ...  4.88...]
ptrie-walktrie:            4.547 ±   0.164 [ 4.35.. 4.99]        [... 4.42 ...   4.5 ...  4.68...]
itrie-nolimit:             3.907 ±   0.127 [ 3.69.. 4.23]        [... 3.81 ...   3.9 ...   4.0...]

Je serais impatient de voir ce que cela (ou le programme de hachage) voudrait s'il était traduit en rouille . :-)

Plus de détails

1. À propos de la structure de données utilisée ici: une explication des essais de "compactage" est donnée sommairement dans l'exercice 4 de la section 6.3 (Recherche numérique, c'est-à-dire essais) dans le volume 3 de TAOCP, ainsi que dans la thèse de Frank Liang, étudiant de Knuth, sur la césure dans TeX : Word Hy-phen-a-tion par Com-put-er .

2. Le contexte des colonnes de Bentley, du programme de Knuth et de la revue de McIlroy (dont une petite partie seulement concernait la philosophie Unix) est plus clair à la lumière des colonnes précédentes et ultérieures , et de l'expérience antérieure de Knuth, y compris les compilateurs, TAOCP et TeX.

3. Il y a un livre entier Exercices in Programming Style , montrant différentes approches de ce programme particulier, etc.

J'ai un article de blog inachevé expliquant les points ci-dessus; pourrait modifier cette réponse une fois terminée. En attendant, postez cette réponse ici de toute façon, à l'occasion (10 janvier) de l'anniversaire de Knuth. :-)

Python 3

Cette implémentation avec un dictionnaire simple est légèrement plus rapide que celle qui en utilise Counterun sur mon système.

def words_from_file(filename):
    import re

    pattern = re.compile('[a-z]+')

    for line in open(filename):
        yield from pattern.findall(line.lower())


def freq(textfile, k):
    frequencies = {}

    for word in words_from_file(textfile):
        frequencies[word] = frequencies.get(word, 0) + 1

    most_frequent = sorted(frequencies.items(), key=lambda item: item[1], reverse=True)

    for i, (word, frequency) in enumerate(most_frequent):
        if i == k:
            break

        yield word, frequency


from time import time

start = time()
print('\n'.join('{}:\t{}'.format(f, w) for w,f in freq('giganovel', 10)))
end = time()
print(end - start)

[C] Arborescence des préfixes + liste des liens triés

Il prend deux arguments en entrée (chemin vers le fichier texte et pour k nombre de mots les plus fréquents à lister)

Sur la base de mon autre entrée, cette version est beaucoup plus rapide pour les plus grandes valeurs de k mais à un coût de performance mineur à des valeurs de k plus faibles.

Il crée un arbre ramifié sur des lettres de mots, puis au niveau des lettres foliaires, il incrémente un compteur. Vérifie ensuite si le compteur de feuilles actuel est supérieur au plus petit mot le plus fréquent dans la liste des mots les plus fréquents. (la taille de la liste est le nombre déterminé via l'argument de la ligne de commande) Si c'est le cas, promouvez le mot représenté par la lettre feuille comme l'un des plus fréquents. S'il s'agit déjà d'un mot le plus fréquent, remplacez-le par le suivant le plus fréquent si le nombre de mots est désormais plus élevé, ce qui permet de maintenir la liste triée. Tout cela se répète jusqu'à ce qu'aucune autre lettre ne soit lue. Après quoi la liste des mots les plus fréquents est sortie.

Par défaut, il affiche actuellement le temps de traitement, mais à des fins de cohérence avec les autres soumissions, désactivez la définition de TIMING dans le code source.

// comment out TIMING if using external program timing mechanism
#define TIMING 1

// may need to increase if the source text has many unique words
#define MAX_LETTER_INSTANCES 1000000

#define false 0
#define true 1
#define null 0

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifdef TIMING
#include <sys/time.h>
#endif

struct Letter
{
    char isTopWord;
    struct Letter* parent;
    struct Letter* higher;
    struct Letter* lower;
    char asciiCode;
    unsigned int count;
    struct Letter* nextLetters[26];
};
typedef struct Letter Letter;

int main(int argc, char *argv[]) 
{
#ifdef TIMING
    struct timeval tv1, tv2;
    gettimeofday(&tv1, null);
#endif

    int k;
    if (argc !=3 || (k = atoi(argv[2])) <= 0)
    {
        printf("Usage:\n");
        printf("      WordCount <input file path> <number of most frequent words to find>\n\n");
        return -1;
    }

    long  file_size;
    long dataLength;
    char* data;

    // read in file contents
    FILE *fptr;
    size_t read_s = 0;  
    fptr = fopen(argv[1], "rb");
    fseek(fptr, 0L, SEEK_END);
    dataLength = ftell(fptr);
    rewind(fptr);
    data = (char*)malloc((dataLength));
    read_s = fread(data, 1, dataLength, fptr);
    if (fptr) fclose(fptr);

    unsigned int chr;
    unsigned int i;

    // working memory of letters
    Letter* letters = (Letter*) malloc(sizeof(Letter) * MAX_LETTER_INSTANCES);
    memset(&letters[0], 0, sizeof( Letter) * MAX_LETTER_INSTANCES);

    // the index of the next unused letter
    unsigned int letterMasterIndex=0;

    // pesudo letter representing the starting point of any word
    Letter* root = &letters[letterMasterIndex++];

    // the current letter in the word being processed
    Letter* currentLetter = root;

    // the next letter to be processed
    Letter* nextLetter = null;
    Letter* sortedWordsStart = null;
    Letter* sortedWordsEnd = null;
    Letter* A;
    Letter* B;
    Letter* C;
    Letter* D;

    unsigned int sortedListSize = 0;


    unsigned int lowestWordCount = 0;
    unsigned int lowestWordIndex = 0;
    unsigned int highestWordCount = 0;
    unsigned int highestWordIndex = 0;

    // main loop
    for (int j=0;j<dataLength;j++)
    {
        chr = data[j]|0x20; // convert to lower case

        // is a letter?
        if (chr > 96 && chr < 123)
        {
            chr-=97; // translate to be zero indexed
            nextLetter = currentLetter->nextLetters[chr];

            // this is a new letter at this word length, intialise the new letter
            if (nextLetter == null)
            {
                nextLetter = &letters[letterMasterIndex++];
                nextLetter->parent = currentLetter;
                nextLetter->asciiCode = chr;
                currentLetter->nextLetters[chr] = nextLetter;
            }

            currentLetter = nextLetter;
        }
        // not a letter so this means the current letter is the last letter of a word (if any letters)
        else if (currentLetter!=root)
        {

            // increment the count of the full word that this letter represents
            ++currentLetter->count;

            // is this word not in the top word list?
            if (!currentLetter->isTopWord)
            {
                // first word becomes the sorted list
                if (sortedWordsStart == null)
                {
                  sortedWordsStart = currentLetter;
                  sortedWordsEnd = currentLetter;
                  currentLetter->isTopWord = true;
                  ++sortedListSize;
                }
                // always add words until list is at desired size, or 
                // swap the current word with the end of the sorted word list if current word count is larger
                else if (sortedListSize < k || currentLetter->count> sortedWordsEnd->count)
                {
                    // replace sortedWordsEnd entry with current word
                    if (sortedListSize == k)
                    {
                      currentLetter->higher = sortedWordsEnd->higher;
                      currentLetter->higher->lower = currentLetter;
                      sortedWordsEnd->isTopWord = false;
                    }
                    // add current word to the sorted list as the sortedWordsEnd entry
                    else
                    {
                      ++sortedListSize;
                      sortedWordsEnd->lower = currentLetter;
                      currentLetter->higher = sortedWordsEnd;
                    }

                    currentLetter->lower = null;
                    sortedWordsEnd = currentLetter;
                    currentLetter->isTopWord = true;
                }
            }
            // word is in top list
            else
            {
                // check to see whether the current word count is greater than the supposedly next highest word in the list
                // we ignore the word that is sortedWordsStart (i.e. most frequent)
                while (currentLetter != sortedWordsStart && currentLetter->count> currentLetter->higher->count)
                {
                    B = currentLetter->higher;
                    C = currentLetter;
                    A = B != null ? currentLetter->higher->higher : null;
                    D = currentLetter->lower;

                    if (A !=null) A->lower = C;
                    if (D !=null) D->higher = B;
                    B->higher = C;
                    C->higher = A;
                    B->lower = D;
                    C->lower = B;

                    if (B == sortedWordsStart)
                    {
                      sortedWordsStart = C;
                    }

                    if (C == sortedWordsEnd)
                    {
                      sortedWordsEnd = B;
                    }
                }
            }

            // reset the letter path representing the word
            currentLetter = root;
        }
    }

    // print out the top frequent words and counts
    char string[256];
    char tmp[256];

    Letter* letter;
    while (sortedWordsStart != null )
    {
        letter = sortedWordsStart;
        highestWordCount = letter->count;
        string[0]=0;
        tmp[0]=0;

        if (highestWordCount > 0)
        {
            // construct string of letters to form the word
            while (letter != root)
            {
                memmove(&tmp[1],&string[0],255);
                tmp[0]=letter->asciiCode+97;
                memmove(&string[0],&tmp[0],255);
                letter=letter->parent;
            }

            printf("%u %s\n",highestWordCount,string);
        }
        sortedWordsStart = sortedWordsStart->lower;
    }

    free( data );
    free( letters );

#ifdef TIMING   
    gettimeofday(&tv2, null);
    printf("\nTime Taken: %f seconds\n", (double) (tv2.tv_usec - tv1.tv_usec)/1000000 + (double) (tv2.tv_sec - tv1.tv_sec));
#endif
    return 0;
}

C #

Celui-ci devrait fonctionner avec les derniers SDK .net .

using System;
using System.IO;
using System.Diagnostics;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

class Node {
    public Node Parent;
    public Node[] Nodes;
    public int Index;
    public int Count;

    public static readonly List<Node> AllNodes = new List<Node>();

    public Node(Node parent, int index) {
        this.Parent = parent;
        this.Index = index;
        AllNodes.Add(this);
    }

    public Node Traverse(uint u) {
        int b = (int)u;
        if (this.Nodes is null) {
            this.Nodes = new Node[26];
            return this.Nodes[b] = new Node(this, b);
        }
        if (this.Nodes[b] is null) return this.Nodes[b] = new Node(this, b);
        return this.Nodes[b];
    }

    public string GetWord() => this.Index >= 0 
        ? this.Parent.GetWord() + (char)(this.Index + 97)
        : "";
}

class Freq {
    const int DefaultBufferSize = 0x10000;

    public static void Main(string[] args) {
        var sw = Stopwatch.StartNew();

        if (args.Length < 2) {
            WriteLine("Usage: freq.exe {filename} {k} [{buffersize}]");
            return;
        }

        string file = args[0];
        int k = int.Parse(args[1]);
        int bufferSize = args.Length >= 3 ? int.Parse(args[2]) : DefaultBufferSize;

        Node root = new Node(null, -1) { Nodes = new Node[26] }, current = root;
        int b;
        uint u;

        using (var fr = new FileStream(file, FileMode.Open))
        using (var br = new BufferedStream(fr, bufferSize)) {
            outword:
                b = br.ReadByte() | 32;
                if ((u = (uint)(b - 97)) >= 26) {
                    if (b == -1) goto done; 
                    else goto outword;
                }
                else current = root.Traverse(u);
            inword:
                b = br.ReadByte() | 32;
                if ((u = (uint)(b - 97)) >= 26) {
                    if (b == -1) goto done;
                    ++current.Count;
                    goto outword;
                }
                else {
                    current = current.Traverse(u);
                    goto inword;
                }
            done:;
        }

        WriteLine(string.Join("\n", Node.AllNodes
            .OrderByDescending(count => count.Count)
            .Take(k)
            .Select(node => node.GetWord())));

        WriteLine("Self-measured milliseconds: {0}", sw.ElapsedMilliseconds);
    }
}

Voici un exemple de sortie.

C:\dev\freq>csc -o -nologo freq-trie.cs && freq-trie.exe giganovel 100000
e
ihit
ah
ist
 [... omitted for sanity ...]
omaah
aanhele
okaistai
akaanio
Self-measured milliseconds: 13619

Au début, j'ai essayé d'utiliser un dictionnaire avec des clés de chaîne, mais c'était beaucoup trop lent. Je pense que c'est parce que les chaînes .net sont représentées en interne avec un codage à 2 octets, ce qui est un peu inutile pour cette application. Alors, je suis juste passé à des octets purs et à une horrible machine d'état de style goto. La conversion de casse est un opérateur au niveau du bit. La vérification de la plage de caractères se fait en une seule comparaison après soustraction. Je n'ai consacré aucun effort à optimiser le tri final, car j'ai constaté qu'il utilisait moins de 0,1% du temps d'exécution.

Corrigé: L'algorithme était essentiellement correct, mais il surestimait le nombre total de mots, en comptant tous les préfixes de mots. Étant donné que le nombre total de mots n'est pas une exigence du problème, j'ai supprimé cette sortie. Afin d'afficher tous les k mots, j'ai également ajusté la sortie. J'ai finalement décidé d'utiliser string.Join()puis d'écrire la liste entière à la fois. Étonnamment, c'est environ une seconde plus rapide sur ma machine que d'écrire chaque mot séparément pour 100k.

Ruby 2.7.0-preview1 avec tally

La dernière version de Ruby a une nouvelle méthode appelée tally. D'après les notes de version :

Enumerable#tallyest ajouté. Il compte l'occurrence de chaque élément.

["a", "b", "c", "b"].tally
#=> {"a"=>1, "b"=>2, "c"=>1}

Cela résout presque toute la tâche pour nous. Nous avons juste besoin de lire le fichier en premier et de trouver le maximum plus tard.

Voici le tout:

k = ARGV.shift.to_i

pp ARGF
  .each_line
  .lazy
  .flat_map { @1.scan(/[A-Za-z]+/).map(&:downcase) }
  .tally
  .max_by(k, &:last)

edit: ajouté kcomme argument de ligne de commande

Il peut être exécuté avec ruby k filename.rb input.txtla version 2.7.0-preview1 de Ruby. Il peut être téléchargé à partir de divers liens sur la page des notes de publication ou installé avec rbenv à l'aide de rbenv install 2.7.0-dev.

Exemple exécuté sur mon propre vieil ordinateur usé:

$ time ruby bentley.rb 10 ulysses64 
[["the", 968832],
 ["of", 528960],
 ["and", 466432],
 ["a", 421184],
 ["to", 322624],
 ["in", 320512],
 ["he", 270528],
 ["his", 213120],
 ["i", 191808],
 ["s", 182144]]

real    0m17.884s
user    0m17.720s
sys 0m0.142s