Частотный анализ текста на С++. Быстро и просто

Привет!

Хочу рассказать о быстром частотном анализе текста на С++, практически без применения головы и алгоритмов.
Иногда такое задание часто дают на контрольной по программированию в каком-нибудь МИРЭА, или МИФИ.

Суть задачи такова. На входе текстовый файл TextForAnalyze.txt(довольно большой ≈ 400кб). Необходимо получить порядок встречаемости слов файле(в порядке убывания частоты). При сравнении слов регистр не учитывать. Необходимо игнорировать предлоги и союзы (список слов в стоп-словаре составить самостоятельно, стоп-словарь хранить в файле). Разделителями слов являются пробел, табуляция, символы перевода строки, знаки, «слеши» и тд.

Названия функций я делал понятными и не нуждающихся в объяснении.

Для начала нужно быстро получить текст.

std::string GetText(const char * filename)
{
	std::ifstream in(filename);
	std::string data;
	data.assign((std::istreambuf_iterator<char>(in.rdbuf())), std::istreambuf_iterator<char>());

	tolowerStr(data);
	return data;
}

Обратим внимание на tolowerStr! Я написал его сам так как мы все знаем какая

 std::transform(s.begin(), s.end(), s.begin(), ::toupper); 

прожорливая функция, поэтому забудем про нее и реализуем более быструю «функцию»:

//ToLowerConverter.hpp
class ToLowerConverter
{
public:
	ToLowerConverter();
	char Get(char ch);
	char operator[](char ch);
	void StrToLower(std::string &str);

private:
	char _convertTable[256];
};

//ToLowerConverter.cpp

ToLowerConverter::ToLowerConverter()
{
	for (int i = 0; i < 256; ++i)
		_convertTable[i] = tolower(i);
}

char ToLowerConverter::Get(char ch)
{
	return _convertTable[(unsigned char)ch];
}



char ToLowerConverter::operator[](char ch)
{
	return _convertTable[(unsigned char)ch];
}

void ToLowerConverter::StrToLower(std::string &str)
{
	char * c = const_cast<char*>(str.c_str());
	size_t l = str.size();

	for (char * c2 = c; c2 < c + l; c2++)
		*c2 = Get(*c2);
}

В итоге наша «tolowerStr» будет выглядеть так:

char SmartToLower(char ch)
{
	static ToLowerConverter converter;

	return converter[ch];
}

void tolowerStr(std::string &s)
{
	char * c = const_cast<char*>(s.c_str());
	size_t l = s.size();

	for (char* c2 = c; c2 < c + l; c2++)
		*c2 = SmartToLower(*c2);
};

Теперь мы будем извращаться по полной и создавать свою локаль. Точнее новый «объект локали» т.к нам не нужны всякие скобки, звездочки, проценты и так далее.

struct ListOfSpaces : std::ctype<char>
{
	ListOfSpaces() : std::ctype<char>(DelimsTable())
	{
	}

