Вычисление общей и относительной частоты значений в диктовке, представляющей правило цепи Маркова

Question

Я сделал функцию make_rule(text, scope=1), которая просто перебирает строку и генерирует словарь, который служит правилом для марковского текстового генератора (где область действия - это количество связанных символов, а не слов).

>>> rule = make_rule("abbcad", 1)
>>> rule
{'a': ['b', 'd'], 'b': ['b', 'c'], 'c': ['a']}

Мне было поручено вычислить энтропию этой системы. Я думаю, что для этого мне нужно знать:

1. Как часто значение появляется в словаре в целом, т.е. его общая частота.
2. Как часто значение появляется при наличии ключа в словаре, то есть его относительной частоты.

Есть ли быстрый способ получить оба эти числа для каждого из значений в словаре?

Для приведенного выше примера мне понадобится следующий вывод:

'a' total: 1, 'a'|'a': 0, 'a'|'b': 0, 'a'|'c': 1
'b' total: 2, 'b'|'a': 1, 'b'|'b': 1, 'b'|'c': 0
'c' total: 1, 'c'|'a': 0, 'c'|'b': 1, 'c'|'c': 0
'd' total: 1, 'd'|'a': 1, 'a'|'b': 1, 'a'|'c': 1

Полагаю, общее число 'a' легко вывести, поэтому, возможно, вместо этого просто выведите список троек для каждого уникального элемента, который появляется в словаре:

[[('a', 'a', 0), ('a', 'b', 0), ('a', 'c', 1)], [('b', 'a', 1), ('b', 'b', 1), ('b', 'c', 0)], ...]

Answer 1

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

Если вы просто хотите найти относительную частоту значения для данного ключа, это легко получить с помощью dict из Counter объектов:

from collections import Counter

rule = {'a': ['b', 'd'], 'b': ['b', 'c'], 'c': ['a']}

freq = {k: Counter(v) for k, v in rule.items()}

… что дает вам freq вот так:

{
    'a': Counter({'b': 1, 'd': 1}),
    'b': Counter({'b': 1, 'c': 1}),
    'c': Counter({'a': 1})
}

… так что вы можете получить относительную частоту 'a', учитывая ключ 'c', например:

>>> freq['c']['a']
1

Поскольку Counter объекты возвращают 0 для несуществующих ключей, вы также получите нулевые частоты, как и следовало ожидать:

>>> freq['a']['c']
0

Если вам нужен список из 3-х кортежей, как указано в вашем вопросе, вы можете получить это с небольшой дополнительной работой. Вот функция для этого:

def triples(rule):               
    freq = {k: Counter(v) for k, v in rule.items()}
    all_values = sorted(set().union(*rule.values()))      
    sorted_keys = sorted(rule)
    return [(v, k, freq[k][v]) for v in all_values for k in sorted_keys] 

Единственное, что, на мой взгляд, не может быть самоочевидным, это строка all_values = ..., которая:

1. создает пустое set()
2. создает union() этого набора со всеми отдельными элементами списков в rule.values() (обратите внимание на использование оператора unpacking *)
3. преобразует результат в список sorted().

Если у вас все еще есть оригинальный текст, вы можете избежать всей этой работы, например, используя all_values = sorted(set(original_text)) вместо.

Вот оно в действии:

>>> triples({'a': ['b', 'd'], 'b': ['b', 'c'], 'c': ['a']})
[
    ('a', 'a', 0), ('a', 'b', 0), ('a', 'c', 1),
    ('b', 'a', 1), ('b', 'b', 1), ('b', 'c', 0),
    ('c', 'a', 0), ('c', 'b', 1), ('c', 'c', 0),
    ('d', 'a', 1), ('d', 'b', 0), ('d', 'c', 0)
]

Answer 2

Я не могу придумать иного быстрого способа, кроме итерации по символам слова, подсчета вхождений в каждом списке словаря и суммирования его в конце:

alphabet = sorted(set("abbcad"))
rule = {'a': ['b', 'd'], 'b': ['b', 'c'], 'c': ['a']}

totalMatrix = []
for elem in alphabet:
    total = 0
    occurences = []
    for key in rule.keys():
        currentCount = rule[key].count(elem)
        total += currentCount
        occurences.append((elem,key,currentCount))
    totalMatrix.append([elem, total] + occurences)

for elem in totalMatrix:
    print(elem)

Содержимое totalMatrix будет:

['a', 1, ('a', 'a', 0), ('a', 'b', 0), ('a', 'c', 1)]
['b', 2, ('b', 'a', 1), ('b', 'b', 1), ('b', 'c', 0)]
['c', 1, ('c', 'a', 0), ('c', 'b', 1), ('c', 'c', 0)]
['d', 1, ('d', 'a', 1), ('d', 'b', 0), ('d', 'c', 0)]