Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Частотный анализ текста


Автор: Verus 13.9.2008, 10:19
Помогите пожалуйста с алгоритмом.
Суть такая: необходимо произвести частотный анализ закодированного текста и некоторого эталонного текста на языке источника. По итогам сопоставления результатов частотного анализа для закодированного текста и эталона проводится первичное декодирование.
Искал в нете, может и плохо искал, но ничего толкового по этому вопросу не нашел :(

Автор: ksili 13.9.2008, 11:01
в общем так. считаешь частоты в эталонном тексте. Если эталона нет, то в принципе можешь частоты найти в инете. Если их не найдешь, то сразу говорю, что в русском языке самые распространённые буквы -  Л, Т, Р, Н, С, В, И, А, Е, О.
Затем считаешь частоты закодированныго текста. Выбираешь столько же самых частых букв. Затем пытаешься расшифровать, подставляя некую замену самых частых букв. Если ничего внятного не увидел, подставляй по-другому. после того как определишься с самыми частыми, менее частые буквы легко определятся по остаточному принципу

Автор: Verus 13.9.2008, 11:25
Примерно так и делал. Ничего путного из этого не выходит.

Автор: ksili 13.9.2008, 11:29
По-другому никак и не получится.
Надо просто потерпеливее и повнимательней быть.

Сдлай программку, которая бы тебе помогала в переборе вариантов подстановки. Быстрее работа пойдёт

Автор: Verus 13.9.2008, 11:48
Ну я и написал программу на С++. Делает она следующее: находит кол-во вхождений каждого символа зашифрованного текста и также с эталонным текстом и наиболее частые вхождения из эталонного заменяю на наиболее частые в зашифрованном. Вот кусок кода:
[code=nocolor]
Код

map <int,char, greater<int> > Analyse(CString txt)
{
    map <int,char, greater<int> > res;
    CString ch;
    char tmpchar;
    ch="";
    for(int k=0; k<txt.GetLength(); k++)
    {    
        int todo=0;
        tmpchar = txt[k];
        for(int j=0; j<ch.GetLength(); j++)
        {
            if(tmpchar==ch[j])
                todo++;
        }
        if ( (todo==0) ||(k==0))
        {
            int count=0;
            for(int i=0; i<txt.GetLength(); i++)
            {
                    if (tmpchar==txt[i])
                        count++;
            }
            res[count]=tmpchar;
            ch+=tmpchar;
        }
        
    }
    return res;
}

void CTestDlg::OnBnClickedOk()
{
    map<int,char, greater<int> > res;
    map<int,char, greater<int> > mid;
    map <int,char, greater<int> > :: iterator res_Iter;
    map <int,char, greater<int> > :: iterator exmpl_Iter;
    CString source;
    CString exmpl;
    e_SourceTxt.GetWindowTextA(source);
    e_ExmplTxt.GetWindowTextA(exmpl);
    res=Analyse(source);
    mid=Analyse(exmpl);
    res_Iter=res.begin();
    exmpl_Iter=mid.begin();
    int count=(res.size()<mid.size() ? res.size() : mid.size());
    for(int i=0; i<count; i++,res_Iter++,exmpl_Iter++)
    {
        source.Replace(res_Iter->second, exmpl_Iter->second);
    }
    e_SourceTxt.SetWindowTextA(source);
}

Автор: ksili 13.9.2008, 11:52
У тебя 10 символов одного алфавита надо заменить на 10 символов другого. как именно прога выбирает какой на какой менять? Алгоритм перебора вариантов сделан? Самый частый в эталоне не обязательно будет самым частым в зашифрованном тексте 

Автор: Verus 13.9.2008, 12:19
Самый частый заменяется на самый частый в эталонном тексте. То что это не всегда так я уже понял =) поэтому и интересует как это исправить

Автор: v2v 13.9.2008, 12:23
кроме частот отдельных букв (самые популярные O ~ 9%, E ~ 7% самые редкие - Ф - в 50 раз реже буквы О) можно ещё считать частоты биграмм - пар букв : в русском языке самые популярные биграммы: СТ , ИЕ ... не помню...
вобщем возьмите любой русские текст и нпишите утилитку, которая посчитайте найболее популярные биграммы, найменее популярны и запретные - те которые не встречаются не разу (сойдёт текст на 10К символов).

Автор: aleksh 15.9.2008, 09:15
Цитата(v2v @  13.9.2008,  12:23 Найти цитируемый пост)
можно ещё считать частоты биграмм - пар букв

это даже лучше
к тому же, надо взять буквы эталлоного текста, и подстовлять их на возможные места в защифрованном, найти их место (ориентировочно) и вычислить алгоритм шифрования, потом декодировать по вычисленному алгоритму весь текст, повторять пока не получится читаемый текст
Цитата(v2v @  13.9.2008,  12:23 Найти цитируемый пост)
вобщем возьмите любой русские текст и нпишите утилитку, которая посчитайте найболее популярные биграммы, найменее популярны и запретные - те которые не встречаются не разу (сойдёт текст на 10К символов).

не самый удачный путь, проще поискать статистику на спецелизированных сайтах, ибо статистика то во всех текстах выравнивается, но только при большом количестве текста. пример -- если взять две страницы учебника сопромата и столько же любовного романа -- статистика будет сильно различатся, но если взять по 10-20 книжек из этих областей -- статистика выравняется

Автор: ksili 15.9.2008, 16:57
Цитата(aleksh @  15.9.2008,  13:15 Найти цитируемый пост)
найти их место (ориентировочно) и вычислить алгоритм шифрования

алгоритм шифрования уже известен - это шифр замены

Цитата(aleksh @  15.9.2008,  13:15 Найти цитируемый пост)
если взять две страницы учебника сопромата и столько же любовного романа -- статистика будет сильно различатся

сильно/не сильно - это как повезет. Я вот наоборот думаю, что сильно они не будут отличаться. Хотя отличаться конечно будут

Автор: aleksh 15.9.2008, 17:19
Цитата(ksili @  15.9.2008,  16:57 Найти цитируемый пост)
алгоритм шифрования уже известен - это шифр замены

под алгоритмом подразумевалось -- по какому принципу замена осуществляется

Автор: v2v 15.9.2008, 20:03
Цитата(aleksh @  15.9.2008,  17:19 Найти цитируемый пост)
по какому принципу замена осуществляется

это ключ, а не алгоритм.
Цитата(aleksh @  15.9.2008,  09:15 Найти цитируемый пост)
проще поискать статистику 

я затем и предложил такой метод , потому что статистику найти не удалось.

Автор: aleksh 15.9.2008, 20:12
Цитата(v2v @  15.9.2008,  20:03 Найти цитируемый пост)
это ключ, а не алгоритм.

верно, виноват
Цитата(v2v @  15.9.2008,  20:03 Найти цитируемый пост)
я затем и предложил такой метод , потому что статистику найти не удалось.

странно, надо будет поискать...
но все равно -- текст надо брать большой

Автор: spin2 16.9.2008, 17:39
А закодированный текст большой? Вам нужно именно автоматическую обработку сделать или это неважно?

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)