Ini mungkin salah satu tantangan pengkodean klasik yang mendapat resonansi pada tahun 1986, ketika kolumnis Jon Bentley meminta Donald Knuth untuk menulis sebuah program yang akan menemukan kata-kata yang paling sering k dalam sebuah file. Knuth mengimplementasikan solusi cepat menggunakan hash mencoba dalam program sepanjang 8 halaman untuk menggambarkan teknik pemrograman melek hurufnya. Douglas McIlroy dari Bell Labs mengkritik solusi Knuth yang bahkan tidak dapat memproses teks lengkap Alkitab, dan menjawab dengan satu kalimat, yang tidak secepat, tetapi menyelesaikan pekerjaan:

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

Pada tahun 1987, artikel lanjutan diterbitkan dengan solusi lain, kali ini oleh seorang profesor Princeton. Tetapi itu juga tidak bisa mengembalikan hasil untuk satu Alkitab!

Deskripsi masalah

Deskripsi masalah asli:

Diberikan file teks dan bilangan bulat k, Anda harus mencetak kata-kata k yang paling umum dalam file (dan jumlah kemunculannya) dalam mengurangi frekuensi.

Klarifikasi masalah tambahan:

• Knuth mendefinisikan kata sebagai serangkaian huruf Latin: [A-Za-z]+
• semua karakter lain diabaikan
• huruf besar dan kecil dianggap setara ( WoRd== word)
• tidak ada batasan ukuran file atau panjang kata
• jarak antara kata-kata berurutan bisa besar secara sewenang-wenang
• program tercepat adalah yang menggunakan total waktu CPU paling sedikit (multithreading mungkin tidak akan membantu)

Contoh uji kasus

Tes 1: Ulysses oleh James Joyce digabung 64 kali (file 96 MB).

• Unduh Ulysses dari Project Gutenberg:wget http://www.gutenberg.org/files/4300/4300-0.txt
• Menggabungkannya 64 kali: for i in {1..64}; do cat 4300-0.txt >> ulysses64; done
• Kata yang paling sering adalah "the" dengan 968832 penampilan.

Tes 2: Teks acak yang dihasilkan khusus giganovel(sekitar 1 GB).

• Skrip generator Python 3 di sini .
• Teks berisi 148391 kata-kata berbeda yang muncul mirip dengan bahasa alami.
• Kata yang paling sering: "e" (11309 penampakan) dan "ihit" (11290 penampakan).

Tes umum: kata-kata besar sembarangan dengan kesenjangan besar sembarang.

Implementasi referensi

Setelah melihat Rosetta Code untuk masalah ini dan menyadari bahwa banyak implementasi yang sangat lambat (lebih lambat dari skrip shell!), Saya menguji beberapa implementasi yang baik di sini . Di bawah ini adalah kinerja untuk ulysses64bersama dengan kompleksitas waktu:

                                     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)

Bisakah kamu mengalahkan itu?

Pengujian

Kinerja akan dievaluasi menggunakan MacBook Pro 2017 13 "dengan Unix standar time perintah (waktu" pengguna "). Jika memungkinkan, silakan gunakan kompiler modern (mis., Gunakan versi Haskell terbaru, bukan versi lawas).

Peringkat sejauh ini

Pengaturan waktu, termasuk program referensi:

                                              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

