Существует ли формальное определение различия символов в строке и, если да, то как оно рассчитывается?

Question

Обзор

Я хочу проанализировать разницу между двумя символами в процессе проверки надежности пароля.

Я объясню, чего я пытаюсь достичь и почему, и хотел бы знать, формально ли определяется то, что я ищу, и есть ли рекомендуемые алгоритмы для достижения этого.

Что я хочу сделать

По всей строке я хочу сравнить текущий символ с предыдущим и определить, насколько они отличаются.

Поскольку это относится к проверке надежности пароля, разница между одним символом и его предшественником в строке может быть определена как то, насколько предсказуемый символ N основан на знании символа N - 1. Для этого может существовать формальное определение, которое я Я не в курсе.

Пример

Пароль abc123 может быть менее безопасным, чем azu590. Оба содержат три буквы, за которыми следуют три цифры, однако в случае с первой последовательность является более предсказуемой.

Я предполагаю, что гадатель пароля мог бы попробовать некоторые очевидные последовательности, такие, что abc123 будет пробоваться задолго до azu590.

Учитывая десятичные значения ASCII для символов в этих строках и учитывая, что b равно 1, отличается от a, а c равно 1 снова отличается от b, мы можем получить упрощенное вычисление разностей.

Игнорируя случаи, когда два последовательных символа не принадлежат к одному и тому же классу символов, мы могли бы сказать, что abc123 имеет общую разницу символов и символов 4, тогда как azu590 имеет аналогичную разницу 25 + 5 + 4 + 9 = 43.

Это существует?

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

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

Answer 1

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

Также можно использовать варианты этой техники (Цепочка Маркова порядка m ), где вы, например, рассматриваете два предыдущих символа вместо одного.

После создания модели вы можете использовать вероятность генерации пароля из модели в качестве мерысвоей силы.Это произведение вероятностей каждого перехода состояния.

Answer 2

Для общих сигналов / данных временных рядов это известно как Автокорреляция. Вы можете попробовать адаптировать статистику Дурбина-Ватсона и проверить положительную автокорреляцию между персонажами. Наивным способом может быть использование кодовых точек Unicode для каждого символа, но я уверен, что этого будет недостаточно.