Räkna ord med ranges och views

Har du också undrat över hur många gånger orden Caesar, Cleopatra och Hamlet förekommer i William Shakespeares samlade verk. Tja, kanske inte... 😏 Men att räkna ordförekomster och presentera resultat på ett trevligt sätt är en ganska bra programmeringsövning. Jag avser här att använda Shakespeares samlade verk som indata. Häng med på en underhållande artikel om modern C++ med ranges och views.

Denna artikel tar vid där min förra artikel slutade och fortsätter med C++20/23 ranges och views, genom att stegvis skriva ett litet program som behandlar en textfil, läser in alla ord och håller reda på hur många gånger respektive ord förekommer och skriver ut en HTML-fil med de 100 mest förekommande orden, där ordstorleken är proportionell mot dess frekvens och där varje ord har en slumpmässigt vald färg. Jag kommer att visa programkoden i delar, men den kompletta källkoden finns i en GitHub repo, du finner i länksamlingen i slutet på artikeln.

I grova drag är programmet strukturerat på följande vis:

1. Öppna infilen och koppla till ett par av WordIterator-objekt. Jag visar koden för WordIterator senare i artikeln.
2. Bygg en första range-pipeline där orden läses, filtreras och normaliseras till gemener, samt ackumuleras i en hash-map.
3. Kopiera över alla {word, count} par till en vector för att sortera dem i fallande frekvensordning.
4. Bygg en andra range-pipeline där ord-frekvens paren görs till HTML span taggar, där ordstorlek sätts proportionellt mot frekvens.
5. Blanda taggarna i slumpmässig ordning, så att slutresultatet ser litet intressantare ut, än stort till smått.
6. Skriv ut resultatet på en HTML-fil

Parametrar

Följande in-parametrar styr programmet

auto filename   = fs::path{"../data/shakespeare.txt"};
auto min_length = 6U;
auto max_words  = 100U;
auto max_font   = 200U;
auto min_font   = 40U;

for (auto k = 1; k < argc; ++k) {
    auto arg = string{argv[k]};
    if (arg == "--file"s) {
        filename = fs::path{argv[++k]};
    } else if (arg == "--min"s) {
        min_length = std::stoul(argv[++k]);
    } else if (arg == "--max"s) {
        max_words = std::stoul(argv[++k]);
    }
}

Valideringen av indata kunde vara bättre, men duger för ett enkelt demo-program som detta.

Typdefinitioner

Följande typ- och import-definitioner används i programmet

namespace r = std::ranges;
namespace v = std::ranges::views;
namespace c = std::chrono;
namespace fs = std::filesystem;
using WordCount = std::pair<std::string, unsigned>;
using namespace std::string_literals;
using std::string;

Containrar

I programmet används följande containrar. Först en hash-map (std::unordered_map), som populeras från inlästa ord. Sedan en std::vector för sortering varpå de N mest frekventa orden sparas i en annan vector. Denna blir start på en pipeline, som omvandlar varje par till en text-sträng i form av en HTML span-tag.

Inläsning

