在优先级队列中实现比较函数的问题

问题描述 投票：0回答：2

所以我正在构建一个霍夫曼压缩器/解压缩器，但我对符号、频率及其相应代码的打印方式有疑问。我为优先级队列编写了一个 nodecompare 函数，该函数首先比较频率，然后比较符号，作为最后的手段，然后是 nodeID（优先考虑新创建的节点）。虽然我的输出不是预期的，但我似乎无法弄清楚代码中的问题到底出在哪里。请帮助。

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <queue>
using namespace std;

struct Node
{
    char symbol;
    int frequency;
    Node *left;
    Node *right;
    int nodeID;

   Node(char s, int f) : symbol(s), frequency(f), left(nullptr), right(nullptr) {}
};

struct NodeCompare
{
    bool operator()(Node *n1, Node *n2)
    {
        if (n1->frequency == n2->frequency) {
            if (n1->symbol == n2->symbol) {
                return n1->nodeID > n2->nodeID;
            }
            return n1->symbol > n2->symbol;
        }
        else return n1->frequency > n2->frequency;
    }
};

void buildHuffmanTree(priority_queue<Node *, vector<Node *>, NodeCompare> &pq)
{
    static int nodeCounter = 0;

    while (pq.size() > 1)
    {
        Node *left = pq.top();
        pq.pop();
        Node *right = pq.top();
        pq.pop();
        Node *parent = new Node('$', left->frequency + right->frequency);
        parent->nodeID = ++nodeCounter;
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
}

void printCodes(Node *root, string code)
{
    if (root == nullptr)
    {
        return;
    }
    if (root->symbol != '$')
    {
        cout << "Symbol: " << root->symbol << ", Frequency: " << root->frequency << ", Code: " << code << endl;
    }
    printCodes(root->left, code + "0");
    printCodes(root->right, code + "1");
}

int main() {
    string input_file = "input_file.txt";
    //cin >> input_file;

    ifstream infile(input_file);

    vector<Node *> symbols;
    char symbol;
    int frequency;
    priority_queue<Node *, vector<Node *>, NodeCompare> pq;

    string inputline;

    while (getline(infile, inputline)){
        istringstream ss(inputline);
        ss >> std::noskipws >> symbol;
        ss >> std::skipws >> frequency;

        Node *node = new Node(symbol, frequency);
        symbols.push_back(node);
        pq.push(node);
    }

    buildHuffmanTree(pq);
    Node *root = pq.top();
    printCodes(root, "");
}

actual output:
Symbol: 0, Frequency: 2, Code: 000
Symbol: 2, Frequency: 2, Code: 001
Symbol: C, Frequency: 2, Code: 010
Symbol: S, Frequency: 2, Code: 011
Symbol:  , Frequency: 3, Code: 100
Symbol: R, Frequency: 1, Code: 1010
Symbol: 6, Frequency: 1, Code: 10110
Symbol: G, Frequency: 1, Code: 10111
Symbol: 3, Frequency: 3, Code: 110
Symbol: I, Frequency: 1, Code: 11100
Symbol: N, Frequency: 1, Code: 11101
Symbol: O, Frequency: 1, Code: 11110
Symbol: P, Frequency: 1, Code: 11111

expected output:
Symbol: 0, Frequency: 2, Code: 000
Symbol: 2, Frequency: 2, Code: 001
Symbol: I, Frequency: 1, Code: 0100
Symbol: N, Frequency: 1, Code: 0101
Symbol: 6, Frequency: 1, Code: 0110
Symbol: G, Frequency: 1, Code: 0111
Symbol: R, Frequency: 1, Code: 1000
Symbol: O, Frequency: 1, Code: 10010
Symbol: P, Frequency: 1, Code: 10011
Symbol:  , Frequency: 3, Code: 101
Symbol: 3, Frequency: 3, Code: 110
Symbol: C, Frequency: 2, Code: 1110
Symbol: S, Frequency: 2, Code: 1111
c++ huffman-code
2个回答
1
投票

我通常建议使用 

std::tie
创建比较器，但在这种情况下，我将接受两个小的更改。

  • 您需要分别处理父节点，
    $
    符号。非父节点应该在队列中的父节点之后，因为它们具有相同的频率。
  • 你需要交换
    nodeID
    s的优先顺序。
struct NodeCompare {
    bool operator()(const Node *n1, const Node *n2) const {
        if (n1->frequency == n2->frequency) {
            if (n1->symbol == n2->symbol) {
                return n1->nodeID < n2->nodeID;
//                               ^^^ swapped
            }
            if (n1->symbol != '$' && n2->symbol == '$') return true;
// if `n1` is _not_ a parent node but `n2` is, then return true
            return n1->symbol > n2->symbol;
        } else
            return n1->frequency > n2->frequency;
    }
};

演示

一种更简单的方法是使用不同的“父”字符，而不是使用自然按正确顺序排序的字符。那将是具有最小值的字符。

#include <limits>

constexpr char Parent = std::numeric_limits<char>::min(); // -128 probably

然后在您现在使用

Parent
的任何地方使用
'$'
。

有了它，您不需要单独对待父节点，并且可以使用更容易实现的比较器

std::tie
：

#include <tuple>

struct NodeCompare {
    bool operator()(const Node *n1, const Node *n2) const {
        return std::tie(n1->frequency, n1->symbol, n2->nodeID) >
               std::tie(n2->frequency, n2->symbol, n1->nodeID);
               // note that the ordering of `nodeID` still needs to be swapped
    };
};

演示

如果您不喜欢为

nodeID
设置不同的排序规则，而是...

struct NodeCompare {
    bool operator()(const Node *n1, const Node *n2) const {
        return std::tie(n1->frequency, n1->symbol, n1->nodeID) >
               std::tie(n2->frequency, n2->symbol, n2->nodeID);
    };
};

...你只需要使用递减计数器而不是递增计数器：

parent->nodeID = --nodeCounter; // was parent->nodeID = ++nodeCounter;
0
投票

您的实际输出没有问题。实际输出和期望输出都是最优霍夫曼编码。两者都以总共 76 位对所示频率进行编码，这是频率符号乘以代码长度的总和。因为这组频率在决定接下来要组合哪个最低频率时会产生平局（事实上，有很多平局），所以在那些导致不同树和不同代码的步骤中有不同的、同样有效的选择。无论做出什么选择，每次都会生成一个最佳代码，将输入编码为总共 76 位。

对于那组特定的频率，七个 1、四个 2 和两个 3，有太多的关系，根据选择的方式，可以出现 16 种拓扑不同的树。这是所有这些树：

更重要的是，对于这些树中的每一棵，每个分支都可以独立地左边为0，右边为1，或左边为1，右边为0。每个拓扑都有 12 个分支（比符号数少一个），因此每个拓扑的代码有 4096 种可能的 0 和 1 分配。

总的来说，我可以为那组频率生成 65,536 个不同的霍夫曼代码，所有这些代码都是有效的，而且都同样是最优的。你正在展示其中的两个。他们两个都没有什么特别的。

上面显示的最后两棵树有一些特别之处，因为它们的深度（最长代码长度）为四，而所有其他树的深度为五。有些人可能更喜欢最小深度树，您显示的代码都不是。您可以通过组合相同频率的最小深度叶子和/或子树来解决关系以获得最小深度树。 （叶子的深度为零。）

为此，您需要跟踪深度并在频率相等时对其进行排序。为此，我会将 

symbol
设为 
int
而不是 
char
，并将子树的深度存储为 
symbol
中的负数。 IE。 -1 表示深度一，-2 表示深度二，依此类推。 （确保你的符号总是非负的，所以字节必须是 0..255，而不是 -128..127。）然后当频率相等时，更喜欢 
symbol
.

的最大值

在

struct Node
中，有：

    int symbol;

并添加到

struct Node
：

    int depth() {
        return left == nullptr ? 0 : -symbol;
    }

新的

nodeCompare()
是：

struct NodeCompare
{
    bool operator()(Node *n1, Node *n2)
    {
        if (n1->frequency != n2->frequency)
            return n1->frequency > n2->frequency;
        else
            return n1->symbol < n2->symbol;
    }
};

深度在

buildHuffmanTree()
中更新，使用：

        Node *parent = new Node(-(max(left->depth(), right->depth()) + 1),
                                left->frequency + right->frequency);

为了展示树，你不需要

$
业务。只需检查其中一个指针：

    if (root->left == nullptr)
    {
        cout << "Symbol: " << (char)(root->symbol) << ", Frequency: " << root->frequency << ", Code: " << code << endl;
    }

现在它将构建一个最小深度，但仍然是最优的树，在这种情况下是深度四：

符号：0，频率：2，代码：000
符号：O，频率：1，代码：0010
符号：N，频率：1，代码：0011
符号：R，频率：1，代码：0100
符号：P，频率：1，代码：0101
符号：I，频率：1，代码：0110
符号：G，频率：1，代码：0111
符号：3，频率：3，代码：100
符号：，频率：3，代码：101
符号：6，频率：1，代码：1100
符号：S，频率：2，代码：1101
符号：C，频率：2，代码：1110
符号：2，频率：2，代码：1111
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.