Peringkat kumulatif * (%, skor terbaik - 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

* Jumlah kinerja waktu relatif terhadap program terbaik di masing-masing dari tiga tes.

Program terbaik sejauh ini: di sini (solusi kedua)

[C]

Berikut ini berjalan di bawah 1,6 detik untuk Uji 1 pada 2,8 Ghz Xeon W3530 saya. Dibangun menggunakan MinGW.org GCC-6.3.0-1 pada Windows 7:

Dibutuhkan dua argumen sebagai input (jalur ke file teks dan untuk k jumlah kata yang paling sering didaftar)

Ini hanya membuat pohon bercabang pada huruf kata-kata, kemudian pada huruf daun itu menambah counter. Kemudian periksa untuk melihat apakah penghitung daun saat ini lebih besar dari kata yang paling sering terkecil dalam daftar kata yang paling sering. (daftar ukuran adalah angka yang ditentukan melalui argumen baris perintah) Jika demikian maka promosikan kata yang diwakili oleh huruf daun menjadi salah satu yang paling sering. Ini semua berulang sampai tidak ada lagi huruf yang dibaca. Setelah itu, daftar kata yang paling sering dihasilkan melalui pencarian berulang yang tidak efisien untuk kata yang paling sering dari daftar kata yang paling sering.

Saat ini default untuk output waktu pemrosesan, tetapi untuk keperluan konsistensi dengan kiriman lainnya, nonaktifkan definisi TIMING dalam kode sumber.

Juga, saya telah mengirimkan ini dari komputer kerja dan belum dapat mengunduh teks Uji 2. Seharusnya berfungsi dengan Tes 2 ini tanpa modifikasi, namun nilai MAX_LETTER_INSTANCES mungkin perlu ditingkatkan.

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

Untuk Uji 1, dan untuk 10 kata paling sering dan dengan pengaturan waktu diaktifkan itu harus dicetak:

 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

Karat

Di komputer saya, ini menjalankan giganovel 100000 sekitar 42% lebih cepat (10,64 detik vs 18,24 detik) daripada solusi C "prefix tree + bins" C Moogie. Juga tidak memiliki batas yang telah ditentukan (tidak seperti solusi C yang menentukan batas pada panjang kata, kata-kata unik, kata-kata yang diulang, dll.).

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

Pemakaian

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

APL (Dyalog Unicode)

Berikut ini berjalan di bawah 8 detik pada 2,6 Ghz i7-4720HQ saya menggunakan 64-bit Dyalog APL 17.0 pada Windows 10:

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

Pertama meminta nama file, lalu untuk k. Perhatikan bahwa sebagian besar waktu berjalan (sekitar 1 detik) hanya membaca file dalam.

Untuk menentukan waktu, Anda harus dapat menyalurkan berikut ini ke dalam dyalogexecutable Anda (untuk sepuluh kata yang paling sering):

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

Itu harus mencetak:

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

[C] Pohon Awalan + Bins

CATATAN: Kompiler yang digunakan memiliki efek signifikan pada kecepatan eksekusi program! Saya telah menggunakan gcc (MinGW.org GCC-8.2.0-3) 8.2.0. Saat menggunakansakelar -Ofast , program ini menjalankan hampir 50% lebih cepat daripada program yang biasanya dikompilasi.

Kompleksitas Algoritma

Sejak itu saya menyadari bahwa penyortiran Bin yang saya lakukan adalah bentuk semacam Pigeonhost. Ini berarti bahwa saya dapat mengurangi kompleksitas Big O dari solusi ini.

Saya menghitungnya menjadi:

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

Kompleksitas konstruksi pohon setara dengan traversal pohon sehingga karena pada tingkat mana pun simpul yang benar untuk dilintasi adalah O (1) (karena setiap huruf dipetakan langsung ke simpul dan kami selalu hanya melintasi satu tingkat pohon untuk setiap huruf)

Penyortiran Pigeon Hole adalah O (N + n) di mana n adalah rentang nilai kunci, namun untuk masalah ini, kita tidak perlu menyortir semua nilai, hanya angka k sehingga yang terburuk adalah O (N + k).

Menggabungkan bersama-sama menghasilkan O (1 + N + k).

Kompleksitas ruang untuk konstruksi pohon disebabkan oleh fakta bahwa kasus terburuk adalah 26 * M node jika data terdiri dari satu kata dengan jumlah huruf M dan bahwa setiap node memiliki 26 node (yaitu untuk huruf-huruf alfabet). Jadi O (26 * M) = O (M)

Untuk Pigeon Hole sorting memiliki kompleksitas ruang O (N + n)

Menggabungkan bersama-sama menghasilkan O (26 * M + N + n) = O (M + N + n)

Algoritma

Dibutuhkan dua argumen sebagai input (jalur ke file teks dan untuk k jumlah kata yang paling sering didaftar)

Berdasarkan entri saya yang lain, versi ini memiliki biaya waktu yang sangat kecil dengan peningkatan nilai k dibandingkan dengan solusi saya yang lain. Tetapi terasa lebih lambat untuk nilai-nilai rendah k tetapi harus jauh lebih cepat untuk nilai-nilai k yang lebih besar.

Itu membuat pohon bercabang pada huruf kata-kata, kemudian pada huruf daun itu menambah counter. Kemudian menambahkan kata ke nampan kata-kata dengan ukuran yang sama (setelah terlebih dahulu menghapus kata dari nampan itu sudah tinggal di). Ini semua diulang sampai tidak ada lagi huruf yang dibaca. Setelah itu tempat sampah dibalik k kali dimulai dari nampan terbesar dan kata-kata dari masing-masing nampan adalah output.

Saat ini default untuk output waktu pemrosesan, tetapi untuk keperluan konsistensi dengan kiriman lainnya, nonaktifkan definisi TIMING dalam kode sumber.

// 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: sekarang menunda nampan-nampan penduduk sampai setelah pohon dibangun dan mengoptimalkan konstruksi output.

EDIT2: sekarang menggunakan aritmatika pointer bukan akses array untuk optimasi kecepatan.

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

Jalankan sebagai skrip dengan jconsole <script> <input> <k>. Misalnya, output dari giganoveldengan 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

Tidak ada batasan kecuali untuk jumlah memori sistem yang tersedia.

C ++ (a la Knuth)

Saya ingin tahu bagaimana program Knuth akan berjalan, jadi saya menerjemahkan programnya (awalnya Pascal) ke dalam C ++.

Meskipun tujuan utama Knuth bukanlah kecepatan tetapi untuk menggambarkan sistem WEB pemrograman terpelajarnya, program ini secara mengejutkan kompetitif, dan mengarah ke solusi yang lebih cepat daripada jawaban di sini sejauh ini. Inilah terjemahan saya dari programnya (nomor "bagian" yang sesuai dari program WEB disebutkan dalam komentar seperti "{§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;
}

Perbedaan dari program Knuth:

• Saya menggabungkan Knuth 4 array link, sibling, countdanch menjadi sebuah array dari struct Node(merasa lebih mudah untuk memahami cara ini).
• Saya mengubah pemrograman teks melek huruf (WEB-style) bagian menjadi panggilan fungsi yang lebih konvensional (dan beberapa makro).
• Kita tidak perlu menggunakan konvensi / pembatasan I / O aneh Pascal standar, jadi gunakan freaddandata[i] | 32 - 'a' seperti pada jawaban lain di sini, alih-alih solusi Pascal.
• Jika kita melampaui batas (kehabisan ruang) saat program sedang berjalan, program asli Knuth menghadapinya dengan anggun dengan menjatuhkan kata-kata kemudian, dan mencetak pesan di bagian akhir. (Tidak tepat mengatakan bahwa McIlroy "mengkritik solusi Knuth karena bahkan tidak dapat memproses teks lengkap dari Alkitab"; ia hanya menunjukkan bahwa kadang-kadang kata-kata yang sering terjadi mungkin muncul sangat terlambat dalam sebuah teks, seperti kata "Yesus" "dalam Alkitab, jadi kondisi kesalahannya tidak berbahaya.) Saya telah mengambil pendekatan yang lebih berisik (dan lebih mudah) dengan hanya menghentikan program.
• Program menyatakan TRIE_SIZE konstan untuk mengontrol penggunaan memori, yang saya temui. (Konstanta 32767 telah dipilih untuk persyaratan asli - "pengguna harus dapat menemukan 100 kata yang paling sering dalam makalah teknis dua puluh halaman (kira-kira file 50K byte)" dan karena Pascal menangani dengan baik dengan bilangan bulat yang berkisar ketik dan bungkus secara optimal. Kami harus meningkatkannya 25x menjadi 800.000 karena input uji sekarang 20 juta kali lebih besar.)
• Untuk pencetakan akhir dari string, kita hanya bisa berjalan di trie dan melakukan menambahkan string bodoh (bahkan mungkin kuadrat).

Terlepas dari itu, ini persis seperti program Knuth (menggunakan hash trie / struktur data trie yang dikemas dan bucket sort), dan melakukan operasi yang hampir sama (seperti yang dilakukan oleh program Pascal Knuth) sambil memutar semua karakter dalam input; perhatikan bahwa tidak menggunakan algoritma eksternal atau struktur data perpustakaan, dan juga kata-kata dengan frekuensi yang sama akan dicetak dalam urutan abjad.

Pengaturan waktu

Disusun dengan

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

Ketika dijalankan di testcase terbesar di sini ( giganoveldengan 100.000 kata yang diminta), dan dibandingkan dengan program tercepat yang diposting di sini sejauh ini, saya merasa sedikit tetapi secara konsisten lebih cepat:

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...]

(Baris teratas adalah solusi Rust Anders Kaseorg; bagian bawah adalah program di atas. Ini adalah timing dari 100 run, dengan mean, min, max, median, dan kuartil.)

Analisis

Mengapa ini lebih cepat? Bukan karena C ++ lebih cepat dari Rust, atau bahwa program Knuth adalah yang tercepat mungkin - pada kenyataannya, program Knuth lebih lambat pada penyisipan (seperti yang dia sebutkan) karena pengepakan trie (untuk menghemat memori). Alasannya, saya curiga, terkait dengan sesuatu yang dikeluhkan Knuth pada 2008 :

A Flame Tentang 64-bit Pointer

Benar-benar bodoh memiliki pointer 64-bit ketika saya mengkompilasi sebuah program yang menggunakan RAM kurang dari 4 gigabytes. Ketika nilai pointer tersebut muncul di dalam sebuah struct, mereka tidak hanya membuang setengah memori, mereka secara efektif membuang setengah dari cache.

Program di atas menggunakan indeks array 32-bit (bukan 64-bit pointer), sehingga struct "Node" menempati lebih sedikit memori, sehingga ada lebih banyak Node pada stack dan lebih sedikit cache misses. (Bahkan, ada beberapa pekerjaan pada ini sebagai x32 ABI , tetapi tampaknya tidak dalam kondisi baik meskipun ide ini jelas berguna, misalnya melihat pengumuman baru dari kompresi pointer di V8 . Oh well.) Jadi pada giganovel, program ini menggunakan 12,8 MB untuk trie (penuh), versus 32,18 MB program Rust untuk trie (aktif giganovel). Kita dapat meningkatkan 1000x (dari "giganovel" ke "teranovel" katakan) dan masih tidak melebihi indeks 32-bit, jadi ini sepertinya pilihan yang masuk akal.

Varian lebih cepat

Kami dapat mengoptimalkan kecepatan dan melepaskan pengepakan, sehingga kami benar-benar dapat menggunakan trie (tidak dikemas) seperti pada solusi Rust, dengan indeks bukan pointer. Ini memberikan sesuatu yang lebih cepat dan tidak memiliki batasan pra-tetap pada jumlah kata, karakter dll:

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

Program ini, walaupun melakukan banyak hal untuk menyortir daripada solusi di sini, hanya menggunakan (untuk giganovel) 12,2MB untuk ketiganya, dan mengelola untuk menjadi lebih cepat. Pengaturan waktu dari program ini (baris terakhir), dibandingkan dengan penentuan waktu sebelumnya yang disebutkan:

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...]

