Как исправить ошибку в алгоритме Хаффмана?

Question

[Илья Трусов]

Здравствуйте. Не могу понять в чем ошибка.

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

int main()
{
	int weight[0x100];
	for (auto &i : weight)
		i = 0;
	{
		ifstream f("ex.txt");
		while (!f.eof())
		{
			unsigned char ch;
			f.read((char *)&ch, sizeof(ch));
			++weight[ch];
		}
	}
	multimap<int, int> sortedWeight;
	struct Node
	{
		char ch;
		int parent;
		int zero;
		int one;
		bool branch;
	};
	vector<Node> tree;
	map<char, int> charMap;
	for (size_t i = 0; i < 0x100; ++i)
	{
		if (weight[i] > 0)
		{
			tree.push_back(Node{ (char)i, -1, -1, -1, false });
			charMap[i] = tree.size() - 1;
			sortedWeight.insert(make_pair(weight[i], tree.size() - 1));
		}
	}
	while (sortedWeight.size() > 1)
	{
		int w0 = begin(sortedWeight)->first;
		int n0 = begin(sortedWeight)->second;
		sortedWeight.erase(begin(sortedWeight));
		int w1 = begin(sortedWeight)->first;
		int n1 = begin(sortedWeight)->second;
		sortedWeight.erase(begin(sortedWeight));
		tree.push_back(Node{ '\0', -1, n0, n1, false });
		tree[n0].parent = tree.size() - 1;
		tree[n0].branch = false;
		tree[n1].parent = tree.size() - 1;
		tree[n1].branch = true;
		sortedWeight.insert(make_pair(w0 + w1, tree.size() - 1));
	}
	vector<bool> data;
	{
		ifstream f("ex.txt");
		while (!f.eof())
		{
			unsigned char ch;
			f.read((char *)&ch, sizeof(ch));
			auto n = tree[charMap[ch]];
			vector<bool> compressedChar;
			while (n.parent != -1)
			{
				compressedChar.push_back(n.branch);
				n = tree[n.parent];
			}
			data.insert(end(data), compressedChar.rbegin(), compressedChar.rend());
		}
	}
	ofstream f("ex.huff");
	int treeSize = tree.size();
	f.write((char *)&treeSize, sizeof(treeSize));
	for (auto i : tree)
		f.write((char *)&i, sizeof(i));
	for (size_t i = 0; i <= data.size() / 8; ++i)
	{
		unsigned char ch = 0;
		for (int j = 0; j < 8; ++j)
			if (data[i * 8 + j])
				ch |= (1 << j);
		f.write((char *)&ch, sizeof(ch));
	}
}

Лог вывода:

"Huffman.exe" (Win32). Загружено "C:\Users\Илья\Documents\Visual Studio 2015\Projects\Huffman\Debug\Huffman.exe". Символы загружены.
"Huffman.exe" (Win32). Загружено "C:\Windows\SysWOW64\ntdll.dll". Невозможно найти или открыть PDB-файл.
"Huffman.exe" (Win32). Загружено "C:\Windows\SysWOW64\kernel32.dll". Невозможно найти или открыть PDB-файл.
"Huffman.exe" (Win32). Загружено "C:\Windows\SysWOW64\KernelBase.dll". Невозможно найти или открыть PDB-файл.
"Huffman.exe" (Win32). Загружено "C:\Windows\SysWOW64\msvcp140d.dll". Невозможно найти или открыть PDB-файл.
"Huffman.exe" (Win32). Загружено "C:\Windows\SysWOW64\vcruntime140d.dll". Невозможно найти или открыть PDB-файл.
"Huffman.exe" (Win32). Загружено "C:\Windows\SysWOW64\advapi32.dll". Невозможно найти или открыть PDB-файл.
"Huffman.exe" (Win32). Загружено "C:\Windows\SysWOW64\msvcrt.dll". Невозможно найти или открыть PDB-файл.
"Huffman.exe" (Win32). Загружено "C:\Windows\SysWOW64\sechost.dll". Невозможно найти или открыть PDB-файл.
"Huffman.exe" (Win32). Загружено "C:\Windows\SysWOW64\rpcrt4.dll". Невозможно найти или открыть PDB-файл.
"Huffman.exe" (Win32). Загружено "C:\Windows\SysWOW64\sspicli.dll". Невозможно найти или открыть PDB-файл.
"Huffman.exe" (Win32). Загружено "C:\Windows\SysWOW64\cryptbase.dll". Невозможно найти или открыть PDB-файл.
"Huffman.exe" (Win32). Загружено "C:\Windows\SysWOW64\bcryptprimitives.dll". Невозможно найти или открыть PDB-файл.
"Huffman.exe" (Win32). Загружено "C:\Windows\SysWOW64\ucrtbased.dll". Невозможно найти или открыть PDB-файл.
"Huffman.exe" (Win32). Загружено "C:\Windows\SysWOW64\kernel.appcore.dll". Невозможно найти или открыть PDB-файл.
Debug Assertion Failed!