auto freqs = std::unordered_map<string, unsigned>{};
freqs.reserve(10'000);

auto in = std::ifstream{filename}; if (not in) {...}
r::for_each(r::subrange{WordIterator{in}, WordIterator{}}
            | v::filter(drop_small_words)
            | v::transform(to_lower_case)
            | v::filter(drop_modern_words)
            ,
            count_words
);

Vi börjar med att deklarera en hash-map för ord-frekvenser och blåsa upp den lite på måfå för att minska ned antalet interna minnesallokeringar. Infilen öppnas och ett par av WordIterator objekt i en subrange bildar starten på en pipeline. Jag återkommer till min egen-definierade iterator-klass senare. Just nu räcker det med att veta den läser ett ord i taget (sekvens av bokstäver).

En (range-) pipeline inleds vanligtvis med en STL container. Om man inte har detta, men däremot ett par av iteratorer, så kan man skapa ett range-objekt med att instansiera std::ranges::subrange, vilket vi gör här ovan.

Det finns tre steg i denna pipeline, som sedan fungerar som indata för for-each funktionen, där inlästa ord ackumuleras i hash-map:en. Det första steget filtrerar bort korta ord, via följande lambda.

 auto drop_small_words = [min_length](string const& word) -> bool {
    return word.size() >= min_length;
};

Det andra steget normaliserar orden till bara gemener (små bokstäver), via följande lambda.

auto to_lower_case = [](string word) -> string {
    for (char& c: word) { 
        auto ch = static_cast<unsigned char>(c);
        c = static_cast<char>(std::tolower(ch));
    }
    return word;
};

Här skickar vi string-objektet by-value, dvs en kopia, vilket tillåter oss att ändra varje bokstav med std::tolower() och returnera det modifierade ordet. Alternativet hade varit att skicka in ordet som en konstant referens och populera ett lokalt string objekt.

Typomvandlingen mellan signed och unsigned char motiveras med följande kommentar på cppreference.com

Like all other functions from <cctype>, the behavior of std::tolower is undefined if the argument's value is neither representable as unsigned char nor equal to EOF. To use these functions safely with plain chars (or signed chars), the argument should first be converted to unsigned char:
char my_tolower(char ch) {
   return static_cast<char>(std::tolower(static_cast<unsigned char>(ch)));
}

Det tredje steget filtrerar bort några ord som finns i indata-filen och upplyser om att texten finns på gutenberg.org. Vi kan ju vara ganska säkra på att William inte använde ord som "electronic" i hans skådespels-manus. 😏

auto drop_modern_words = [](string const& word) -> bool {
    static auto const modern_words = std::unordered_set{
        "electronic"s, "distributed"s, "copies"s, "copyright"s, "gutenberg"s
    };
    return not modern_words.contains(word);
};

Till slut, sker ackumuleringen i en lambda som utgör for_each funktionens applikations-logik.

auto count_words = [&freqs](string const& word) { ++freqs[word]; };

Uttrycket freqs[word] hittar det std::pair objekt som har word som nyckel (.first) och returnerar referensen till dess värde (.second), vilken då inkrementeras. Finns inte pair-objekt, så skapas det ett nytt, med ordet som nyckel och där värdet initieras med default-konstruktorn (för ett numeriskt värde blir det 0).

Sortering

Vi använder en hash-map för ackumuleringen eftersom den är den snabbaste containern för återkommande uppslag och insättning. Men det går inte att sortera en dylik, så därför behöver vi hälla över alla ord-frekvens par till en container som går att sortera, vilket i vårt fall är en std::vector.

Vi "behöver inte" sortera samtliga par, det räcker med de par vi är intresserade av, vilket är de N mest frekventa orden. Funktionen partial_sort i standard-biblioteket löser detta på ett elegant sätt, genom att peka ut hur många element man vill ha sorterade. Denna funktion har funnits med länge, men här använder jag dess moderna version, som tar en range som input, en iterator som pekar på antalet element, samt en komparator som styr hur elementen ska sorteras.

auto sortable = std::vector<WordCount>(freqs.begin(), freqs.end());

auto by_count_desc = [](auto const& a, auto const& b) { return a.second > b.second; };
r::partial_sort(sortable, sortable.begin() + max_words, by_count_desc);

Ska man vara petig med robust kod, så borde man validera max_words och säkerställa att uttrycket sortable.begin() + max_words inte pekar utanför vektorn. Detta kan man ordna genom att sätta brytpunkten till den minsta av max_words och vektorlängden. Här nedan visar jag uppdaterade kodrader avseende kodfragmentet ovan.

//...
auto N = std::min<std::size_t>(max_words, sortable.size());
//...
r::partial_sort(sortable, sortable.begin() + N, by_count_desc);

HTML-taggar

I programmets sista fas, ska vi omvandla ord-frekvens par till text-strängar med HTML span taggar. Det första vi behöver göra är att spara de par vi är intresserade av, vilket jag gör med en liten pipeline.

auto items = sortable | v::take(max_words) | r::to<std::vector<WordCount>>();

Här bör kanske invändas att man skulle kunna kapa ned sortable med anropet sortable.resize(max_words). Men då missar vi den eleganta pipeline:n ovan. 😎

Själva transformeringen från par till text gör med ytterligare en liknande pipeline.

auto tags = items | v::transform(to_span_tag) | r::to<std::vector<string>>();

Transformations-lambdan ser ut så här.

auto to_span_tag = [scale, min_cnt, min_font, &rnd_color](WordCount const& wc) {
    auto const& word = wc.first;
    auto freq        = wc.second;
    auto size        = static_cast<int>(scale * (freq - min_cnt)) + min_font;
    auto colr        = rnd_color();
    return std::format(
        R"(<span style="font-size: {}px; color: {};" title="The word '{}' occurs {} times" >{}</span>)",
        size, colr, word, freq, word);
};

Jag använder mig av std::format för att returnera en span-tag, eftersom den funktionen gör det enkelt att patcha in text-fragment på olika ställen i en text-mall. Första argumentet är en text-mall i form av en så kallad raw-string (R"(...text goes here...)"), så man slipper skriva back-slash före varje citationstecken, vilka det finns flera av i en typisk HTML tagg.

Ordstorleken (font-size) beräknas genom att frekvensen multipliceras med en skalfaktor, vilken definieras på följande vis.

auto max_cnt = items.front().second;
auto min_cnt = items.back().second;
auto scale   = static_cast<double>(max_font - min_font) / (max_cnt - min_cnt);

Här utgår vi från att indata-filen innehåller flera olika ord, vilket gör att vi hoppar över att kontrollera för eventuell division med noll. Det vill säga de två cnt variablerna har samma värde.

Varje ord färgläggs med en slumpmässigt genererad HTML-color, med hjälp av följande lambda.

auto R = std::default_random_engine{std::random_device{}()};
auto rnd_color = [&R]() {
    auto B = std::uniform_int_distribution<unsigned char>{0, 255};
    return std::format("#{:02X}{:02X}{:02X}", B(R), B(R), B(R));
};

Lambdan genererar tre slumpmässiga byte-värden i intervallet {0,255} och formaterar dessa i hex-format, samt returnerar dem i HTML RGB-color format, som t.ex. #BA3A0A.

Summa summarum; ett indata par som std::pair<"othello", 325> omvandlas till text-strängen

<span style="font-size: 51px; color: #C3326A;" title="The word 'othello' occurs 325 times" >othello</span>

Generering av HTML-fil

Innan vi skriver ut alla HTML taggar, blandar vi om dessa i slumpmässig ordning, så att resultatet ser intressantare ut än att alla ord radas upp från det största till det minsta.

r::shuffle(tags, R);

Först skapar vi filnamnet genom att ta indata-filens namn och byta ut filändelsen mot .html och sen öppnar vi utfilen.

auto outfile = fs::path{filename.stem().string() + ".html"s};
auto out     = std::ofstream{outfile}; if (not out) {...}

Sen skriver vi ut början på en HTML-fil.

out << R"(<!DOCTYPE html>
    <html lang="en">
        <head>
            <meta charset="UTF-8">
            <meta name="viewport" content="width=device-width, initial-scale=1.0, shrink-to-fit=yes">
            <title>Word Frequencies</title>
        </head>
    <body>
    )"
    << std::format("<h1>The {} most frequent words of <code>{}</code></h1>", max_words, filename.string());