Saya ingin sekali melihat apa yang diinginkan (atau program hash-trie) ini jika diterjemahkan ke dalam Rust . :-)

Keterangan lebih lanjut

1. Tentang struktur data yang digunakan di sini: penjelasan tentang percobaan "pengepakan" diberikan secara ringkas dalam Latihan 4 dari Bagian 6.3 (Pencarian Digital, yaitu percobaan) dalam Volume 3 TAOCP, dan juga dalam tesis siswa Knuth, Frank Liang tentang hyphenation in TeX : Word Hy-phen-a-tion oleh Com-put-er .

2. Konteks kolom Bentley, program Knuth, dan ulasan McIlroy (hanya sebagian kecil tentang filosofi Unix) lebih jelas mengingat kolom sebelumnya dan kemudian , dan pengalaman Knuth sebelumnya termasuk kompiler, TAOCP, dan TeX.

3. Ada seluruh buku Latihan dalam Gaya Pemrograman , yang menunjukkan berbagai pendekatan untuk program khusus ini, dll.

Saya memiliki posting blog yang belum selesai menguraikan poin-poin di atas; mungkin mengedit jawaban ini setelah selesai. Sementara itu, memposting jawaban ini di sini, pada kesempatan (10 Januari) di hari ulang tahun Knuth. :-)

