Module szyfrow.support.language_models
+Descriptive models of a natural language (in this case, English).
+The functions Pwords()
, Pletters()
, Pbigrams()
, and Ptrigrams()
return the
+log probability of a section of text.
If you want to use a different language, replace the data files in
+szyfrow/language_model_files
.
-
+
count_1l.txt
: counts of single letters
+count_2l.txt
: counts of pairs letters, bigrams
+count_3l.txt
: counts of triples of letters, triagrams
+words.txt
: a dictionary of words, used for keyword-based cipher breaking. +These words should only contain characters cointained in +string.ascii_letters
.
+
+Expand source code +
+"""Descriptive models of a natural language (in this case, English).
+
+The functions `Pwords`, `Pletters`, `Pbigrams`, and `Ptrigrams` return the
+log probability of a section of text.
+
+If you want to use a different language, replace the data files in
+[`szyfrow/language_model_files`](../language_model_files/index.html).
+
+* `count_1l.txt`: counts of single letters
+* `count_2l.txt`: counts of pairs letters, bigrams
+* `count_3l.txt`: counts of triples of letters, triagrams
+* `words.txt`: a dictionary of words, used for keyword-based cipher breaking.
+ These words should only contain characters cointained in
+ `string.ascii_letters`.
+
+"""
+
+import string
+import random
+import collections
+import itertools
+from math import log10
+import os
+import importlib.resources as pkg_resources
+
+import szyfrow.support.norms
+from szyfrow.support.utilities import sanitise, deduplicate
+from szyfrow import language_model_files
+
+
+def datafile(name, sep='\t'):
+ """Read key,value pairs from file.
+ """
+ with pkg_resources.open_text(language_model_files, name) as f:
+ # with open(p name), 'r') as f:
+ for line in f:
+ splits = line.split(sep)
+ yield [splits[0], int(splits[1])]
+
+english_counts = collections.Counter(dict(datafile('count_1l.txt')))
+"""Counts of single letters in English."""
+normalised_english_counts = szyfrow.support.norms.normalise(english_counts)
+"""Normalised counts of single letters in English (the sum of all counts
+adds to 1)."""
+
+english_bigram_counts = collections.Counter(dict(datafile('count_2l.txt')))
+"""Counts of letter bigrams in English."""
+normalised_english_bigram_counts = szyfrow.support.norms.normalise(english_bigram_counts)
+"""Normalised counts of letter bigrams in English (the sum of all counts
+adds to 1)."""
+
+english_trigram_counts = collections.Counter(dict(datafile('count_3l.txt')))
+"""Counts of letter trigrams in English."""
+normalised_english_trigram_counts = szyfrow.support.norms.normalise(english_trigram_counts)
+"""Normalised counts of letter trigrams in English (the sum of all counts
+adds to 1)."""
+
+keywords = []
+"""A sample list of keywords, to act as a dictionary for
+dictionary-based cipher breaking attempts."""
+with pkg_resources.open_text(language_model_files, 'words.txt') as f:
+ keywords = [line.rstrip() for line in f]
+
+
+def transpositions_of(keyword):
+ """Finds the transpostions given by a keyword. For instance, the keyword
+ 'clever' rearranges to 'celrv', so the first column (0) stays first, the
+ second column (1) moves to third, the third column (2) moves to second,
+ and so on.
+
+ If passed a tuple, assume it's already a transposition and just return it.
+
+ >>> transpositions_of('clever')
+ (0, 2, 1, 4, 3)
+ >>> transpositions_of('fred')
+ (3, 2, 0, 1)
+ >>> transpositions_of((3, 2, 0, 1))
+ (3, 2, 0, 1)
+ """
+ if isinstance(keyword, tuple):
+ return keyword
+ else:
+ key = deduplicate(keyword)
+ transpositions = tuple(key.index(l) for l in sorted(key))
+ return transpositions
+
+transpositions = collections.defaultdict(list)
+"""A sample dict of transpositions, to act as a dictionary for
+dictionary-based cipher breaking attempts. Each key is a transposition,
+each value is a list of words that give that transposition."""
+for word in keywords:
+ transpositions[transpositions_of(word)] += [word]
+
+
+def weighted_choice(d):
+ """Generate random item from a dictionary of item counts
+ """
+ delems, dweights = list(zip(*d.items()))
+ return random.choices(delems, dweights)[0]
+ # target = random.uniform(0, sum(d.values()))
+ # cuml = 0.0
+ # for (l, p) in d.items():
+ # cuml += p
+ # if cuml > target:
+ # return l
+ # return None
+
+def random_english_letter():
+ """Generate a random letter based on English letter counts
+ """
+ return weighted_choice(normalised_english_counts)
+
+
+def ngrams(text, n):
+ """Returns all n-grams of a text
+
+ >>> ngrams(sanitise('the quick brown fox'), 2) # doctest: +NORMALIZE_WHITESPACE
+ ['th', 'he', 'eq', 'qu', 'ui', 'ic', 'ck', 'kb', 'br', 'ro', 'ow', 'wn',
+ 'nf', 'fo', 'ox']
+ >>> ngrams(sanitise('the quick brown fox'), 4) # doctest: +NORMALIZE_WHITESPACE
+ ['theq', 'hequ', 'equi', 'quic', 'uick', 'ickb', 'ckbr', 'kbro', 'brow',
+ 'rown', 'ownf', 'wnfo', 'nfox']
+ """
+ return [text[i:i+n] for i in range(len(text)-n+1)]
+
+
+class Pdist(dict):
+ """A probability distribution estimated from counts in datafile.
+ Values are stored and returned as log probabilities.
+ """
+ def __init__(self, data=[], estimate_of_missing=None):
+ data1, data2 = itertools.tee(data)
+ self.total = sum([d[1] for d in data1])
+ for key, count in data2:
+ self[key] = log10(count / self.total)
+ self.estimate_of_missing = estimate_of_missing or (lambda k, N: 1./N)
+ def __missing__(self, key):
+ return self.estimate_of_missing(key, self.total)
+
+def log_probability_of_unknown_word(key, N):
+ """Estimate the probability of an unknown word.
+ """
+ return -log10(N * 10**((len(key) - 2) * 1.4))
+
+Pw = Pdist(datafile('count_1w.txt'), log_probability_of_unknown_word)
+"""A [Pdist](#szyfrow.support.language_models.Pdist) holding log probabilities
+of words. Unknown words have their probability estimated by
+[log_probability_of_unknown_word](#szyfrow.support.language_models.log_probability_of_unknown_word)"""
+Pl = Pdist(datafile('count_1l.txt'), lambda _k, _N: 0)
+"""A [Pdist](#szyfrow.support.language_models.Pdist) holding log probabilities
+of single letters. Unknown words have their probability estimated as zero."""
+P2l = Pdist(datafile('count_2l.txt'), lambda _k, _N: 0)
+"""A [Pdist](#szyfrow.support.language_models.Pdist) holding log probabilities
+of letter bigrams. Unknown words have their probability estimated as zero."""
+P3l = Pdist(datafile('count_3l.txt'), lambda _k, _N: 0)
+"""A [Pdist](#szyfrow.support.language_models.Pdist) holding log probabilities
+of letter trigrams. Unknown words have their probability estimated as zero."""
+
+def Pwords(words):
+ """The Naive Bayes log probability of a sequence of words.
+ """
+ return sum(Pw[w.lower()] for w in words)
+
+def Pletters(letters):
+ """The Naive Bayes log probability of a sequence of letters.
+ """
+ return sum(Pl[l.lower()] for l in letters)
+
+def Pbigrams(letters):
+ """The Naive Bayes log probability of the bigrams formed from a sequence
+ of letters.
+ """
+ return sum(P2l[p] for p in ngrams(letters, 2))
+
+def Ptrigrams(letters):
+ """The Naive Bayes log probability of the trigrams formed from a sequence
+ of letters.
+ """
+ return sum(P3l[p] for p in ngrams(letters, 3))
+
+
+def cosine_distance_score(text):
+ """Finds the dissimilarity of a text to English, using the cosine distance
+ of the frequency distribution.
+
+ >>> cosine_distance_score('abcabc') # doctest: +ELLIPSIS
+ 0.73771...
+ """
+ # return szyfrow.support.norms.cosine_distance(english_counts,
+ # collections.Counter(sanitise(text)))
+ return 1 - szyfrow.support.norms.cosine_similarity(english_counts,
+ collections.Counter(sanitise(text)))
+
+
+if __name__ == "__main__":
+ import doctest
+ doctest.testmod()
+Global variables
+-
+
var P2l
+-
++
A Pdist holding log probabilities +of letter bigrams. Unknown words have their probability estimated as zero.
+ var P3l
+-
++
A Pdist holding log probabilities +of letter trigrams. Unknown words have their probability estimated as zero.
+ var Pl
+-
++
A Pdist holding log probabilities +of single letters. Unknown words have their probability estimated as zero.
+ var Pw
+-
++
A Pdist holding log probabilities +of words. Unknown words have their probability estimated by +log_probability_of_unknown_word
+ var english_bigram_counts
+-
++
Counts of letter bigrams in English.
+ var english_counts
+-
++
Counts of single letters in English.
+ var english_trigram_counts
+-
++
Counts of letter trigrams in English.
+ var keywords
+-
++
A sample list of keywords, to act as a dictionary for +dictionary-based cipher breaking attempts.
+ var normalised_english_bigram_counts
+-
++
Normalised counts of letter bigrams in English (the sum of all counts +adds to 1).
+ var normalised_english_counts
+-
++
Normalised counts of single letters in English (the sum of all counts +adds to 1).
+ var normalised_english_trigram_counts
+-
++
Normalised counts of letter trigrams in English (the sum of all counts +adds to 1).
+ var transpositions
+-
++
A sample dict of transpositions, to act as a dictionary for +dictionary-based cipher breaking attempts. Each key is a transposition, +each value is a list of words that give that transposition.
+
Functions
+-
+
+def Pbigrams(letters) +
+-
++
The Naive Bayes log probability of the bigrams formed from a sequence +of letters.
+++Expand source code +
+
+def Pbigrams(letters): + """The Naive Bayes log probability of the bigrams formed from a sequence + of letters. + """ + return sum(P2l[p] for p in ngrams(letters, 2))
+ +def Pletters(letters) +
+-
++
The Naive Bayes log probability of a sequence of letters.
+++Expand source code +
+
+def Pletters(letters): + """The Naive Bayes log probability of a sequence of letters. + """ + return sum(Pl[l.lower()] for l in letters)
+ +def Ptrigrams(letters) +
+-
++
The Naive Bayes log probability of the trigrams formed from a sequence +of letters.
+++Expand source code +
+
+def Ptrigrams(letters): + """The Naive Bayes log probability of the trigrams formed from a sequence + of letters. + """ + return sum(P3l[p] for p in ngrams(letters, 3))
+ +def Pwords(words) +
+-
++
The Naive Bayes log probability of a sequence of words.
+++Expand source code +
+
+def Pwords(words): + """The Naive Bayes log probability of a sequence of words. + """ + return sum(Pw[w.lower()] for w in words)
+ +def cosine_distance_score(text) +
+-
++
Finds the dissimilarity of a text to English, using the cosine distance +of the frequency distribution.
+>>> cosine_distance_score('abcabc') # doctest: +ELLIPSIS +0.73771... +
+++Expand source code +
+
+def cosine_distance_score(text): + """Finds the dissimilarity of a text to English, using the cosine distance + of the frequency distribution. + + >>> cosine_distance_score('abcabc') # doctest: +ELLIPSIS + 0.73771... + """ + # return szyfrow.support.norms.cosine_distance(english_counts, + # collections.Counter(sanitise(text))) + return 1 - szyfrow.support.norms.cosine_similarity(english_counts, + collections.Counter(sanitise(text)))
+ +def datafile(name, sep='\t') +
+-
++
Read key,value pairs from file.
+++Expand source code +
+
+def datafile(name, sep='\t'): + """Read key,value pairs from file. + """ + with pkg_resources.open_text(language_model_files, name) as f: + # with open(p name), 'r') as f: + for line in f: + splits = line.split(sep) + yield [splits[0], int(splits[1])]
+ +def log_probability_of_unknown_word(key, N) +
+-
++
Estimate the probability of an unknown word.
+++Expand source code +
+
+def log_probability_of_unknown_word(key, N): + """Estimate the probability of an unknown word. + """ + return -log10(N * 10**((len(key) - 2) * 1.4))
+ +def ngrams(text, n) +
+-
++
Returns all n-grams of a text
+>>> ngrams(sanitise('the quick brown fox'), 2) # doctest: +NORMALIZE_WHITESPACE +['th', 'he', 'eq', 'qu', 'ui', 'ic', 'ck', 'kb', 'br', 'ro', 'ow', 'wn', + 'nf', 'fo', 'ox'] +>>> ngrams(sanitise('the quick brown fox'), 4) # doctest: +NORMALIZE_WHITESPACE +['theq', 'hequ', 'equi', 'quic', 'uick', 'ickb', 'ckbr', 'kbro', 'brow', + 'rown', 'ownf', 'wnfo', 'nfox'] +
+++Expand source code +
+
+def ngrams(text, n): + """Returns all n-grams of a text + + >>> ngrams(sanitise('the quick brown fox'), 2) # doctest: +NORMALIZE_WHITESPACE + ['th', 'he', 'eq', 'qu', 'ui', 'ic', 'ck', 'kb', 'br', 'ro', 'ow', 'wn', + 'nf', 'fo', 'ox'] + >>> ngrams(sanitise('the quick brown fox'), 4) # doctest: +NORMALIZE_WHITESPACE + ['theq', 'hequ', 'equi', 'quic', 'uick', 'ickb', 'ckbr', 'kbro', 'brow', + 'rown', 'ownf', 'wnfo', 'nfox'] + """ + return [text[i:i+n] for i in range(len(text)-n+1)]
+ +def random_english_letter() +
+-
++
Generate a random letter based on English letter counts
+++Expand source code +
+
+def random_english_letter(): + """Generate a random letter based on English letter counts + """ + return weighted_choice(normalised_english_counts)
+ +def transpositions_of(keyword) +
+-
++
Finds the transpostions given by a keyword. For instance, the keyword +'clever' rearranges to 'celrv', so the first column (0) stays first, the +second column (1) moves to third, the third column (2) moves to second, +and so on.
+If passed a tuple, assume it's already a transposition and just return it.
+>>> transpositions_of('clever') +(0, 2, 1, 4, 3) +>>> transpositions_of('fred') +(3, 2, 0, 1) +>>> transpositions_of((3, 2, 0, 1)) +(3, 2, 0, 1) +
+++Expand source code +
+
+def transpositions_of(keyword): + """Finds the transpostions given by a keyword. For instance, the keyword + 'clever' rearranges to 'celrv', so the first column (0) stays first, the + second column (1) moves to third, the third column (2) moves to second, + and so on. + + If passed a tuple, assume it's already a transposition and just return it. + + >>> transpositions_of('clever') + (0, 2, 1, 4, 3) + >>> transpositions_of('fred') + (3, 2, 0, 1) + >>> transpositions_of((3, 2, 0, 1)) + (3, 2, 0, 1) + """ + if isinstance(keyword, tuple): + return keyword + else: + key = deduplicate(keyword) + transpositions = tuple(key.index(l) for l in sorted(key)) + return transpositions
+ +def weighted_choice(d) +
+-
++
Generate random item from a dictionary of item counts
+++Expand source code +
+
+def weighted_choice(d): + """Generate random item from a dictionary of item counts + """ + delems, dweights = list(zip(*d.items())) + return random.choices(delems, dweights)[0] + # target = random.uniform(0, sum(d.values())) + # cuml = 0.0 + # for (l, p) in d.items(): + # cuml += p + # if cuml > target: + # return l + # return None
+
Classes
+-
+
+class Pdist +(data=[], estimate_of_missing=None) +
+-
++
A probability distribution estimated from counts in datafile. +Values are stored and returned as log probabilities.
+++Expand source code +
+
+class Pdist(dict): + """A probability distribution estimated from counts in datafile. + Values are stored and returned as log probabilities. + """ + def __init__(self, data=[], estimate_of_missing=None): + data1, data2 = itertools.tee(data) + self.total = sum([d[1] for d in data1]) + for key, count in data2: + self[key] = log10(count / self.total) + self.estimate_of_missing = estimate_of_missing or (lambda k, N: 1./N) + def __missing__(self, key): + return self.estimate_of_missing(key, self.total)
Ancestors
+-
+
- builtins.dict +
+