Я хочу написать Java-программу, которая просматривает зашифрованный текст и возвращает количество символов в шифре, например, шифр: "jshddllpkeldldwgbdpked" будет иметь такой результат:
2 вхождения букв:
pk = 2, ke = 2, ld = 2
3 вхождения букв:
пке = 2.
Любой алгоритм, который позволяет мне сделать это максимально эффективно?
Стратегия карты хороша, но я бы выбрал HashMap<String, Integer>, поскольку учитываются кортежи символов.
Перебирая символы в зашифрованном тексте, вы можете сохранить последние X символов, и это даст вам карту всех вхождений подстрок длины X+1.
Обычный подход состоял бы в том, чтобы использовать какую-то карту, чтобы сопоставить ваших персонажей с их счетами. Например, вы можете использовать HashMap<Character, Integer>. Затем вы можете перебрать свой зашифрованный текст по символам и либо поместить символ на карту со счетом 1 (если он еще не существует), либо увеличить его счетчик.
Вы можете хранить n-граммы в trie, изменяя нормальный порядок, чтобы последний символ в n-грамме находился вверху дерева. Каждый узел в дереве хранит количество символов. Прокрутите строку, отслеживая последние N символов (как предлагает Buhb). Каждый раз во внешнем цикле вы проходите по дереву, используя последние N символов для выбора пути, начиная с последнего символа и заканчивая Nth последним. Для каждого узла, который вы посещаете, увеличивается его счетчик.
Чтобы напечатать частоты n-грамм, выполните обход дерева в ширину.
Общая производительность оставлена в качестве упражнения.
Либо имейте массив с ячейкой для каждого возможного значения (легко, если зашифрованный текст состоит из всех символов нижнего регистра - 26 - сложнее, если нет), либо перейдите к карте, где вы передаете символ и увеличиваете значение в любом случае. Массив быстрее, но менее гибок.
Если набор длин необходимых вам последовательностей фиксирован, очевидный алгоритм использует линейное количество операций подсчета (скажем, поиск счетчика в хеш-таблице и его увеличение).
Когда вы говорите «как можно эффективнее», вы предлагаете потратить много сил на мизерное улучшение постоянного фактора, безнадежно искать сублинейный алгоритм или вообще не понимаете классов сложности алгоритма?
Вы можете использовать хэш или граф (благодаря outis, теперь я знаю, что это специальное название, такой вид графов называется "trie"). Хэш будет медленнее, граф будет быстрее. Хэш получит меньше памяти, граф займет больше при плохой реализации.
Вы не можете сделать это с помощью массива, так как он получит ОГРОМНЫЙ объем памяти, если ваша максимальная длина последовательности символов равна длине вашего текста, а текст достаточно длинный. Если вы ограничите его, он получит что-то вроде ([number of letters]^[max sequence length])*4 байтов, что будет (52^4)*4 ~= 24Mb памяти для последовательности из 4 нижних/верхних букв. Если вас устраивает ограниченная длина последовательности и этот объем памяти является нормальным, то алгоритм будет довольно простым для ‹=4 букв в последовательности.
Вы можете начать с поиска максимально возможной повторяемой последовательности, а затем двигаться дальше. Например, если строка состоит из 10 символов, самая большая повторяющаяся последовательность, которая может возникнуть, будет состоять из 5 букв, поэтому сначала ищите последовательности из 5 букв, затем из 4 букв и так далее, пока не достигнете 2. Это должно уменьшить количество итераций в вашей программе.
У меня нет ответа на этот вопрос,
Но я чувствую, что этот алгоритм точно такой же, как алгоритм, используемый алгоритмами сжатия для создания сжатых файлов с подходом словаря.
Если я не ошибаюсь, в этом подходе словарь используется следующим образом:
данные:
abccccabaccabcaaaaabcaaabbbbbccccaaabcbbbbabbabab
разбор 1: ключ: * значение: abc
новые данные:
*cccabacc*aaaa*aaabbbbbccccaa*bbbbabbabab
Просто обоснованное предположение, я думаю (здесь не уверен), что стандартный «zip» файл использует этот подход, поэтому я предлагаю вам взглянуть на эти алгоритмы.
