5
\$\begingroup\$

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.

\$\endgroup\$

2 Answers 2

4
\$\begingroup\$

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.

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

\$\endgroup\$
12
  • \$\begingroup\$ Thank you for the review. Let me address some of topics one by one before I make a revision 4. (1) On the fast::isdigit I wrote above “although a little bit risky”, but I intentionally made this decision, since if I’d implemented in cached way somebody for sure would come with comment “don’t overengineer” and Suzhou numerals won’t persuade them. Anyway, let’s consider this as “example for brevity” here; I totally agree with your point. \$\endgroup\$ Feb 13 at 15:32
  • \$\begingroup\$ (2) I intentionally made casting in extract_lexem code in order to simplify switching between std and fast versions for performance measurement; the production code uses char. (3) On function extraction, I am still in twenty minds here if 3 lines of code worth a new function; I love self-documenting, but having a dozen of extra functions (in a typical, not this situation) in the same “namespace” seems to be a high price for this. I will reword and compare, but I am still not sure here that’s why I inlined skip_delimiters() code into extract_lexem(). \$\endgroup\$ Feb 13 at 15:32
  • \$\begingroup\$ (4) On in-word lexems and paired lexems, it is even worse, since English use quotes for dialogues and this comes to a huge task or pairing and handling pairing errors in texts, as well as intentional unpairing like with . So, this is above this simple parser which works fine with parents’, but, really can’t handle context. Let’s leave this for lexical parsing level if it comes to, keeping this syntactic parser simple. Of course, I agree with you here. \$\endgroup\$ Feb 13 at 15:32
  • \$\begingroup\$ I looked for where C++ guarantees that the basic digits '0'..'9' are consecutive as in C, but failed to find it. \$\endgroup\$ Feb 13 at 15:39
  • 1
    \$\begingroup\$ I am not sure return it1.lexem.data() == it2.lexem.data(); in the operator==() would work, since the main goal of it in our case to compare with iterator returned by end() and it returns default constructed std::string_view which data() is nullptr and when lexem gets empty it returns std::string_view with a very specific address of an empty string '\0'. It wouldn't have worked even if default constructed were initialized by another very specific address. The return it1.data == it2.data; should work, still. \$\endgroup\$ Feb 13 at 18:04
5
\$\begingroup\$

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);
\$\endgroup\$
4
  • \$\begingroup\$ Thank you. I have two points here. (1) I agree on the includes; the question is if there some way (except reading documentation for each and every function) to see which includes are necessary? It works when I add includes, but when I do clean up it is very easy to remove include which is used in some place of a long source file. (2) I see. That's why I missed the whole story about converting types in my previous revisions, I used these functions and char cascaded till that point without any conversions. \$\endgroup\$ Feb 13 at 15:05
  • 1
    \$\begingroup\$ I think the iwyu ("include what you use") tool helps to identify missing and extraneous includes, but I've hardly used it - I mostly just rely on documentation, memory and inspection. \$\endgroup\$ Feb 13 at 15:41
  • \$\begingroup\$ Applied in the Rev.4 by removing all casts to unsigned char, hope I got this right. Thank you again. \$\endgroup\$ Feb 13 at 18:44
  • \$\begingroup\$ Just to be on the same page, now Rev.5 is the actual version. \$\endgroup\$ Feb 14 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.