2
\$\begingroup\$

This is the third iteration of the Fast search for the longest repeating substrings in large text (Rev.2) code review. Special thanks goes to G. Sliepen who conducted the first two reviews.

Functional specification

Having a large text and already built suffix array find the longest substrings (limited by the number of repetitions) getting benefit from already existing prefix array, if reasonable. Provide the version which would benefit from multithreading keeping the code as simple as possible.

Implementation

The fully functional demo.

Reservation: current implementation utilizes execution policies, so using ranges/projections/views under the question; would work if multi-threading requirement from above met. The further details make sense only as addition to aforementioned second Code Review with answer to it.

Answers to the questions on previous revision code review

  1. On the dilemma “this number or more” or “exactly this number” it is really funny. I tested both on real texts and real environment they give much the same results; the difference is subtle. Main goal was to clean up text base from text duplicates (like the same story in different collections of works, etc.). Even more, the same goes to duplication defect from the first version. With this I mean that all defects, of course, must be fixed and option for different way of search should be provided, but in real environment even “slightly erroneous version” is “good enough”. Just funny side note.
  2. I tested both versions of calculateAdjacents with std::for_each and with std::transform_reduce on real data. You are correct, no significant difference in performance, which is highly reasonable, but since I am aiming to port this to GPU with many cores later, I decided to stay with std::transform_reduce which should give some speed up on GPU, I believe.

Here is the current implementation of calculateAdjacents:

