3
\$\begingroup\$

This is the forth 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 class 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.

Consider out of scope paired quotes and other lexical parsing level issues.

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.

Reservations

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

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 <iostream>
#include <limits>
#include <locale>
#include <numeric>
#include <ranges>
#include <vector>

namespace fast {
    template <typename Fn>
    class IsSomething
    {
        std::array<char, std::numeric_limits<char>::max() + 1> cache = {};

    public:
        explicit IsSomething(Fn fn, const std::locale& locale = {})
        {
            set_locale(fn, locale);
        }

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

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

    IsSomething isalpha(std::isalpha<char>);
    IsSomething isdigit(std::isdigit<char>);

    bool is_not_alphanumeric(char c) {
        return !fast::isalpha(c)
            && !fast::isdigit(c);
    }
}

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();
        void skip_delimiters();
        bool check_for_stable_lexems();
    };

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

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

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

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

bool TokenRange::Iterator::check_for_stable_lexems()
{
    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());
        data = data.substr(it->size());
        return true;
    }
    return false;
}

void TokenRange::Iterator::extract_lexem()
{
    skip_delimiters();

    if (check_for_stable_lexems()) {
        return;
    }

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

        if (fast::is_not_alphanumeric(data[index])) {
            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);
    data = data.substr(index);
}

TokenRange::Iterator& TokenRange::Iterator::operator++()
{
    extract_lexem();
    return *this;
}

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

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

1 Answer 1

4
\$\begingroup\$

It doesn't output the last token

Your own demo shows that it is not printing the last token ....

Missing test suite

You should create a test suite that tests your class TokenRange. It could look like:

int main() {
    struct {
        std::string input;
        std::vector<std::string> expected;
    } samples = {
        {"Hello, world!", {"Hello", ",", "world", "!"}},
        …
    };

    for (auto& sample: samples) {
        assert(std::ranges::equal(TokenRange(sample.input), sample.expected));
    }
}

Make sure you test all the features of your tokenizer, like the stable lexems and in-word lexems, different locales, and corner cases like an empty input, input with only delimiters, and so on.

But the above code also doesn't compile, which brings me to:

It's not a valid std::ranges::input_iterator

While iterating over a TokenRange works, algorithms like std::ranges:equal() don't because you are not fulfilling all of the requirements of std::ranges::input_range. In particular, it is because your TokenRange::Iterator is not a valid std::ranges::input_iterator.

Because of this, your TokenRange will fail to work with many standard algorithms and views. Make sure you fulfill all the requirements. In particular, your iterator needs a post-increment operator and the member type difference_type to be defined.

Some nitpicking

  • IsSomething doesn't sound like a good name. Everything is something, so it's meaningless. A better name would be CharacterClass.
  • Avoid negative names. So instead of is_not_alphanumeric(), prefer is_alphanumeric(), and the caller can then just use ! to invert the meaning.
  • An even better name is isalnum(), to match std::isalnum().
\$\endgroup\$
1
  • \$\begingroup\$ Thank you so much for the new review. I am sure that the comparisons could be done with std::equal based on the existing functionality of the TokenRange / TokenRange::Iterator, but I took the chance to get some practice with 'std::ranges'-style implementations. Please see the Rev.5; defects fixed; tests added. I will be thankful for your input on function extraction comments in Rev.3. \$\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.