Function FindEquivalentSubtries

library/cpp/containers/comptrie/minimize.cpp:284–343

    }

    static TOffsetMap FindEquivalentSubtries(const TOpaqueTrie& trie, bool verbose, size_t minMergeSize) {
        // Tree nodes, arranged by span length.
        // When all nodes of a given size are considered, they pop off the queue.
        TPieceIndex subtries;
        TOffsetMap merger;
        // Start walking the trie from head.
        AddPiece(subtries, 0, trie.Length);

        size_t counter = 0;
        // Now consider all nodes with sizeable continuations
        for (size_t curlen = trie.Length; curlen >= minMergeSize && !subtries.empty(); curlen--) {
            TPieceIndex::iterator iit = subtries.find(curlen);

            if (iit == subtries.end())
                continue; // fast forward to the next available length value

            TOffsetList& batch = iit->second;
            TPieceComparer comparer(trie.Data, curlen);
            Sort(batch.begin(), batch.end(), comparer);

            TOffsetList::iterator it = batch.begin();
            while (it != batch.end()) {
                if (verbose)
                    ShowProgress(++counter);

                size_t offset = *it;

                // Fill the array with the subnodes of the element
                TNode node(trie.Data, offset, trie.SkipFunction);
                size_t end = offset + curlen;
                if (size_t rightOffset = node.GetRightOffset()) {
                    AddPiece(subtries, rightOffset, end - rightOffset);
                    end = rightOffset;
                }
                if (size_t leftOffset = node.GetLeftOffset()) {
                    AddPiece(subtries, leftOffset, end - leftOffset);
                    end = leftOffset;
                }
                if (size_t forwardOffset = node.GetForwardOffset()) {
                    AddPiece(subtries, forwardOffset, end - forwardOffset);
                }

                while (++it != batch.end()) {
                    // Find next different; until then, just add the offsets to the list of merged nodes.
                    size_t nextoffset = *it;

                    if (memcmp(trie.Data + offset, trie.Data + nextoffset, curlen))
                        break;

                    merger.Add(nextoffset, offset);
                }
            }

            subtries.erase(curlen);
        }
        if (verbose) {
            Cerr << counter << Endl;
        }