// Returns found sequence(s) length
size_t calculateAdjacents(const Index<>& index,
                          std::vector<index_t>& adjacent_matches,
                          size_t repetitions,
                          bool strong_repetition_count)
{
    std::fill(std::execution::par_unseq, adjacent_matches.begin(), adjacent_matches.end(), 0);

    size_t max_match_length = std::transform_reduce(/*std::execution::par_unseq,*/
        index.begin(), index.end() - (repetitions - 1), size_t(0), 
        [&](size_t max_match_length, size_t match_length) -> size_t {
            return std::max(max_match_length, match_length);
        }, 
        [&](const auto& item) -> size_t {
            const auto& text = index.text;
            size_t idx = &item - std::data(index.index);
            
            size_t match_length = findMatchLengthWithOffsetInSuffixArray(index, idx, (repetitions - 1));

            if (strong_repetition_count) {
                // Not more than min_repetitions times before item
                if (&item > std::data(index.index)) {
                    size_t prev_match_length = findMatchLengthWithOffsetInSuffixArray(index, idx, -1);

                    if (prev_match_length == match_length)
                        return 0;
                }

                // Not more than min_repetitions times after (item+repetitions-1)
                if ((size_t)((&item + repetitions) - std::data(index.index)) < index.size()) {
                    size_t next_match_length = findMatchLengthWithOffsetInSuffixArray(index, idx, repetitions);

                    if (next_match_length == match_length)
                        return 0;
                }
            }

            adjacent_matches[idx] = (index_t)match_length;

            return match_length;
        });

    return max_match_length;
}
  1. On keeping the findMatchLength, this is kind of adherence to Occam's razor principle to avoid unnecessary entities and a kind of rule of thumb like “If you can’t explain in simple words (preferably by function name) what it does generically, out of context of current task, avoid creating it or at least avoid making it visible to client. For this particular function I can’t explain in simple words what it does without this task context.
  2. On the “I would be happy to avoid this `std::fill' at the beginning of calculateAdjacents function, but I am not sure if this is possible.”, I most likely wrongly worded my intention. I mean I want to avoid clearing the vector this way or another. I am not concerned with the way it is done, I am concerned with the algorithm which requires it and I am looking for a way to avoid such performance-consuming operation with high memory-bounding. I will do my best to change the algorithm to avoid this in the subsequent versions. At the same time, I don’t want to move it to calculateAdjacents, because this will cause allocating and releasing this array on each function call. Taking into account that its size equal to text size, on large text bases this could be quite expensive; this is the reason I create the array on a higher level.
  3. In real code I wouldn't use std::string and will use std::vector to keep identifiers (unsigned int) of lexems (actually, even a bit deeper – identifiers of categories or clusters of lexem, but this doesn’t matter at the moment). That’s why in the next revision I will move from std::string to std::vector just to better understand how to manipulate with sequences in absence of std::string and std::string_view functions.

Major changes

  1. Since in real project I will use lexem identifiers instead of plain text, I did some “emulation” in code for this, making pseudo tokenizer which for the sake of simplicity just converts characters’ codes to ints. This is just a trick to go to real types I use and move from std::string and std::string_views. Another step to make algorithm generic, meanwhile.

So, I introduced the:

using lexem_t = unsigned int;
using index_t = unsigned int;
  1. Function parameters text and index replaced with Index template which will be covered below.
  2. “Subtle” defect for the "this number or more" version (“weak count”) mentioned by G. Sliepen has been fixed in the collectRepeatingSubstrings function.
  3. The max_repetitions threshold removed; it is not needed even on large data sets, no significant performance impact or memory footprint on real data.
  4. The collectRepeatingSubstrings function reworked according recommendations. New version is much more readable.

Here it is:

struct SubstringOccurences {
    std::span<const lexem_t> sequence;
    std::vector<index_t> pos;
};

std::vector<SubstringOccurences>
collectRepeatingSubstrings(const Index<>& index,
    std::vector<index_t> adjacent_matches,
    size_t repetitions,
    size_t max_match_length)
{
    std::vector<SubstringOccurences> result;

    size_t j = 1;
    for (size_t i = 0; i < adjacent_matches.size() - 1; i+=j) {
        if (adjacent_matches[i] == max_match_length) {
            result.emplace_back(
                std::span(index.text.begin() + index[i], max_match_length),
                std::vector(&index[i], &index[i + repetitions])
            );
        }

        for (j = 1; i+j < adjacent_matches.size() 
                    && max_match_length == findMatchLengthWithOffsetInSuffixArray(index, i, j); ++j)
            ;
    }

    return result;
}
  1. The findMatchLength function inlined to findMatchLengthWithOffsetInSuffixArray to avoid swamping the namespace.

Here is how it looks like now:

size_t findMatchLengthWithOffsetInSuffixArray(const Index<>& index, 
                                              const size_t idx,
                                              ptrdiff_t offset)
{
    const auto& text = index.text;

    return std::mismatch(text.begin() + index[idx], text.end(), 
                         text.begin() + index[idx + offset], text.end()).first 
                       - (text.begin() + index[idx]);
}
  1. Introduced option strong_repetition_count to control the way the algorithm handles repetitions parameter: “find substring with exact number of repetitions” = “strong count” and “find substring with this number of repetitions or more” = “weak count”.

My concerns on this code

  1. I started with a dozen lines of code and now it grew to 150+ lines of code most of which is still not reusable. I had one function, now I have 2 new types and 4 functions. Well, some defects were fixed which complicated the code a bit, but mostly I paid for functional decomposition. I am still in two minds that the price is reasonable. Anyway, this is still not a final version, so, let’s compare the final result.
  2. While the function findRepeatedSubsequences is a kind of client function, I don’t like that std::cout (or any other stream) is build-in here. Of course, I can return new object RepeatedSubsequences from this function which will collect all the results and overload the operator << for this type in order to be able to output it in any stream in usual manner, but this will additionally complicate the code and will have performance and memory footprint on storing these results.

Here is how the functions looks like now:

void findRepeatedSubsequences(const Index<>& index, size_t max_repetitions, bool strong_repetition_count = true)
{
    std::vector<index_t> adjacent_matches(index.size());

    for (size_t repetitions = 2 ; repetitions <= max_repetitions; ++repetitions) {
        size_t sequence_length = calculateAdjacents(index, adjacent_matches, repetitions, strong_repetition_count);

        if (sequence_length < 1)
            continue;

        std::cout << "Longest equal sequence(s) repeated " << repetitions << " times is " << sequence_length << " chars.\n";

        for (auto sequence : collectRepeatingSubstrings(index, adjacent_matches, repetitions, sequence_length)) {
            std::cout << "The sequence at position(s): (";

            const char* delimiter = "";
            for (auto pos : sequence.pos) {
                std::cout << delimiter << pos;
                delimiter = ",";
            }
            std::cout << "): ";

            std::copy(sequence.sequence.begin(), sequence.sequence.end(), std::ostream_iterator<char>(std::cout));
            
            std::cout << "\n";
        }
        std::cout << "\n";
    }
}

Index class

I had a special homework from G. Sliepen to figure out the name for the structure to wrap up references to text and index.

My way of thinking is following:

  1. I really need only the index and it would be nice if reference to text is stored somehow in it.
  2. It would be nice to have this index type transparent for the client code in order to avoid client code like index.index as much as possible. (I still have it in std::data(index.index), which could easily be replaced with index.begin() in this context, but I eager to learn how to handle this case, as well.

Before these code reviews I raised the question The best place to store index to data where I didn’t get better proposals than my way to wrap up the references to index and indexed text into Index structure:

template <typename LexemType=lexem_t, typename IndexType = index_t>
struct Index {
    const std::vector<LexemType>& text;
    const std::vector<IndexType>& index;
public:
    decltype(index.begin()) begin() const { return index.begin(); }
    decltype(index.end())   end() const { return index.end(); }

    size_t size() const { return index.size(); }
    const IndexType& operator[] (size_t idx) const { return index[idx]; }
};

Some reservations: I made it a structure to avoid excessive accessors. I don’t think they would help much here. Of course, having text and index public makes redundant exposing begin(), end(), size() and operator[]; I made it to simplify client code.

Other code snippets

Since I moved from std::string to std::vector to keep the sequences, I reworked SubstringOccurences to:

struct SubstringOccurences {
    std::span<const lexem_t> sequence;
    std::vector<index_t> pos;
};

I hope, this is the correct way and place to use std::span.

Generalization

One of the questions from G. Sliepen was “Why limit it to strings at all? It seems to me that you could make this work for any kind of range.”.

The only reason I am keeping this not generic is that I want to keep implementation in source files, not in headers in order to maximize insulation (physical encapsulation), reduce compile time and keep visible interfaces free of utility functions.

If there is a way to make them generic without exposing them to header files, it would be nice to know. If not and it goes to header files, there is another question. The findMatchLengthWithOffsetInSuffixArray is not generic, I can’t explain to user what it does without the context of the task, as well as calculateAdjacents and collectRepeatingSubstrings. What is the best way to hide them from client? Create nested utility namespace? Wrap up everything in class which will be able to hold the results and support operator << and will provide encapsulation? Other methods?

Is there any way to improve this code? Any mistakes or issues? Could you please help conducting further steps of code review?

\$\endgroup\$
0

1 Answer 1

2
\$\begingroup\$

Don't use decltype() unnecessarily

In Index you have this member functions:

decltype(index.begin()) begin() const { return index.begin(); }

First of all, you are repeating index.begin() twice. What if the body of your begin() is much more complicated? It quickly becomes very complicated to declare the return type like that. You could just use decltype(auto). However, why do you need decltype() at all here? It would only make sense if you were forwarding the return value of a function whose return type you don't know. But here it is clear: index.begin() returns an iterator by value. It wouldn't ever make sense for it to return a reference. So just write:

auto begin() const { return index.begin(); }

Be consistent

If you are using return type deduction for begin() and end() in Index, why not use the same for size() and operator[]()?

If you make Index a template so you can vary LexemType and IndexType, why isn't SubstringOccurences a template in the same way? And why are calculateAdjacents() and the other functions that take an index as input templates? Either nothing should be a template here, or everything should.

index and text are not private

In struct Index, nothing is private. You added the member functions begin(), end(), size() and operator[]() to avoid other code from directly accessing the member variables. But other code is accessing those member functions directly anyway.

Again, be consistent: either just make it a simple struct that is just holding two vectors without member functions, or make it a class that makes all member variables private and only allows access via member functions.

Clearing adjacent_matches

Inside the call to std::transform_reduce() you only ever write to adjacent_matches. You visit every index from the start to the end minus repetitions - 1. So if you ensure you always write to adjacent_matches[idx] in the transformation function, then the only thing left to do afterwards is to clear the last repetitions - 1 elements.

Remove responsibilities from findRepeatedSubsequences()

While the function findRepeatedSubsequences is a kind of client function, I don’t like that std::cout (or any other stream) is build-in here.

Indeed, that's bad. This function is now responsible both for finding repeated subsequences (as its name implies), and for formatting the result and printing it to std::cout. It should just do the former.

Of course, I can return new object RepeatedSubsequences from this function which will collect all the results

That's not an unreasonable way to do it.

and overload the operator << for this type in order to be able to output it in any stream in usual manner,

No. Again, this unnecessarily complicates RepeatedSubsequences. What if you don't want to output the result to a stream, but do something else with it? Or what if I want to be able to format the output as JSON or XML instead of printing something human readable? You can't just add more and more member functions to that class just to cover all possible uses. It might never end. Just make sure other code can access the results stored in it.

[this] will have performance and memory footprint on storing these results.

That is a valid concern. There are various ways to go about this. First, I would remove the loop from findRepeatedSubsequences(), so it only finds repeated subsequences for one value of repetitions. If you are worried about repeated allocation and initialization of adjacent_matches, you can make it a static variable:

RepeatedSubsequences
findRepeatedSubsequences(const Index<>& index, size_t repetitions,
                         bool strong_repetition_count = true)
{
    static std::vector<index_t> adjacent_matches;
    adjacent_matches.resize(index.size());

    RepeatedSubsequences result;

    result.sequence_length =
        calculateAdjacents(index, adjacent_matches, repetitions,
                           strong_repetition_count);
    result.repeating_substrings =
        collectRepeatingSubstrings(index, adjacent_matches, repetitions,
                                   result.sequence_length));

    return result;
}

Now you can create a printRepeatedSubsequences() function that formats the contents of a RepeatedSubsequences object.

Another option is to keep the outer for-loop in findRepeatedSubsequences(), but pass a callback function to it that will be called for every iteration:

template<typename Callback>
void findRepeatedSubsequences(const Index<>& index, size_t max_repetitions,
                              bool strong_repetition_count = true,
                              Callback callback)
{
    std::vector<index_t> adjacent_matches(index.size());

    for (size_t repetitions = 2 ; repetitions <= max_repetitions; ++repetitions) {
        RepeatedSubsequences result;

        result.sequence_length =
            calculateAdjacents(index, adjacent_matches, repetitions,
                               strong_repetition_count);

        if (sequence_length < 1)
            continue;

        result.repeating_substrings =
            collectRepeatingSubstrings(index, adjacent_matches, repetitions,
                                       sequence_length);

        callback(result);
    }
}

The caller can then pass printRepeatedSubsequences() as the callback function, or whatever else it likes. But I think it is more complicated than necessary in this case.

About the code size

I started with a dozen lines of code and now it grew to 150+ lines of code most of which is still not reusable.

The code from the first revision you posted here was more than two dozen lines of code, even excluding buildPrefixArrayIndex(). Some of the growth comes from nicer formatting of the output, and from fixing some of the bugs you had in the first version.

I had one function, now I have 2 new types and 4 functions. Well, some defects were fixed which complicated the code a bit, but mostly I paid for functional decomposition.

But that's fine. Splitting code into multiple functions usually makes it easier to read, more maintainable and more self-documenting. This is well worth the extra number of lines.

The biggest increase in code size comes from calculateAdjacents(), and in particular to support the strong_repetition_count. I would focus on simplifying this function. Consider:

size_t calculateAdjacents(const Index<>& index,
                          std::vector<index_t>& adjacent_matches,
                          size_t repetitions,
                          bool strong_repetition_count)
{
    return std::transform_reduce(/*std::execution::par_unseq,*/
                                 index.begin(),
                                 index.end() - (repetitions - 1), size_t(0),
                                 std::ranges::max,
                                 [&](const auto& item) -> size_t {
        const auto& text = index.text;
        size_t idx = &item - std::data(index.index);
            
        size_t match_length = findMatchLengthWithOffsetInSuffixArray(index, idx, (repetitions - 1));

        if (strong_repetition_count && !isStrongRepetition(match_length, …))
            match_length = 0;
        }

        return adjacent_matches[idx] = match_length;
    });
}

Sure, I moved the problem to isStrongRepetition(). But now that problem is compartmentalized and calculateAdjacents() looks reasonably simple again.

\$\endgroup\$
5
  • \$\begingroup\$ On the "index and text are not private", didn't my text "Some reservations: I made it a structure to avoid excessive accessors. I don’t think they would help much here. Of course, having text and index public makes redundant exposing begin(), end(), size() and operator[]; I made it to simplify client code." cover my intentions? I wanted to simplify client code. Anyway, I'd love to make them private if I could solve the issue with 'std::data(index)` which requires the container. Can you give advice here? \$\endgroup\$ Jan 28 at 19:32
  • \$\begingroup\$ Sure, why not add a data() member function that returns index.data()? My main issue is that you are not being consistent. If you want to simplify client code by not having to make it access index.index, then just make it so it never has to do that. In your code some operations are simplified, others are not. \$\endgroup\$
    – G. Sliepen
    Jan 28 at 20:27
  • \$\begingroup\$ This works, thanks. I was just used to 'std::data' instead of 'obj.data()' to be able to handle pure C++ arrays if necessary. It seems that in this case this is excessive, since I anyway stuck to Index interface which will handle this. \$\endgroup\$ Jan 28 at 21:02
  • \$\begingroup\$ The main thing about Index structure/class you didn't touch in this round of code review, it was my homework to develop the name for it (and the approach itself). Are you agree with the solution for 'Index` or you had different or better ways to do this? \$\endgroup\$ Jan 28 at 21:03
  • 1
    \$\begingroup\$ Thank you again for your time and help here. I reworked the code according to your recommendations in posted in Fast search for the longest repeating substrings in large text (Rev.4). It seems that we are close to have it done, but I still have some comments, questions and doubts. Could you please revisit the new version? \$\endgroup\$ Jan 31 at 21:59

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.