2

Доброго времени суток, уважаемое сообщество. У меня к вам вопрос не касающийся программирования, но, возможно, кто-то из вас уже сталкивался с подобной проблемой. Я пишу программу для дешифрования шифра простой замены с помощью частотного анализа. Я решил дешифровать по частотам биграмм. Но вместо использования готовой статистики по частотам, мне хотелось бы собрать свою. То есть я буду вводить тексты на русском, программа будет считать частоту биграмм в них и обновлять таблицу статистики в файле. Вот, собственно, и сам вопрос: как мне обновить статистику? Первой мыслью было взять среднее арифметическое частоты биграммы из файла и из текста, и записать в статистику. Но это явно не то.

P.S. Простите, что вопрос не по теме, просто больше негде искать.

2 ответа 2

4

Что вообще такое частота в контексте сбора этой статистики?

Это отношение количества в тексте биграмм с одним конкретным значением к общему количеству всех биграмм.


Так, у нас есть два текста и некая биграмма X.

Для первого текста, в котором всего N1 биграмм и N1X биграмм Х, частота равна P1X=N2X/N1.
Для второго текста, соответственно, P2X=N2X/N2.

Теперь у нас есть сумма этих двух текстов. Грубо считаем, что конкатенация без учёта биграмм на стыке.

То, что мы хотим получить, выглядит как (N1X + N2X)/(N1 + N2): сколько всего раз эта биграмма встречается, разделить на общее число биграмм в текстах. Очевидно, среднее арифметическое P1X и P1X даст нечто совсем другое. Более того, видно, что одних частот знать недостаточно, нужно ещё как минимум знать общее число биграмм в обоих текстах.

Вам нужно среднее взвешенное, где весами будут объёмы (в биграммах) соответствующих текстов. Собственно, если в формуле выше выразить количества через частоты, получится прямо оно:

(P1XN1 + P2XN2)/(N1 + N2)

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

1
  • Все работает, большое спасибо за помощь. Commented 24 нояб. 2016 в 13:17
4

В принципе, задача сводиться к тому, как посчитать среднее арифметическое, не запоминая всех измерений.

Когда то давно у меня был калькулятор, который умел считать средне арифметическое массива чисел. Я долго думал, что он запоминает все числа, но у него явно не было сколько памяти. Я так и не знаю, как именно он считал это, но я нашел три способа

  • запоминаем не среднее, а сумму и количество. А среднее всегда можно посчитать
  • считаем по следующей формуле "новое среднее" = ("старое среднее" * "кол-во" + текущее) / ("кол-во" + 1). где "кол-во" - это количество чисел, для которых уже посчитали среднее.

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

Поэтому приходит на помощь третий способ суммировать числа, поделив их на две (или три) группы. В одной суммируются большие числа, в второй - маленькие.

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

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.