algorithm - 霍夫曼编码算法/数据结构

Question

所以我们的任务是为文本/数字的 .txt 编写压缩算法(可能是通过哈夫曼编码，因为我们的教授非常含糊)

我将所有的线作为 map 中的键，以频率作为它们的值。我对如何从这里开始有点粗略，因为 map 是按键而不是值按顺序组织的 我应该使用不同的数据结构(而不​​是 map )还是每次我想添加到树中时只找到 2 个最小的最小值是否足够容易？下面的代码，任何帮助都会很棒!

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

int main()
{
    vector <string> words;
    map <string, int> store;
    ifstream infile("file.txt");
    string text;
    while (getline(infile, text))
    {
        istringstream iss(text);
        string input;
        if (!(iss >> input))
            break;
        words.push_back(input);
    }
    int freq = 0;


    while (!words.empty())
    {

        string check = words[0];
        if(check == "") //make sure not reading a blank
        {
            words.erase(remove(words.begin(), words.end(), "")); //remove all blanks
            continue; //top of loop
        }
        check = words[0];
        freq = count(words.begin(), words.end(), check);//calculate frequency
        store.insert(pair<string, int>(check, freq)); //store words and frequency in map
        words.erase(remove(words.begin(), words.end(), check)); //erase that      value entirely from the vector
    }

    map<string, int>::iterator i;

    for(i = store.begin(); i != store.end(); ++i)
    {
        cout << "store[" << i ->first << "] = " << i->second << '\n';
    } 
    return 0;
}

Answer 1

要找到 min 值，您可以使用 Priority Queue .

A Priority Queue is a data structure that can give you the min or max value from a set of elements. Finding or inserting in it costs O(log(n)). So in this case, it might be a perfect choice.

C++ has its own built-in Priority Queue.

这是 C++ 中的 priority_queue 的简单示例。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    priority_queue <int> Q;

    Q.push(10);
    Q.push(7);
    Q.push(1);
    Q.push(-3);
    Q.push(4);

    while(!Q.empty()){ // run this loop until the priority_queue gets empty

        int top = Q.top();
        Q.pop();
        cout << top << ' ';

    }
    cout << endl;
    return 0;
}

输出

10, 7, 4, 1, -3

正如您所注意到的，这是按升序排列的。 那是因为:

默认情况下，优先级队列给出最高值。

因此您可以使优先级队列过载，或者一个非常聪明的技巧可以通过反转它们的符号来存储值，并且在您将它们从队列中弹出后，您可以再次反转符号。