Natural language text fast tokenizer (Rev.2)

Question

This is the second iteration of the Natural language text fast tokenizer code review. Special thanks goes to G. Sliepen and Toby Speight who conducted the first review.

Functional specification

Implement a function for fast tokenization of text in char[] buffer handling some natural language specifics below:

1. Consider ‘ ‘ (space) as a delimiter, keeping a way to extends the list of delimiters later.
2. Extract stable collocations like “i.e.”, “etc.”, “…” as a single lexem.
3. In case word contains characters like ‘-‘ and ‘’’ (examples: semi-column, half-, cat’s) return the whole construct as a whole lexem. (3.1) Otherwise, split word and return parts as separate lexems and each non-alphanumeric "inword" symbols as separate lexems.
4. 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.

Note: The defect in specification was found by Matthieu M in question for first code review when I already posted current Rev.2.: any "inword" non-alphanumeric character except described in item 3 above returns as separate lexems which contradicted original functional specification. Since I still in two minds about behaviour I want here, the item 3.1 has been added which describes how it works now. If you change the code and removing 3.1 to keep lexems with internal non-alphanumeric as a whole (like "a|b") will simplify the code, please feel free to fix on the fly. I will fix this in Rev3.

Answers/comments on the items in the first Code Review iteration

1. I am not sure we need tokenize function since we can just use TokenRange(sample); why do we need a wrapper here? Any purpose or risks without it?
2. Thank you for the explanation on the full std::ranges approach. Taking into account that I will need to use the tokenized with the execution policies which are still missing in std::ranges, I will stay with current implementation so far; considering to make view just for learning ranges/views/projections.
3. The question about regex library usage is still on the table. Isn’t regex the tool intended exactly for these purposes? Shouldn’t the code with regex be shorter in times? The only concern is performance, which I mentioned in the first post.
4. I decided not to inherit Iterator to std::iterator because of KISS principle; so far I don’t see any benefits from it. When I see how this could be really used, I will rework this as a separate exercise.

Changelog

1. The code reworked to ranges approach with TokenRange.
2. To avoid offset recalculation for operator++, the mutable next field introduced.
3. Recent C++ features used including switching to std::isdigit and std::isalpha.

Concerns

1. The main issue is this Iterator::end(). In the tutorials they say that the best approach is to transparently pass the end() iterator of underlying data, but since here I can’t return data.end(), the empty range is returned and I am still in two minds if end() is the only case when empty range could occur, so this could lead to false-positive check to end() if I am correct. Please, comment.
2. Mutable next to pass the offset from operator* to operator++ is not the best solution here, but I don’t see anything better. Any suggestions?
3. Still don’t like the code in the inner while loop in the TokenRange::Iterator::operator*. It is hard to grasp and prove to be correct, but don’t see any way to simplify it.
4. Still not sure if class Iterator is the best place for these dilimiters, stable_lexems and inword_lexems; I want them to be configurable later, but still in two minds if they should belong to TokenRange or to Iterator, since formally they don’t define the range, but the way to iterate the range. On the other hand, any hardcoded values is evil, so I should request them in constructor and I don’t want to have them in every iterator’s ctor. Putting them into TokenRange and copy to Iterator on creation to be able to adjust seems as overengineering.

The code

Here is the updated code for the code review; could you please take a look and suggest further ways to improve?

Fully functional demo.

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

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_lexems = "-\'";

        std::string_view data;
        mutable size_t next = ((size_t)-1);
    public:
        Iterator(std::string_view data = {}) : data(data) { skip_delimiters(); }
        std::string_view operator*() const;
        Iterator& operator++();
        friend bool operator==(const Iterator& it1, const Iterator& it2) { return it1.data == it2.data; }
    private:
        void skip_delimiters();
    };

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

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

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

void TokenRange::Iterator::skip_delimiters()
{
    size_t skip = 0;
    while (skip < data.size() && std::ranges::contains(delimiters, data[skip])) {
        ++skip;
    }

    data.remove_prefix(skip);
}

