path: root/library/cpp/containers/comptrie/minimize.cpp

#include "minimize.h"
#include "node.h"
#include "writeable_node.h"
#include "write_trie_backwards.h"
#include "comptrie_impl.h"

#include <util/generic/hash.h>
#include <util/generic/algorithm.h>

namespace NCompactTrie {
    // Minimize the trie. The result is equivalent to the original
    // trie, except that it takes less space (and has marginally lower
    // performance, because of eventual epsilon links).
    // The algorithm is as follows: starting from the largest pieces, we find
    // nodes that have identical continuations  (Daciuk's right language),
    // and repack the trie. Repacking is done in-place, so memory is less
    // of an issue; however, it may take considerable time.

    // IMPORTANT: never try to reminimize an already minimized trie or a trie with fast layout.
    // Because of non-local structure and epsilon links, it won't work
    // as you expect it to, and can destroy the trie in the making.

    namespace {
        using TOffsetList = TVector<size_t>;
        using TPieceIndex = THashMap<size_t, TOffsetList>;

        using TSizePair = std::pair<size_t, size_t>;
        using TSizePairVector = TVector<TSizePair>;
        using TSizePairVectorVector = TVector<TSizePairVector>;

        class TOffsetMap {
        protected:
            TSizePairVectorVector Data;

        public:
            TOffsetMap() {
                Data.reserve(0x10000);
            }

            void Add(size_t key, size_t value) {
                size_t hikey = key & 0xFFFF;

                if (Data.size() <= hikey)
                    Data.resize(hikey + 1);

                TSizePairVector& sublist = Data[hikey];

                for (auto& it : sublist) {
                    if (it.first == key) {
                        it.second = value;

                        return;
                    }
                }

                sublist.push_back(TSizePair(key, value));
            }

            bool Contains(size_t key) const {
                return (Get(key) != 0);
            }

            size_t Get(size_t key) const {
                size_t hikey = key & 0xFFFF;

                if (Data.size() <= hikey)
                    return 0;

                const TSizePairVector& sublist = Data[hikey];

                for (const auto& it : sublist) {
                    if (it.first == key)
                        return it.second;
                }

                return 0;
            }
        };

        class TOffsetDeltas {
        protected:
            TSizePairVector Data;

        public:
            void Add(size_t key, size_t value) {
                if (Data.empty()) {
                    if (key == value)
                        return; // no offset
                } else {
                    TSizePair last = Data.back();

                    if (key <= last.first) {
                        Cerr << "Trouble: elements to offset delta list added in wrong order" << Endl;

                        return;
                    }

                    if (last.first + value == last.second + key)
                        return; // same  offset
                }

                Data.push_back(TSizePair(key, value));
            }

            size_t Get(size_t key) const {
                if (Data.empty())
                    return key; // difference is zero;

                if (key < Data.front().first)
                    return key;

                // Binary search for the highest entry in the list that does not exceed the key
                size_t from = 0;
                size_t to = Data.size() - 1;

                while (from < to) {
                    size_t midpoint = (from + to + 1) / 2;

                    if (key < Data[midpoint].first)
                        to = midpoint - 1;
                    else
                        from = midpoint;
                }

                TSizePair entry = Data[from];

                return key - entry.first + entry.second;
            }
        };

        class TPieceComparer {
        private:
            const char* Data;
            const size_t Length;

        public:
            TPieceComparer(const char* buf, size_t len)
                : Data(buf)
                , Length(len)
            {
            }

            bool operator()(size_t p1, const size_t p2) {
                int res = memcmp(Data + p1, Data + p2, Length);

                if (res)
                    return (res > 0);

                return (p1 > p2); // the pieces are sorted in the reverse order of appearance
            }
        };

        struct TBranchPoint {
            TNode Node;
            int Selector;

        public:
            TBranchPoint()
                : Selector(0)
            {
            }

            TBranchPoint(const char* data, size_t offset, const ILeafSkipper& skipFunction)
                : Node(data, offset, skipFunction)
                , Selector(0)
            {
            }