Span-taggarna är ju redan klara, så det är enkelt att bara dumpa ut dem härnäst, samt skriva ut HTML avslutningen.

for (auto&& tag: tags) out << tag << "\n";

out << "</body></html>\n";
std::println("written result to '{}'", outfile.string());

Tidsmätning

I början av koden läste jag av klockan och likaså i slutet, för att beräkna förfluten tid.

auto start_time = c::high_resolution_clock::now();
//...program goes here...
auto end_time     = c::high_resolution_clock::now();
auto elapsed_time = c::duration_cast<c::milliseconds>(end_time - start_time);
std::println("Elapsed time was {} ms", elapsed_time.count());

Programutskrift

Kompilerar man och kör programmet kan det se ut så här.

$ g++ -std=c++23 -Wall word-count.cxx -o word-count
$ ./word-count --file data/shakespeare.txt
Loading 5.33 MB from 'data/shakespeare.txt'
written result to 'shakespeare.html'
Elapsed time was 969 ms

HTML-resultatet

Öppnar vi den skapade HTML-filen i en webbläsare kan det se ut så här. Jag har markerat orden caesar (525 förekomster) och cleopatra (263 förekomster). Emellertid, förekommer ordet hamlet inte bland de 100 mest förekommande utan är på en blygsam plats med 117 förekomster (vilket man kan se genom att öka på max_words).

Klassen WordIterator

För att läsa in orden från infilen har jag använt en egen-utvecklad iterator-klass, som returnerar ett ord (sekvens av bokstäver) i taget. Den finns i en separat header-fil för att enkelt kunna återanvändas i något annat projekt.

class WordIterator {
public:
    using iterator_category = std::input_iterator_tag; //...

    explicit WordIterator(std::istream& is);
    WordIterator() = default;

    reference operator*()  const;
    pointer   operator->() const;

    WordIterator& operator++();
    WordIterator  operator++(int);

    friend bool operator==(WordIterator const& a, WordIterator const& b);
    friend bool operator!=(WordIterator const& a, WordIterator const& b);
private:
    // ...
    static bool is_letter(char c);
    void read_next();
};

Den börjar med ett antal standardiserade publika typ-alias, vilka behövs för att andra funktioner ska kunna välja lämplig realisering i compile-time.

    using iterator_category = std::input_iterator_tag;
    using value_type        = std::string;
    using reference         = const std::string&;
    using pointer           = const std::string*;
    using difference_type   = std::ptrdiff_t;

