Natural language text fast tokenizer (Rev.3)

Question

This is the third iteration of the Natural language text fast tokenizer code review. Special thanks goes to G. Sliepen, Toby Speight and uli who conducted previous reviews and to Matthieu M. and Adrian McCarthy who participated with important findings.

Functional specification

Implement a function for fast text tokenization handling some natural language specifics below:

1. Consider ‘ ‘ (space) as a delimiter, keeping a way to extend the list of delimiters later; the delimiters couldn’t be a part of other constructs.
2. Extract stable collocations like “i.e.”, “etc.”, “…” as a single lexem.
3. In case word contains “inword” characters like ‘-‘ and ‘’’ (examples: semi-column, half-, cat’s) return the whole construct as a whole lexem.
4. Threat all other non-alphanumeric characters as separate lexems.
5. Return sequences of numbers (integers without signs) as a single lexem. Performance is critical, since the amount of data is huge. The function should be thread-safe.

Changes

1. The code has been reworked according to most of code review points.
2. The only exception is brackets { and } formatting consistency; I am still in two minds if my approach somewhere should be replaced with lengthier one.
3. I added the fast::isalpha (12% faster than std::isalpha) (works in assumption of 8-bit encoding) and fast::isdigit (5% faster than std::isdigit, although a little bit risky). Of course, not these percents is a point here, but the dramatic slowdown of these std operations when it comes to work with some specific locale.

Concerns

1. The only place I still don’t like is this calculation of offset in operator++(), but I can’t see the better way:

    if (!lexem.empty()) {
        std::size_t offset = lexem.data() - data.data() + lexem.size();
        data.remove_prefix(offset);
    }

Reservations

1. Methods implementation inside of the class definition done only to the sake of brevity; production code will have them implemented separately.
2. I have no idea why in set_locale when auto const func compiled with Clang with [&locale](unsigned char c) leads to 'std::bad_cast' while with MSVC it works just fine; the only way Clang works is with [&locale](char c), even [&locale](unsigned int c) doesn’t work. So, I have to leave this as is on godbolt.org. If you know the reason, please help me to fix to make this portable.

The code

Here is the updated code for the code review; could you please take a look and suggest further ways to improve or confirm that this is ready to go code?

Fully functional demo.

#include <algorithm>    
#include <cstring>
#include <iostream>
#include <numeric>
#include <ranges>
#include <vector>

namespace fast {
    class IsAlpha
    {
        std::array<unsigned char, std::numeric_limits<unsigned char>::max() + 1> cache = {};

    public:
        explicit IsAlpha(const std::locale& locale = {})
        {
            set_locale(locale);
        }

        void set_locale(const std::locale& locale)
        {
            auto const func = [&locale](unsigned char c) { return std::isalpha(c, locale); };
            std::ranges::copy(std::views::iota(0u, cache.size())
                | std::views::transform(func),
                cache.begin());
        }

        bool operator()(unsigned char c) const { return cache[c]; }
    };

    IsAlpha isalpha;

    bool isdigit(unsigned char c) { return c >= '0' && c <= '9'; }
}

class TokenRange {
    std::string_view data;
public:
    class Iterator {
        const std::string_view delimiters = " ";
        const std::vector<std::string_view> stable_lexems = { "i.e.", "etc.", "..." };
        const std::string_view inword_symbols = "-\'";

        std::string_view data;
        std::string_view lexem;
    public:
        Iterator() {}
        Iterator(std::string_view data) : data(data) { extract_lexem(); }
        std::string_view operator*() const { return lexem; }
        Iterator& operator++();
        friend bool operator==(const Iterator& it1, const Iterator& it2) { return it1.data == it2.data; }
    private:
        void extract_lexem();
    };

    TokenRange(std::string_view data) : data(data) {}

    Iterator begin() {
        return Iterator(data);
    }

    Iterator end() {
        return {};
    }
};