            bool IsFinal() const {
                return Node.IsFinal();
            }

            // NextNode returns child nodes, starting from the last node: Right, then Left, then Forward
            size_t NextNode(const TOffsetMap& mergedNodes) {
                while (Selector < 3) {
                    size_t nextOffset = 0;

                    switch (++Selector) {
                        case 1:
                            if (Node.GetRightOffset())
                                nextOffset = Node.GetRightOffset();
                            break;

                        case 2:
                            if (Node.GetLeftOffset())
                                nextOffset = Node.GetLeftOffset();
                            break;

                        case 3:
                            if (Node.GetForwardOffset())
                                nextOffset = Node.GetForwardOffset();
                            break;

                        default:
                            break;
                    }

                    if (nextOffset && !mergedNodes.Contains(nextOffset))
                        return nextOffset;
                }
                return 0;
            }
        };

        class TMergingReverseNodeEnumerator: public TReverseNodeEnumerator {
        private:
            bool Fresh;
            TOpaqueTrie Trie;
            const TOffsetMap& MergeMap;
            TVector<TBranchPoint> Trace;
            TOffsetDeltas OffsetIndex;

        public:
            TMergingReverseNodeEnumerator(const TOpaqueTrie& trie, const TOffsetMap& mergers)
                : Fresh(true)
                , Trie(trie)
                , MergeMap(mergers)
            {
            }

            bool Move() override {
                if (Fresh) {
                    Trace.push_back(TBranchPoint(Trie.Data, 0, Trie.SkipFunction));
                    Fresh = false;
                } else {
                    if (Trace.empty())
                        return false;

                    Trace.pop_back();

                    if (Trace.empty())
                        return false;
                }

                size_t nextnode = Trace.back().NextNode(MergeMap);

                while (nextnode) {
                    Trace.push_back(TBranchPoint(Trie.Data, nextnode, Trie.SkipFunction));
                    nextnode = Trace.back().NextNode(MergeMap);
                }

                return (!Trace.empty());
            }

            const TNode& Get() const {
                return Trace.back().Node;
            }
            size_t GetLeafLength() const override {
                return Get().GetLeafLength();
            }

            // Returns recalculated offset from the end of the current node
            size_t PrepareOffset(size_t absoffset, size_t minilength) {
                if (!absoffset)
                    return NPOS;

                if (MergeMap.Contains(absoffset))
                    absoffset = MergeMap.Get(absoffset);
                return minilength - OffsetIndex.Get(Trie.Length - absoffset);
            }

            size_t RecreateNode(char* buffer, size_t resultLength) override {
                TWriteableNode newNode(Get(), Trie.Data);
                newNode.ForwardOffset = PrepareOffset(Get().GetForwardOffset(), resultLength);
                newNode.LeftOffset = PrepareOffset(Get().GetLeftOffset(), resultLength);
                newNode.RightOffset = PrepareOffset(Get().GetRightOffset(), resultLength);

                if (!buffer)
                    return newNode.Measure();

                const size_t len = newNode.Pack(buffer);
                OffsetIndex.Add(Trie.Length - Get().GetOffset(), resultLength + len);

                return len;
            }
        };

    }

    static void AddPiece(TPieceIndex& index, size_t offset, size_t len) {
        index[len].push_back(offset);
    }

    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;
        }
        return merger;
    }

    size_t RawCompactTrieMinimizeImpl(IOutputStream& os, TOpaqueTrie& trie, bool verbose, size_t minMergeSize, EMinimizeMode mode) {
        if (!trie.Data || !trie.Length) {
            return 0;
        }

        TOffsetMap merger = FindEquivalentSubtries(trie, verbose, minMergeSize);
        TMergingReverseNodeEnumerator enumerator(trie, merger);

        if (mode == MM_DEFAULT)
            return WriteTrieBackwards(os, enumerator, verbose);
        else
            return WriteTrieBackwardsNoAlloc(os, enumerator, trie, mode);
    }

}