Dies ist vielleicht eine der klassischen Codierungsherausforderungen, die 1986 Anklang fanden, als der Kolumnist Jon Bentley Donald Knuth aufforderte, ein Programm zu schreiben, das k häufigste Wörter in einer Datei findet. Knuth implementierte eine schnelle Lösung mit Hash-Versuchen in einem 8-seitigen Programm, um seine literarische Programmiertechnik zu veranschaulichen. Douglas McIlroy von Bell Labs kritisierte Knuths Lösung als nicht einmal in der Lage, einen vollständigen Text der Bibel zu verarbeiten, und antwortete mit einem Einzeiler, der nicht so schnell sei, aber die Aufgabe erledige:

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

1987 wurde ein Folgeartikel mit einer weiteren Lösung veröffentlicht, diesmal von einem Princeton-Professor. Aber es konnte nicht einmal ein Ergebnis für eine einzige Bibel liefern!

Problembeschreibung

Ursprüngliche Problembeschreibung:

Bei einer gegebenen Textdatei und einer Ganzzahl k müssen Sie die k häufigsten Wörter in der Datei (und die Anzahl ihrer Vorkommen) in abnehmender Häufigkeit drucken.

Zusätzliche Problemklärungen:

• Knuth definierte ein Wort als eine Folge lateinischer Buchstaben: [A-Za-z]+
• Alle anderen Zeichen werden ignoriert
• Groß- und Kleinbuchstaben werden als gleichwertig angesehen ( WoRd== word)
• Keine Beschränkung der Dateigröße oder der Wortlänge
• Abstände zwischen aufeinanderfolgenden Wörtern können beliebig groß sein
• Das schnellste Programm benötigt am wenigsten CPU-Zeit (Multithreading hilft wahrscheinlich nicht)

Beispiel-Testfälle

Test 1: Ulysses von James Joyce 64-mal verkettet (96 MB-Datei).

• Laden Sie Ulysses vom Projekt Gutenberg herunter :wget http://www.gutenberg.org/files/4300/4300-0.txt
• Verketten Sie es 64 Mal: for i in {1..64}; do cat 4300-0.txt >> ulysses64; done
• Das häufigste Wort ist "der" mit 968832 Erscheinungen.

Test 2: Speziell generierter zufälliger Text giganovel(ca. 1 GB).

• Python 3-Generator-Skript hier .
• Der Text enthält 148391 verschiedene Wörter, die den natürlichen Sprachen ähnlich sind.
• Häufigste Wörter: "e" (11309 Auftritte) und "ihit" (11290 Auftritte).

Allgemeinheitstest: Beliebig große Wörter mit beliebig großen Lücken.

Referenzimplementierungen

Nachdem ich Rosetta Code auf dieses Problem untersucht und festgestellt habe, dass viele Implementierungen unglaublich langsam sind (langsamer als das Shell-Skript!), Habe ich hier einige gute Implementierungen getestet . Nachfolgend finden Sie die Leistung ulysses64zusammen mit der Zeitkomplexität:

                                     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)

Kannst du das schlagen?

Testen

Die Leistung wird mit dem 13 "MacBook Pro 2017 mit dem Standard-Unix- timeBefehl (" Benutzer "-Zeit) bewertet . Wenn möglich, verwenden Sie bitte moderne Compiler (z. B. verwenden Sie die neueste Haskell-Version, nicht die ältere).

Bisherige Platzierungen

Timings, einschließlich der Referenzprogramme:

                                              k=10                  k=100K
                                     ulysses64      giganovel      giganovel
C (trie + bins) by Moogie            0.704          9.568          9.459
C (trie + list) by Moogie            0.767          6.051          82.306
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

Kumulatives Ranking * (%, bestmögliche Punktzahl - 300):

#     Program                         Score  Generality
 1  Rust (trie) by Anders Kaseorg       334     Yes
 2  C (trie + bins) by Moogie           384      x
 3  J by miles                          852     Yes
 4  C# (trie) by recursive             1278      x
 5  C (trie + list) by Moogie          1306      x
 6  C++ (trie + heap)                  2255      x
 7  Python (dict) by movatica          4316     Yes
 8  Python (Counter)                   4583     Yes
 9  Ruby (tally) by daniero            7264     Yes
10  AWK + sort                         9422     Yes
11  McIlroy (tr + sort + uniq)        28014     Yes

* Summe der Zeitleistung im Verhältnis zu den besten Programmen in jedem der drei Tests.

Bestes Programm: hier .

[C]

Das Folgende dauert weniger als 1,6 Sekunden für Test 1 auf meinem 2,8-GHz-Xeon W3530. Mit MinGW.org GCC-6.3.0-1 unter Windows 7 erstellt:

Es werden zwei Argumente als Eingabe verwendet (Pfad zur Textdatei und für k Anzahl der am häufigsten aufzulistenden Wörter)