Python 3

Implementasi ini dengan kamus sederhana sedikit lebih cepat daripada yang menggunakan Counterpada sistem saya.

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] Pohon Awalan + Daftar Linked Sorted

Dibutuhkan dua argumen sebagai input (jalur ke file teks dan untuk k jumlah kata yang paling sering didaftar)

Berdasarkan entri saya yang lain, versi ini jauh lebih cepat untuk nilai k yang lebih besar tetapi dengan biaya kinerja yang kecil dengan nilai k yang lebih rendah.

Itu membuat pohon bercabang pada huruf kata-kata, kemudian pada huruf daun itu menambah counter. Kemudian periksa untuk melihat apakah penghitung daun saat ini lebih besar dari kata yang paling sering terkecil dalam daftar kata yang paling sering. (daftar ukuran adalah jumlah yang ditentukan melalui argumen baris perintah) Jika demikian maka promosikan kata yang diwakili oleh huruf daun menjadi salah satu yang paling sering. Jika sudah menjadi kata yang paling sering, maka tukar dengan kata yang paling sering berikutnya jika jumlah kata sekarang lebih tinggi, sehingga daftar tetap diurutkan. Ini semua berulang sampai tidak ada lagi huruf yang dibaca. Setelah itu daftar kata yang paling sering adalah output.