std::string_view TokenRange::Iterator::operator*() const
{
    size_t i = 0;

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

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

        while (i < data.size() && !std::ranges::contains(delimiters, data[i])) {
            const bool is_inword_char = std::ranges::contains(inword_lexems, data[i]);

            if (is_inword_char && i != 0 && std::isalpha(data[i - 1])) {
                ++i;
                continue;
            }

            if (!std::isalpha(data[i]) && !std::isdigit(data[i])) {
                if (i == 0) {
                    ++i;
                }
                break;
            }

            ++i;
        }
    }

    next = i + (data.size() - data.size());
    return data.substr(0,i);
}

TokenRange::Iterator& TokenRange::Iterator::operator++()
{ 
    if (next == ((size_t)-1)) {
        operator*();
    }

    data.remove_prefix(next);
    skip_delimiters();

    next = ((size_t)-1);

    return *this;
}

int main()
{
    std::string sample = "Let's consider, this semi-simple sample, i.e. test data with ints: 100, etc. For ... some testing...";
        
    for (auto token : TokenRange(sample)) {
        std::cout << token << " | ";
    }
}

Performance

I was really surprised with the performance results I got with this new code. Tested on my local PC, the new code is about 18% faster than my original code despite the fact that std::string_view is at least twice larger (pointer and size) than const char*.

I expected the new version to be at least somewhat slower if not dramatically, but it seems that std::ranges library does its work best to provide code which compiler could optimize even better than my original code.

So, at least at this stage no ground for being afraid of expenses.

Being honest, I was used to think that low-level C-style which is closer to assembler language should compile better; the reality is different for our luck.

Here is a demo for those who interested in performance measurements.

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

I've make a partial review below. It's only partial, because it's become clear that the code is a bit too much work in progress. Not only the formatting, but also the correctness. Further, that also makes it pretty hard to follow. In general, it would help if you sometimes described in prose what a section of code does. I believe the size-size issue below was caused by refactoring and changing the meaning of code, too. Having those comments and proof-reading them afterwards helps avoid these issues. That said, despite these flaws, your code is not a mess and generally well-structured.

Formatting Consistency

Sometimes you put the opening { and closing } on the same line with the function header, sometimes only the opening { and sometimes neither. Use one style consistently. Don't cram too much into one line. The compiler won't generate smaller or faster code for it, but it will make the code harder to read and understand.

Cornercase Skipping Space Characters

The function skipping the initial spaces will fail if there is only spaces. I'd rewrite it like this:

while (true) {
    if (input is empty) {
        break;
    }
    if (input[0] is not a delimiter) {
        break;
    }
    input.drop_prefix(1);
}

Putting multiple condition checks into the while condition won't generate smaller or faster code. It does make it less readable which in turn makes it more likely that you miss errors.

Use Of C-Style Casts

I'm referring to ((size_t)-1), which is bad for two reasons. Firstly, it's a magic number. Secondly, it uses C-style casts. Using a named constant (npos for example) would be much more readable.

Mutable Data

You raised the question concerning the mutable next yourself and whether it's necessary. I don't think it is. If you look at what's happening on the input sequence, you find these steps:

1. skip separators
2. find end of token to process it
3. skip to end of token
4. go to step 1

I've ignore the checks for EOF here for now, since it's not important here. The point is that step 2 (operator *) assumes a constant iterator. However, it must store the end of the token for step 3 (operator ++) in order to not repeat the forward scan there.

As alternative, I'd combine skipping separators and scanning for the end of the token. So, in the constructor, you do that once from the initial position and remember both the start and end of the token. operator* then just returns the subsequence you determined there. operator++ then drops the determined token from the head of the sequence and then searches for the next exactly like the constructor.

As additional benefit, multiple or zero calls to operator* will be handled much more gracefully.

Unicode Compliance

Is that even a goal for you? If your input is plain ASCII, quite a few things simplify. For example, all the locale-specific is* can much easier be implemented as ranges::contains() calls.

Skipping Stable Lexems

The code there does (data.size()-data.size()), which makes no sense to me, it's zero. Does this even work correctly?