Es wird einfach ein Baum erstellt, der sich aus Buchstaben von Wörtern verzweigt, und an den Blattbuchstaben wird ein Zähler erhöht. Überprüfen Sie dann, ob der aktuelle Blattzähler größer als das kleinste häufigste Wort in der Liste der häufigsten Wörter ist. (Die Listengröße ist die Zahl, die über das Befehlszeilenargument festgelegt wird.) Wenn ja, stufen Sie das Wort, das durch den Blattbuchstaben dargestellt wird, als eines der häufigsten ein. Dies alles wiederholt sich, bis keine Buchstaben mehr eingelesen werden. Danach wird die Liste der häufigsten Wörter über eine ineffiziente iterative Suche nach dem häufigsten Wort aus der Liste der häufigsten Wörter ausgegeben.

Derzeit wird standardmäßig die Verarbeitungszeit ausgegeben. Deaktivieren Sie jedoch aus Gründen der Konsistenz mit anderen Übermittlungen die TIMING-Definition im Quellcode.

Außerdem habe ich dies von einem Arbeitscomputer übermittelt und konnte Test 2-Text nicht herunterladen. Es sollte mit diesem Test 2 ohne Änderung funktionieren, der MAX_LETTER_INSTANCES-Wert muss jedoch möglicherweise erhöht werden.

// 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;
}

Für Test 1 und für die 10 häufigsten Wörter sollte bei aktiviertem Timing Folgendes gedruckt werden:

 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

APL (Dyalog Unicode)

Das Folgende läuft in weniger als 8 Sekunden auf meinem 2.6 Ghz i7-4720HQ mit 64-Bit Dyalog APL 17.0 unter Windows 10:

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

Zuerst wird nach dem Dateinamen gefragt, dann nach k. Beachten Sie, dass ein erheblicher Teil der Laufzeit (ca. 1 Sekunde) nur das Einlesen der Datei ist.

Um die Zeit zu bestimmen, sollten Sie in der Lage sein, Folgendes in Ihre dyalogausführbare Datei zu leiten (für die zehn häufigsten Wörter):

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

Es sollte drucken:

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

Rost

Auf meinem Computer läuft giganovel 100000 etwa 42% schneller (10,64 s gegenüber 18,24 s) als die C-Lösung von Moogie mit dem Präfix "tree + bins". Außerdem gibt es keine vordefinierten Grenzen (im Gegensatz zur C-Lösung, die Grenzen für die Wortlänge, eindeutige Wörter, wiederholte Wörter usw. festlegt).

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

Verwendung

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

[C] Präfixbaum + Bins

HINWEIS: Der verwendete Compiler hat einen erheblichen Einfluss auf die Programmausführungsgeschwindigkeit! Ich habe gcc (MinGW.org GCC-8.2.0-3) 8.2.0 verwendet. Bei Verwendung der Option -Ofast wird das Programm fast 50% schneller ausgeführt als das normalerweise kompilierte Programm.

Komplexität von Algorithmen

Seitdem ist mir klar geworden, dass die Sortierung der Behälter, die ich durchführe, eine Art von Pigeonhost-Sortierung ist. Dies bedeutet, dass ich die Big O-Komplexität dieser Lösung ableiten kann.

Ich rechne damit:

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

Die Komplexität der Baumkonstruktion entspricht der Baumdurchquerung, da auf jeder Ebene der richtige Knoten, zu dem durchquert werden soll, O (1) ist (da jeder Buchstabe direkt einem Knoten zugeordnet ist und wir für jeden Buchstaben immer nur eine Ebene des Baums durchqueren).

Die Sortierung der Brieftaschen ist O (N + n), wobei n der Bereich der Schlüsselwerte ist. Für dieses Problem müssen jedoch nicht alle Werte sortiert werden, sondern nur die k-Zahl, sodass der schlechteste Fall O (N + k) ist.

Die Kombination ergibt O (1 + N + k).

Die Raumkomplexität für die Baumkonstruktion beruht auf der Tatsache, dass der schlechteste Fall 26 * M Knoten ist, wenn die Daten aus einem Wort mit einer Buchstabenanzahl von M bestehen und jeder Knoten 26 Knoten hat (dh für die Buchstaben des Alphabets). Also ist O (26 * M) = O (M)

Für das Pigeon Hole hat die Sortierung eine Raumkomplexität von O (N + n)

Zusammenfügen ergibt O (26 * M + N + n) = O (M + N + n)

Algorithmus

Es werden zwei Argumente als Eingabe verwendet (Pfad zur Textdatei und für k Anzahl der am häufigsten aufzulistenden Wörter)

Basierend auf meinen anderen Einträgen hat diese Version eine sehr kleine Zeitkostenrampe mit steigenden Werten von k im Vergleich zu meinen anderen Lösungen. Ist aber bei niedrigen Werten von k merklich langsamer, sollte aber bei größeren Werten von k deutlich schneller sein.

Es wird ein Baum erstellt, der sich aus Buchstaben von Wörtern verzweigt, und an den Blattbuchstaben wird ein Zähler erhöht. Fügt das Wort dann zu einer Gruppe von Wörtern derselben Größe hinzu (nachdem das Wort zuerst aus der Gruppe entfernt wurde, in der es sich bereits befunden hat). Dies alles wiederholt sich, bis keine Buchstaben mehr eingelesen werden. Danach werden die Bins k-mal rückwärts iteriert, beginnend mit dem größten Bin, und die Wörter jedes Bins werden ausgegeben.