void TokenRange::Iterator::extract_lexem()
{
    while (!data.empty() && std::ranges::contains(delimiters, data.front())) {
        data.remove_prefix(1);
    }

    auto it = std::ranges::find_if(stable_lexems, [&](auto stable_lexem) 
        {
            return data.starts_with(stable_lexem);
        });

    if (it != stable_lexems.end()) {
        lexem = data.substr(0, it->size());
        return;
    }

    std::size_t index = 0;
    while (index < data.size()) 
    {
        if (std::ranges::contains(delimiters, data[index])) {
            break;
        }

        const bool is_not_alphanumeric = !fast::isalpha(static_cast<unsigned char>(data[index])) && !fast::isdigit(static_cast<unsigned char>(data[index]));
        if (is_not_alphanumeric) {
            if (index == 0) {
                ++index;
            }
            break;
        }

        const bool is_next_char_inword_symbol = (index+1) < data.size() ? std::ranges::contains(inword_symbols, data[index+1]) : false;

        if (is_next_char_inword_symbol) {
            ++index;
        }

        ++index;
    }

    lexem = data.substr(0, index);
}

TokenRange::Iterator& TokenRange::Iterator::operator++()
{
    if (!lexem.empty()) {
        std::size_t offset = lexem.data() - data.data() + lexem.size();
        data.remove_prefix(offset);
    }
    extract_lexem();
    return *this;
}

int main()
{
    {
        std::string sample = "Let's consider, this semi-simple sample, i.e. test data with ints: 100 and 0x20u, etc. For ... some testing...";

        for (auto token : TokenRange(sample)) {
            std::cout << token << " | ";
        }
    }
}

Performance

For those who interested in performance evaluations, here is the code with tests.

Please, note that godbolt.org is not suited for performance measurements (at least, as I know it), so the results could differ dramatically. You could just copy the code to your local PC and check.

Answer 1

Answers to your questions

Concerns

1. The only place I still don’t like is this calculation of offset in operator++(), but I can’t see the better way:

I think it's a very minor issue. However, if you want to get rid of it in operator++(), I would make extract_lexem() update data directly. Then the only issue is that data is used in operator==(). But instead of comparing two whole string views there, consider just comparing the lexem.data() pointers to each other:

friend bool operator==(const Iterator& it1, const Iterator& it2) {
    return it1.lexem.data() == it2.lexem.data();
}

Reservations

1. Methods implementation inside of the class definition done only to the sake of brevity; production code will have them implemented separately.

I personally don't mind if short functions are defined inside the class if it's going to be all header-only, but otherwise they should indeed be defined separately in a source file.

2. I have no idea why in set_locale when auto const func compiled with Clang with [&locale](unsigned char c) leads to 'std::bad_cast' […]

See Toby Speight's answer.

Why is fast::isdigit() not locale-aware?

It's really weird to see you set up a cache for a locale-aware isalpha(), but then have a very simple isdigit() that just assumes digits are always like in US-ASCII. Are you really sure that's the case for all possible locales?

Move casting into fast::isalpha()/isdigit()

I would make fast::isalpha() and fast::isidigit() take a regular char as a parameter, and have those functions do the casting to unsigned char. That simplifies the code using it.

Split up extract_lexem()

Consider splitting up some of the code in extract_lexem() into separate functions. For example, the first three lines could be put into a skip_delimiters() function. This helps simplify extract_lexem() and also provides self-documentation.

About in-word lexems

Natural language is messy. I see why you want to be able to parse Let's as one token. But what if they are used as single quotes, like in 'foo' or 'hello world'? A trailing apostrophe is considered to be in-word by your tokenizer. And my examples here are where you don't want to consider that as part of a word, but in English you can have a trailing apostrophe when you have a plural of a possessive noun, like in the parents' children. And other languages might have very different rules.

Answer 2

We're missing includes of <locale> and <limits>. It is not portable to assume any transitive includes of standard library headers except those few specifically prescribed in the C++ standard.

This looks wrong:

 [&locale](unsigned char c) { return std::isalpha(c, locale); };

The std::isalpha() function from <cctype> accepts unsigned char.

But here, we're using the std::isalpha() template function from <locales>. The template is specialised for the character types char and wchar_t. C++ does not require a specialisation for unsigned char, so we need a cast there:

         std::isalpha(static_cast<char>(c), locale);