Den har två konstruktorer, där den första knyter till början av en öppen data-ström och den andra representerar filslut (eof).

    explicit WordIterator(std::istream& is) : input{&is} { read_next(); }
    WordIterator() = default;

Detta leder oss till det privata innehållet i ett iterator-objekt.

    std::istream* input{nullptr};
    std::string   current_word{};
    bool          at_eof{true};

Indata-strömmen utgörs av en pekare (och inte referens), eftersom pekaren behöver vara null-ställd för eof-iteratorn, vilket inte skulle kompilera om vi hade haft en referens. Sedan har vi en ackumulator-sträng för aktuellt ord, samt en boolsk flagga för att signallera filslut.

Vidare, så har den en föreskriven uppsättning av operatorer för att kunna iterera över den datamängd den är skapad för.

    // element access
    reference operator*()  const { return current_word; }
    pointer   operator->() const { return &current_word; }

    // increment
    WordIterator& operator++() {
        read_next();
        return *this;
    }
    WordIterator operator++(int) {
        auto tmp = *this;
        ++(*this);
        return tmp;
    }

    // comparison
    friend bool operator==(WordIterator const& a, WordIterator const& b) {
        return a.input == b.input && a.at_eof == b.at_eof;
    }
    friend bool operator!=(WordIterator const& a, WordIterator const& b) {
        return !(a == b);
    }

Själva inläsningen görs av funktionen read_next.

    void read_next() {
        if (input == nullptr) { at_eof = true; return; }

        current_word.clear();
        for (char ch; input->get(ch) && not is_letter(ch);) {}
        if (input->gcount()) input->unget();

        if (current_word.empty() && input->eof()) {
            at_eof = true;
            input = nullptr;
            return;
        }

        for (char ch; input->get(ch) && is_letter(ch);) {
            current_word.push_back(ch);
        }
        at_eof = false;
    }

    static bool is_letter(char c) {
        auto ch = static_cast<unsigned char>(c);
        return std::isalpha(ch) || ch == '\'';
    }

Givet att vi har en inström, så nollställer vi aktuellt ord och skannar förbi alla icke-bokstäver, tills första bokstaven i ett ord. Eftersom vi i det läget har läst en bokstav för mycket, så puttar vi tillbaka denna i strömmen.

Om vi inte har nått slutet, så börjar vi samla på oss bokstäver tills vi har läst en icke-bokstav. Eftersom, vi vet efter detta att det finns minst ett ord kvar så sätter vi filsluts-flaggan till false.

Konverteringen i funktionen is_letter till unsigned char, tarvar en liten utläggning. Så här står det på cppreference.com

Like all other functions from <cctype>, the behavior of std::isalpha is undefined if the argument's value is neither representable as unsigned char nor equal to EOF. To use these functions safely with plain chars (or signed chars), the argument should first be converted to unsigned char.

Alternativ inläsning

Måste man verkligen skriva en egen iterator-klass. Självklart inte. Alternativet här är att förlita sig på ett par av std::istream_iterator<string> objekt, samt strippa bort icke-bokstäver, som första steg i vår inläsnings-pipeline. Så här skulle det kunna se ut.

auto strip_non_letters = [](string const& word) {
    auto result = string{};
    result.reserve(word.size());
    auto is_letter = [](char c) -> bool {
        auto ch = static_cast<unsigned char>(c);
        return std::isalpha(ch) || ch == '\'';
    };
    for (char c: word) if (is_letter(c)) result += c;
    return result;
};

auto in_iter  = std::istream_iterator<string>{in};
auto eof_iter = std::istream_iterator<string>{};
auto read_words_pipeline =
        r::subrange{in_iter, eof_iter}
        | v::transform(strip_non_letters)
        | v::filter(drop_small_words)
        | v::transform(to_lower_case)
        | v::filter(drop_modern_words);
        
r::for_each(read_words_pipeline, count_words);

Kör vi programmet med denna alternativa inläsning, ser det ut så här

Loading 5.33 MB from '../data/shakespeare.txt'
written result to 'shakespeare.html'
Elapsed time was 3794 ms

Som jämförelse, visar jag hur det såg ut med min word-iterator.

Loading 5.33 MB from 'data/shakespeare.txt'
written result to 'shakespeare.html'
Elapsed time was 969 ms

Oj oj oj, nästan fyra gånger så lång exekveringstid. 😮 Här har vi extra string allokeringar i strip_non_letters, samt att std::istream_iterator har en högre intern overhead, jämfört med min egen iterator.

Det lönar sig att tänka på underliggande implementation. Alternativ 2 finns med som kommenterad kod i programkoden på GitHub, så att du kan experimentera själv med koden och prova dig fram.