алгоритм частотного анализа

Question

Я хочу написать программу Java, которая ищет текст шифра и возвращает счетчик частоты символов в шифре, например, шифр "jshddllpkeldldwgbdpked" будет иметь такой результат:

2 буквенных вхождения:

рк = 2, ке = 2, лд = 2

3 вхождения:

pke = 2.

Какой-нибудь алгоритм, который позволяет мне сделать это максимально эффективно?

Answer 1

Стратегия карты хороша, но я бы выбрал HashMap<String, Integer>, так как он учитывает наборы символов.

Перебирая символы в зашифрованном тексте, вы можете сохранить последние символы X, и это даст вам карту для всех вхождений подстрок длины X + 1.

Answer 2

Вы можете сохранить n-грамм в три , изменив нормальный порядок так, чтобы последний символ в n-грамме находился в верхней части дерева. Каждый узел в дереве хранит количество символов. Цикл по строке, отслеживая последние N символов (как Бухб предлагает ). Каждый раз во внешнем цикле вы перемещаетесь по дереву, используя последние N символов для выбора пути, начиная с последнего символа и заканчивая N ^th до последнего. Для каждого посещаемого вами узла увеличивается его счетчик.

Чтобы напечатать частоты в n-граммах, выполните обход в ширину дерева.

Общая производительность оставлена ​​в качестве упражнения.

Answer 3

Обычный подход состоит в том, чтобы использовать какую-то карту, чтобы сопоставить своих персонажей с их количеством. Вы можете использовать HashMap<Character, Integer> например. Затем вы можете перебрать свой зашифрованный текст по символам и либо поместить символ на карту со счетом 1 (если он еще не существует), либо увеличить его счет.

Answer 4

Если набор длин последовательностей, который вам нужен, является фиксированным, очевидный алгоритм принимает линейное число операций подсчета (скажем, поиск счетчика в хеш-таблице и его приращение).

Когда вы говорите «настолько эффективно, насколько это возможно», вы предлагаете потратить немало усилий на скудное улучшение с постоянным коэффициентом, безнадежно искать сублинейный алгоритм или вообще не понимаете классы сложности алгоритма?

Answer 5

Вы можете использовать хеш или график (благодаря outis я знаю, что это специальное имя, такие графы называются "trie"). Хеш будет медленнее, граф будет быстрее. Хэш получит меньше памяти, а граф - в плохой реализации.

Вы не можете сделать это, используя массив, так как он получит ОГРОМНОЕ количество памяти, если ваша максимальная длина последовательности символов равна вашей длине текста, а текст достаточно длинный. Если вы ограничите его, он получит что-то вроде ([number of letters]^[max sequence length])*4 байтов, что будет (52^4)*4 ~= 24Mb памяти для 4 строчных / верхних букв. Если для вас подходит ограниченная длина последовательности, а объем памяти нормальный, алгоритм будет довольно прост для <= 4 букв в последовательности. </p>

Answer 6

Либо есть массив с ячейкой для каждого возможного значения (легко, если в шифре все символы в нижнем регистре - 26 - сложнее, если нет), либо используйте карту, в которой вы передаете символ и увеличиваете значение в любом случае. , Массив быстрее, но менее гибок.

Answer 7

У меня нет ответа на этот вопрос,

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

Если я не ошибаюсь, при таком подходе словарь используется следующим образом:

данные:

abccccabaccabcaaaaabcaaabbbbbccccaaabcbbbbabbabab

парс 1: ключ: * значение: abc

новые данные:

*cccabacc*aaaa*aaabbbbbccccaa*bbbbabbabab

Просто обоснованное предположение, я думаю (не уверен здесь), что стандартный файл "zip" использует этот подход, поэтому я предлагаю вам взглянуть на эти алгоритмы

Answer 8

Вы можете начать с поиска максимально возможной повторяемой последовательности, а затем продолжить свой путь оттуда. Например, если строка состоит из 10 символов, наибольшая повторяемая последовательность может иметь длину 5 букв, поэтому сначала ищите 5 буквенных последовательностей, затем 4 буквы и т. Д., Пока не достигнете 2. Это должно уменьшить количество итераций в вашей программе. 1001 *