Derzeit wird standardmäßig die Verarbeitungszeit ausgegeben. Deaktivieren Sie jedoch aus Gründen der Konsistenz mit anderen Übermittlungen die TIMING-Definition im Quellcode.

// 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;
}

BEARBEITEN: Verschiebt jetzt das Auffüllen von Behältern, bis der Baum erstellt wurde, und optimiert die Konstruktion der Ausgabe.

EDIT2: Jetzt wird Zeigerarithmetik anstelle von Arrayzugriff zur Geschwindigkeitsoptimierung verwendet.

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

Als Skript mit ausführen jconsole <script> <input> <k>. Zum Beispiel die Ausgabe von giganovelwith 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

Es gibt keine Begrenzung außer der Menge des verfügbaren Systemspeichers.

Python 3

Diese Implementierung mit einem einfachen Wörterbuch ist etwas schneller als die mit Countereinem auf meinem System.

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] Präfixbaum + Sortierte verknüpfte Liste

Es werden zwei Argumente als Eingabe verwendet (Pfad zur Textdatei und für k Anzahl der am häufigsten aufzulistenden Wörter)

Basierend auf meinem anderen Eintrag ist diese Version für größere Werte von k viel schneller, bei niedrigeren Werten von k jedoch mit geringen Leistungskosten.

Es wird ein Baum erstellt, der sich aus Buchstaben von Wörtern verzweigt, und an den Blattbuchstaben wird ein Zähler erhöht. Überprüfen Sie dann, ob der aktuelle Blattzähler größer als das kleinste häufigste Wort in der Liste der häufigsten Wörter ist. (Die Listengröße ist die Zahl, die über das Befehlszeilenargument festgelegt wird.) Wenn ja, stufen Sie das Wort, das durch den Blattbuchstaben dargestellt wird, als eines der häufigsten ein. Wenn bereits ein häufigstes Wort vorhanden ist, tauschen Sie es mit dem nächsthäufigsten aus, wenn die Wortanzahl jetzt höher ist. Auf diese Weise bleibt die Liste sortiert. Dies alles wiederholt sich, bis keine Buchstaben mehr eingelesen werden. Danach wird die Liste der häufigsten Wörter ausgegeben.

Derzeit wird standardmäßig die Verarbeitungszeit ausgegeben. Deaktivieren Sie jedoch aus Gründen der Konsistenz mit anderen Übermittlungen die TIMING-Definition im Quellcode.

// 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 #

Dieser sollte mit den neuesten .net SDKs funktionieren .

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);
    }
}

Hier ist eine Beispielausgabe.

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

Zuerst habe ich versucht, ein Wörterbuch mit String-Schlüsseln zu verwenden, aber das war viel zu langsam. Ich denke, es liegt daran, dass .net-Zeichenfolgen intern mit einer 2-Byte-Codierung dargestellt werden, was für diese Anwendung eine Verschwendung darstellt. Also habe ich einfach zu reinen Bytes und einer hässlichen goto-artigen Zustandsmaschine gewechselt. Die Konvertierung von Groß- und Kleinschreibung ist ein bitweiser Operator. Die Prüfung des Zeichenbereichs erfolgt in einem einzigen Vergleich nach der Subtraktion. Ich habe mir keine Mühe gegeben, die endgültige Sortierung zu optimieren, da sie weniger als 0,1% der Laufzeit beansprucht.

Fix: Der Algorithmus war im Wesentlichen korrekt, es wurden jedoch zu viele Wörter gemeldet, indem alle Präfixe von Wörtern gezählt wurden. Da die Gesamtwortzahl keine Voraussetzung für das Problem ist, habe ich diese Ausgabe entfernt. Um alle k Wörter auszugeben, habe ich auch die Ausgabe angepasst. Schließlich habe ich mich entschlossen string.Join(), die gesamte Liste auf einmal zu verwenden und dann zu schreiben. Überraschenderweise ist dies auf meinem Computer etwa eine Sekunde schneller, als wenn jedes Wort einzeln für 100 KB geschrieben wird.

Ruby 2.7.0-preview1 mit tally

Die neueste Version von Ruby hat eine neue Methode namens tally. Aus den Release Notes :

Enumerable#tallyhinzugefügt. Es zählt das Vorkommen jedes Elements.

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

Dies löst fast die gesamte Aufgabe für uns. Wir müssen nur zuerst die Datei lesen und später die max finden.

Hier ist das Ganze:

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: Wurde kals Befehlszeilenargument hinzugefügt

Es kann mit ruby k filename.rb input.txtder Version 2.7.0-preview1 von Ruby ausgeführt werden. Dies kann von verschiedenen Links auf der Seite mit den Versionshinweisen heruntergeladen oder mit rbenv installiert werden rbenv install 2.7.0-dev.

Beispiellauf auf meinem eigenen kaputten, alten Computer:

$ 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