Вычислительная сложность строки - PullRequest
Новая
       6

Вычислительная сложность строки

1 голос
/ 18 марта 2020

Моя конечная цель - вычислить один показатель c, который определяет сложность заданной входной строки.

Вот несколько примеров того, что я бы рассмотрел больше сложных строк : 

jkgf82bclov193ng5783jcjus763hesv9w 
389i2vc9wmv02sdcpe34asci3
m32i8s93

И вот несколько примеров того, что я считаю меньше сложных строк: 

ab  
uuuuuuuu
aaaaa11111
a1a1a1a1a1

Кто-нибудь знает какие-либо известные алгоритмы / метрики / коэффициенты, которые могут использоваться для суммирования сложности входной строки в одно число, нормированное между 0 и 1? Возможно, это общая проблема при определении сложности ввода пароля?

Мой подход

Я уверен, что есть лучший способ, чем этот.

Учитывая входная строка s, простой подход, который я выбрал, состоял в том, чтобы найти максимальное количество информации, которое можно закодировать в строку этой длины len(s), используя количество уникальных символов len(set(s)).

т.е. для строки abb, длина = 3, количество уникальных символов = 2. Поэтому моя сложность metri c равна 3 ^ 2 = 9. Если я определяю верхнюю границу, то я могу нормализовать строки между 0 и 1. Если верхняя граница равна 20, 9/20 - это показатель сложности. Если верхняя граница равна 5, показатель сложности равен 1. 

lst = ["000Gg129", "0000aaaa", "a894iunck", "4iu3nclqkerav8e4", "777777777777bbbbbbbbbbb", "36sne8zk"]
upper_bound = 4000000

for s in lst:
    unique_chars = set(s)
    complexity = (len(s) ** len(unique_chars)) / upper_bound
    normalized_complexity = 1 if complexity>1 else complexity
    print(s, normalized_complexity)

Выходные данные 

1            jkgf82bclov193ng5783jcjus763hesv9w
1            389i2vc9wmv02sdcpe34asci3
0.524288     m32i8s93
2e-06        uuuuuuuu
2.5e-05      aaaaa11111
2.5e-05      a1a1a1a1a1
...