Saat ini default untuk output waktu pemrosesan, tetapi untuk keperluan konsistensi dengan kiriman lainnya, nonaktifkan definisi TIMING dalam kode sumber.

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

Yang ini harus bekerja dengan .net SDK terbaru .

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

Berikut ini contoh keluaran.

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

Pada awalnya, saya mencoba menggunakan kamus dengan tombol string, tapi itu terlalu lambat. Saya pikir itu karena. Net string secara internal diwakili dengan pengkodean 2-byte, yang agak boros untuk aplikasi ini. Jadi kemudian saya hanya beralih ke byte murni, dan mesin negara gaya goto jelek. Konversi kasus adalah operator bitwise. Pemeriksaan rentang karakter dilakukan dalam satu perbandingan setelah pengurangan. Saya tidak menghabiskan usaha mengoptimalkan jenis terakhir karena saya menemukan itu menggunakan kurang dari 0,1% dari runtime.

Perbaiki: Algoritma ini pada dasarnya benar, tetapi itu melaporkan total kata secara berlebihan, dengan menghitung semua awalan kata. Karena jumlah total kata bukan persyaratan masalah, saya menghapus output itu. Untuk mengeluarkan semua kata k, saya juga menyesuaikan hasilnya. Saya akhirnya memutuskan untuk menggunakan string.Join()dan kemudian menulis seluruh daftar sekaligus. Anehnya ini sekitar satu detik lebih cepat di mesin saya yang menulis setiap kata secara terpisah untuk 100rb.

Ruby 2.7.0-preview1 dengan tally

Versi terbaru dari Ruby memiliki metode baru yang disebut tally. Dari catatan rilis :

Enumerable#tallytelah ditambahkan. Ini menghitung terjadinya setiap elemen.

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

Ini hampir menyelesaikan seluruh tugas kami. Kami hanya perlu membaca file terlebih dahulu dan menemukan maks nanti.

Ini semuanya:

k = ARGV.shift.to_i

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

sunting: Ditambahkan ksebagai argumen baris perintah

Itu dapat dijalankan dengan ruby k filename.rb input.txtmenggunakan versi 2.7.0-preview1 Ruby. Ini dapat diunduh dari berbagai tautan pada halaman catatan rilis, atau diinstal dengan rbenv menggunakanrbenv install 2.7.0-dev .

Contoh dijalankan di komputer lama saya yang usang:

$ 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