1

Задача: посчитать индекс совпадений для заданного сообщения

Индекс совпадений это введите сюда описание изображения

Код:

    mes = 'dlcpmpcxuopjnsaeqcxxcnhccgpstrsslyjyzsjiejzlylirsgastfovukwdyvkepydiblcjosllerdmqdeyvfcbxgkvmerbwgbvbtsmyxhscibkqcdejmmnripnmqmxmcagdgflirgicxggzlcbejzlylircejlipdmqccqdikyrjiwusxaribkpnrezoxqkjrovqozcbejgspnwyxhqgmrmlccacbigxhgmerohziapsxgxkrrijoxrovmpxfogmbvcctmxhgxkyvtfkfcdmldlcmmnripdivd'
mas = list(mes)
def get_index(mes):
    mas = list(mes)
    le = len(mas)
    j = 2

    for i in range(2, 8):
        count_i = []
        for j in range(0, le, j):
            count = mas.count(mas[j]) - 1
            count_i.append(count)
        j = i + 1
        index = 0
        for k in range(len(count_i)):
            index += (count_i[k] * (count_i[k] - 1)) / (le * (le - 1))        
        print(index)

get_index(mes)

Проблема: получаются не корректные значения.

Хотел бы увидеть комментарии в чем может быть проблема.

2 ответа 2

1

Попробуйте так:

from collections import Counter

def idx_of_coincidence(msg):
    c = Counter(list(msg))
    return sum(x*(x-1) for x in c.values())/(len(msg)*(len(msg) - 1))

print(min([(i,idx_of_coincidence(mes[::i])) for i in range(1, 50)], 
          key=lambda x: abs(0.0667 - x[1])))

Вывод:

(19, 0.06666666666666667)

Чтобы посмотреть все индексы совпадений:

In [24]: [(i,idx_of_coincidence(mes[::i])) for i in range(1, 50)]
Out[24]:
[(1, 0.0428611777997458),
 (2, 0.04090694378837978),
 (3, 0.05806858826004629),
 (4, 0.03767123287671233),
 (5, 0.04792518994739918),
 (6, 0.06547619047619048),
 (7, 0.03484320557491289),
 (8, 0.03153153153153153),
 (9, 0.058712121212121215),
 (10, 0.05517241379310345),
 (11, 0.045584045584045586),
 (12, 0.056666666666666664),
 (13, 0.043478260869565216),
 (14, 0.02857142857142857),
 (15, 0.06842105263157895),
 (16, 0.03508771929824561),
 (17, 0.026143790849673203),
 (18, 0.058823529411764705),
 (19, 0.06666666666666667),
 (20, 0.06666666666666667),
 (21, 0.03296703296703297),
 (22, 0.054945054945054944),
 (23, 0.02564102564102564),
 (24, 0.05128205128205128),
 (25, 0.015151515151515152),
 (26, 0.045454545454545456),
 (27, 0.07272727272727272),
 (28, 0.03636363636363636),
 (29, 0.01818181818181818),
 (30, 0.044444444444444446),
 (31, 0.08888888888888889),
 (32, 0.044444444444444446),
 (33, 0.1111111111111111),
 (34, 0.0),
 (35, 0.05555555555555555),
 (36, 0.05555555555555555),
 (37, 0.0),
 (38, 0.03571428571428571),
 (39, 0.07142857142857142),
 (40, 0.0),
 (41, 0.0),
 (42, 0.047619047619047616),
 (43, 0.09523809523809523),
 (44, 0.09523809523809523),
 (45, 0.047619047619047616),
 (46, 0.047619047619047616),
 (47, 0.047619047619047616),
 (48, 0.047619047619047616),
 (49, 0.06666666666666667)]
2
  • Спасибо, значения близки, но из этого набора все равно не понять, что длина ключа равна 3
    – Jan Novak
    11 мар 2018 в 13:29
  • @JanNovak, тогда можно ввести погрешность и учитывать значение погрешности при поиске 12 мар 2018 в 9:53
0

Проблема в этом цикле:

for k in range(len(count_i)):
        index += (count_i[k] * (count_i[k] - 1)) / (le * (le - 1))

Правильный вариант:

for k in range(len(count_i)):
        index += (k * (k - 1)) / (le * (le - 1))

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

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