В чем ошибается мой алгоритм (частотный анализ)?

180
04 января 2019, 02:50

Сразу говорю, что мой алгоритм не претендует на лучшее решение, я просто не могу понять, почему он правильно узнает только пробел (в 100% случаев), а остальные буквы как повезет (чем больше текст, тем точнее). Как мне исправить его, чтобы он работал верно?

Функция алгоритма:

#include "header.h"
using namespace std;
void frequency (ifstream & in, ofstream & out){
    map<char,int> fr;
    map<char,char> final_fr;
    map <char, int> :: iterator it = fr.begin();
    map <char, char> :: iterator it_final = final_fr.begin();
    char temp = 0;
    char letters[] = {' ', 'e', 't', 'a', 'o', 'i', 'n', 's',
        'h', 'r','d', 'l', 'c', 'u', 'm', 'w', 'f', 'g', 'y', 'p',
        'b', 'v','k', 'x', 'j', 'q', 'z' };
    //формируем карту из всех символов ascii и счетчика (им будем подсчитывать количество встреченных символов (встретили символ - +1)
    for (int i = 0; i < 255; i++){
        fr.insert(make_pair(char(i),0));
    }
    //считываем файл, сравнивая приходящие из потока значения с ключами мапы
    while (!in.eof()){
        temp = in.get();
        it = fr.find(temp);
        if (it != fr.end()){
            (it->second)++;
        }
    }
    //формируем из полученной мапы с частотностью вектор пар, дабы было легче сортировать
    vector<pair<char,int>> arr_p;
    arr_p.reserve(10);
    for (map <char, int> :: iterator i = fr.begin(); i != fr.end(); i++){
        arr_p.push_back(make_pair(i->first, i->second));
    }
    //сортировка вставками упомянутого вектора
    for (int i = 1; i < arr_p.size (); i++) {
        for (int j = i - 1; (j > 0) && (arr_p[j].second > arr_p[j + 1].second); j--) {
            swap (arr_p[j], arr_p[j + 1]);
        }
    }
    //формирование новой мапы из сортированного вектора(наиболее встречаемые символы лежат в конце) и массива английских букв,
    //изначально отсортированных в порядке встречаемости
    vector<pair<char,int>>::reverse_iterator iter = arr_p.rbegin();
    for (int i = 0; i < 32 && (iter != arr_p.rend()); i++, iter++){
        final_fr.insert(make_pair(iter->first, letters[i]));
    }
    //считываем заново файл, сравнивая приходящие знаки с ключами мапы (если нашли совпадение, то пишем в файл пару ключа - настоящее значение знака)
    in.clear ();
    in.seekg (0, ios::beg);
    while (!in.eof()){
        temp = in.get();
        it_final = final_fr.find(temp);
        if (it_final != final_fr.end()){
            out << it_final->second;
        }
    }
}

Мейн:

int main(int argc, char** argv) {
    ifstream fin;
    ofstream fout;
    int key = 3;
    fin.open("C:\\Users\\user\\Desktop\\output1.txt");
    fout.open("C:\\Users\\user\\Desktop\\input1.txt");
    frequency(fin, fout);
    fin.close();
    fout.close();
    return 0;
}

Заголовок(на всякий):

#pragma once
#include <fstream>
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
void frequency (std::ifstream & in, std::ofstream & out);
Answer 1

Написать ручную сортировку, когда есть готовый std::sort? Интересно.

В целом, на небольших выборках в 200-300 слов частотный алгоритм не дает хорошего результата. Можно специально сделать такой текст, в котором будет чаще встречатся какая то буква. К примеру, в тексте будет упоминатся Фома и все, буква ф, которая в русском языке редко встречается, может выйти на первое место. Поэтому, обычно само сопоставление делает уже человек-лингвист.

Но! есть чудные способы улучшить. К примеру, одиноко стоящей обычно бывает буква а или в. А вот ц или п крайне редко.

Второй способ состоит в том, что не нужно делать частотность буквенную, а нужно делать частотность по парам букв. Есть очень много пар, которые даже для неграмотного написания почти невозможны. к примеру, гласная+мягкий знак.

Я когда то делал частотность по тройкам и это работало просто великолепно. Уже на текстах в сотню букв угадывало до половины алфавита. И потом конечно ручной анализ + словарь.

READ ALSO
Добавление в ArrayList Color

Добавление в ArrayList Color

Немного изменила

148
Игра в угадывание(Head First Java)

Игра в угадывание(Head First Java)

Новичок начал изучать Head First Java столкнулся с проблемой что код используемый в этой книге устарел, помогите довести задачу до рабочего состояния)

159
В чем отличие notify, notifyall?

В чем отличие notify, notifyall?

Я знаю, что notify() - пробуждает любой один поток, а notifyAll() - пробуждает все и даёт доступ одномуНо в чём отличие? в одних случаях работает notify(),...

218
Генерация POJO классов из из схемы данных в виде файла .xml?

Генерация POJO классов из из схемы данных в виде файла .xml?

Всем привет, подскажите пожалуйста, как можно cгенерировать POJO классы из схемы данных в виде файлаxml?

160