Program: C:\WINDOWS\SYSTEM32\MSVCP140D.dll
File: c:\program files (x86)\microsoft visual studio 14.0\vc\include\vector
Line: 1985

Expression: vector iterator not dereferencable

For information on how your program can cause an assertion
failure, see the Visual C++ documentation on asserts.

(Press Retry to debug the application)
"Huffman.exe" (Win32). Загружено "C:\Windows\SysWOW64\user32.dll". Невозможно найти или открыть PDB-файл.
"Huffman.exe" (Win32). Загружено "C:\Windows\SysWOW64\gdi32.dll". Невозможно найти или открыть PDB-файл.
"Huffman.exe" (Win32). Загружено "C:\Windows\SysWOW64\imm32.dll". Невозможно найти или открыть PDB-файл.
"Huffman.exe" (Win32). Загружено "C:\Windows\SysWOW64\msctf.dll". Невозможно найти или открыть PDB-файл.
"Huffman.exe" (Win32). Загружено "C:\Windows\SysWOW64\uxtheme.dll". Невозможно найти или открыть PDB-файл.
"Huffman.exe" (Win32). Загружено "C:\Windows\SysWOW64\combase.dll". Невозможно найти или открыть PDB-файл.
"Huffman.exe" (Win32). Загружено "C:\Windows\SysWOW64\dwmapi.dll". Невозможно найти или открыть PDB-файл.
"Huffman.exe" (Win32). Загружено "C:\Windows\SysWOW64\ole32.dll". Невозможно найти или открыть PDB-файл.
Поток 0x2a4c завершился с кодом 3 (0x3).
Поток 0x2a2c завершился с кодом 3 (0x3).
Программа "[4712] Huffman.exe" завершилась с кодом 3 (0x3).

Answer 1

[jcmvbkbc]

for (size_t i = 0; i <= data.size() / 8; ++i)
  {
    ...
    for (int j = 0; j < 8; ++j)
      if (data[i * 8 + j])
    ...
  }

Вылез за границу data. Если я правильно понял логику, то здесь должно быть что-то такое:

for (size_t i = 0; i < (data.size() + 7) / 8; ++i)
  {
    ...
    for (int j = 0; j < std::min(8, data.size() - i * 8); ++j)
      if (data[i * 8 + j])
    ...
  }

Answer 2

[Олег Цилюрик]

Как исправить ошибку в алгоритме Хаффмана?

Только не стоит называть тему "Как исправить ошибку в алгоритме Хаффмана?".
Лучше называть её как-то нейтральнее ... типа: "Как исправить ошибку в моих чудачествах?".

Comments

[jcmvbkbc]

Для этого у каждого вопроса справа снизу есть многоточие, из которого выпадает меню "Редактировать", с помощью которого можно предложить свою редакцию заголовка/текста/тегов, а автор вопроса или модератор может её принять.

[Олег Цилюрик]

ок

Answer 3

[Владимир Мартьянов]

Нажимаете кнопку "Прервать", смотрите call stack и погружаетесь в интересный мир отладки.