	static mask const* DelimsTable()
	{
		static mask rc[table_size];
		rc[':'] = std::ctype_base::space;
		rc[' '] = std::ctype_base::space;
		rc['.'] = std::ctype_base::space;
		rc['-'] = std::ctype_base::space;
		rc['('] = std::ctype_base::space;
		rc[')'] = std::ctype_base::space;
		rc['+'] = std::ctype_base::space;
		rc['/'] = std::ctype_base::space;
		rc['"'] = std::ctype_base::space;
		rc['1'] = std::ctype_base::space;
		rc['2'] = std::ctype_base::space;
		rc['3'] = std::ctype_base::space;
		rc['4'] = std::ctype_base::space;
		rc['5'] = std::ctype_base::space;
		rc['6'] = std::ctype_base::space;
		rc['7'] = std::ctype_base::space;
		rc['8'] = std::ctype_base::space;
		rc['9'] = std::ctype_base::space;
		rc['0'] = std::ctype_base::space;
		rc['@'] = std::ctype_base::space;
		rc['#'] = std::ctype_base::space;
		rc['$'] = std::ctype_base::space;
		rc['%'] = std::ctype_base::space;
		rc['t'] = std::ctype_base::space;
		rc['n'] = std::ctype_base::space;
		rc[';'] = std::ctype_base::space;
		rc['~'] = std::ctype_base::space;
		rc['№'] = std::ctype_base::space;
		rc['%'] = std::ctype_base::space;
		rc['*'] = std::ctype_base::space;
		rc['['] = std::ctype_base::space;
		rc[']'] = std::ctype_base::space;
		rc['='] = std::ctype_base::space;
		rc['“'] = std::ctype_base::space;
		rc['&'] = std::ctype_base::space;
		rc['''] = std::ctype_base::space;
		rc[','] = std::ctype_base::space;
		rc['<'] = std::ctype_base::space;
		rc['>'] = std::ctype_base::space;
		rc['\'] = std::ctype_base::space;
		rc['^'] = std::ctype_base::space;
		rc['|'] = std::ctype_base::space;

		return &rc[0];
	}

};

Эта битовая маска наследуется от класса ctype. всего до 256 символов. Да, выглядит ужасно, но зато это очень удобно на практике.

Ну теперь практически все сделано. Записываем в текстовый файл с руки все предлоги, которые не хотим видеть в списке, и пишем такой вот код.

typedef  std::pair<std::string, size_t> sipair; // я не знал как адекватно назвать пару<сторока, число> 


std::map<std::string, size_t> GetFrequencyMap(const char * filename) 
{
	std::map<std::string, size_t> result;
	std::string text = GetText(filename);

	std::stringstream inputStringStream(text);
	inputStringStream.imbue(std::locale(inputStringStream.getloc(), std::unique_ptr<ListOfSpaces>(new ListOfSpaces).release())); /*вот наш заветный 
        ListOfSpaces*/

	std::string word;
	while (inputStringStream >> word) 
		result[word]++; 

	return result;
}


class GreatPairCmp // Компаратор для сортировки для вывода результата в файл.
{
public:
	bool operator()(const sipair strInt1, const sipair strInt2)
	{
		return strInt1.second > strInt2.second;
	}
};

std::set<std::string> StopDictionary(const char * filename) // Множество стоп-слов. 
{
	std::ifstream inStream(filename);
	std::set<std::string> result; 
	std::string word;

	for (; !inStream.eof(); inStream >> word)
		result.insert(word);

	return result;
}

std::vector<sipair> GetSortedVector(const char * filename, const char * StopD) 
{
	std::map<std::string, size_t> map = GetFrequencyMap(filename);
	std::set<std::string> stopD = StopDictionary(StopD);
	std::vector<sipair> result;
	
	for (auto it = map.begin(); it != map.end(); ++it)
	{
		bool finded = stopD.find(it->first) != stopD.end();
		if (!finded) //Если не нашли стоп-слово "пихаем его в результат" 
			result.push_back(*it); 
	}

	std::sort(result.begin(), result.end(), GreatPairCmp());

	return result;
}

Ну вот и все дело сделано, научный текст весом в 400кб был пройден за 21ms.
Что я считаю довольно хорошим результатом.
Для тестирования я пользуюсь GTEST`ами это удобно.

// #include необходимое 

TEST(ParseText, Test1)
{

	std::vector<sipair> result = GetSortedVector("../TextForAnalyze.txt", "../Diction.txt");
	std::ofstream some("../result.txt");
	for (auto it = result.begin(); it != result.end(); ++it)
		some << it->first << ":" << it->second << std::endl;
}

[==========] Running 3 tests from 1 test case.
[----------] Global test environment set-up.
[----------] 3 tests from ParseText
[ RUN      ] ParseText.Test1
[       OK ] ParseText.Test1 (19 ms) // получилось меньше но когда как, запуская на домашней машине с i7-3770K получалось быстрее
[ RUN      ] ParseText.Test2
[       OK ] ParseText.Test2 (2 ms) //эти тесты просто проверяют .. был создан файл в него с руки написаны слова  и подсчитаны ..
[ RUN      ] ParseText.Test3
[       OK ] ParseText.Test3 (1 ms)
[----------] 3 tests from ParseText (29 ms total)

[----------] Global test environment tear-down
[==========] 3 tests from 1 test case ran. (38 ms total)
[  PASSED  ] 3 tests.
Для продолжения нажмите любую клавишу . . .

Вот функции которыми я проверяю равенство двух файлов (ожидаемого и действительного «ParseText.Test2»):

int GetSizeFile(char * filename)
{
	std::ifstream file(filename, std::ios_base::binary);
	int size = 0;

	file.seekg(0, std::ios_base::end);
	size = (int)file.tellg();

	return size;
}

bool CompareFiles(char * leftFile, char * rigthFile)
{
	int size1 = GetSizeFile(leftFile);
	int size2 = GetSizeFile(rigthFile);

	if (size1 != size2)
		return false;


	std::ifstream in1(leftFile, std::ifstream::binary);
	std::ifstream in2(rigthFile, std::ifstream::binary);

	const int blockSize = 4096; //можно побольше
	do
	{
		char buffer1[blockSize], buffer2[blockSize];

		in1.read(buffer1, sizeof buffer1);
		in2.read(buffer2, sizeof buffer2);

		if (in2.gcount() != in1.gcount())
			return false;

		if (0 != memcmp(buffer1, buffer2, (int)in1.gcount()))
			return false;

	} while (!in1.eof() && !in2.eof());

	return true;
}