Count unigrams and bigrams in the Wolfart-Ahenakew corpus

$cree-grapheme-stats.md

Cree Grapheme Stats

Count unigrams and bigrams in the Wolfart-Ahenakew nêhiyawêwin corpus!

Why

When building a keyboard for typing Cree, it is useful to know which graphemes are typed often, and which pairs of graphemes are typed one after the other. Using unigram statistics, we can place the most frequent graphemes in the most ergonomic "neutral" positions. To speed up typing, we place frequently typed pairs on opposite sides of the keyboard, optimizing for two-handed typing with to maximize alternating hands/thumbs.

Requirements

• Python 3.6+
• sponge(1) from moreutils (brew install moreutils)
• nfc(1) from unormalize (brew install eddieantonio/eddieantonio/unormalize)

Files

.
├── Makefile
├── bigrams.pdf         [output]
├── bigrams.tsv         [output]
├── cleancorp.txt       [input]
├── count-bigrams
├── count-unigrams
├── create-fdp
├── defuse
├── filter-out-non-sro
├── tokenize
└── unigrams.tsv        [output]

Note: You must download cleancorp.txt separately!

SHA256 sum:

2cb09a54b9c3cc329eba573b4798aa2d79b19f58b4f417a97150c9133c3b3343  cleancorp.txt

bigrams.tsv

count-bigrams

#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

import fileinput
from collections import Counter

bigrams = Counter()

for line in fileinput.input():
    line = line.strip()
    if len(line) <= 1:
        continue

    for a,b in zip(line, line[1:]):
        bigrams[a + b] += 1

print('bigram', 'count', sep='\t')
for bigram, count in bigrams.most_common():
    print(bigram, count, sep='\t')

count-unigrams

#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

import fileinput
from collections import Counter

unigrams = Counter()

for line in fileinput.input():
    line = line.strip()
    if len(line) < 1:
        continue
    unigrams.update(Counter(line))

print('unigram', 'count', sep='\t')
for unigram, count in unigrams.most_common():
    print(unigram, count, sep='\t')

create-fdp

#!/usr/bin/env python3
# -*- encoding: UTF-8 -*-

import fileinput
from math import log, sqrt


MAX_PENWIDTH = 6


print("graph {")
print("""
  node [shape=circle, splines=curved, fontsize=8];
  edge [len=49];
""")


max_count = None

# Skip header
lines = fileinput.input()
next(lines)

for line in lines:
    assert 'count' not in line
    bigram, count = line.strip().split()

    c1, c2 = bigram
    count = int(count)

    if max_count is None:
        max_count = count
    assert count <= max_count

    # Remove self-cycles; not useful here.
    if c1 == c2:
        print(f"  // ignoring {bigram}")
        continue

    weight = max_count + 1 - count
    factor = count / max_count
    logfactor = log(1 + factor)
    penwidth = MAX_PENWIDTH * factor
    alpha = int(255 * logfactor)
    assert 0 <= alpha <= 255
    print(f'  "{c1}" -- "{c2}" ['
          f"weight={weight},"
          f"penwidth={penwidth:.4f},"
          f'color="#000000{alpha:02X}"'
          f"]; // {factor}")

print("}")

defuse

#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

"""
Removes the BOM from a stdin.
"""

import sys

BYTE_ORDER_MARK = '\uFEFF'.encode('UTF-8')

data = sys.stdin.buffer.read()
print(data.replace(BYTE_ORDER_MARK, b'').decode('UTF-8'), end='')

filter-out-non-sro

#!/bin/sh
env LC_ALL=C.UTF-8 grep -o -E '^[ptkcsmnhywêiîoôaâlr-]+$' | grep -v '^---*$'

huff

#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

import sys


TYPE = 0
WEIGHT = 1
LEFT = 2
SYMBOL = 2
RIGHT = 3

unigrams = []

# Skip the header
lines = iter(sys.stdin)
next(lines)

for line in lines:
    symbol, count = line.strip().split()
    unigrams.append((symbol, int(count)))


def by_weight(t):
    return t[WEIGHT]


# Initially, the tree is comprised entirely of leaves.
huffman_tree = [('leaf', weight, symbol) for symbol, weight in unigrams]

# Reduce the tree by glomming on the lowest probability items iteratively.
while True:
    # Invariant: the tree is always sorted:
    huffman_tree.sort(key=by_weight, reverse=True)
    if len(huffman_tree) < 2:
        break

    # Group the items with the lowest probability.
    right = huffman_tree.pop()
    left = huffman_tree.pop()
    weight = by_weight(left) + by_weight(right)
    huffman_tree.append(('internal', weight, left, right))


# Now, traverse the tree to assign binary codes.
def assign_codes(root):
    return _assign_codes(root, ())


def _assign_codes(node, code):
    if node[TYPE] == 'internal':
        assert node[LEFT][WEIGHT] > node[RIGHT][WEIGHT]
        left = _assign_codes(node[LEFT], code + (1,))
        right = _assign_codes(node[RIGHT], code + (0,))
        return {**left, **right}
    else:
        assert node[TYPE] == 'leaf'
        return {node[SYMBOL]: code}


coding = assign_codes(huffman_tree[0])
table = sorted(coding.items(), key=lambda x: len(x[1]))

print('symbol', 'code', sep="\t")
for symbol, code in table:
    bits = ''.join(str(bit) for bit in code)
    print(symbol, bits, sep="\t")

huffman-coding.tsv

Makefile

# Requires nfc(1) from unormalize.
# Requires sponge(1) from moreutils

CORPUS = AWCleanCorp-FalseStarts.txt

all: bigrams.tsv unigrams.tsv wordlist.tsv huffman-coding.tsv

unigrams.tsv: tokens.txt count-unigrams
	<$< ./count-unigrams | sponge $@

bigrams.tsv: tokens.txt count-bigrams
	<$< ./count-bigrams | sponge $@

tokens.txt: $(CORPUS) defuse tokenize filter-out-non-sro
	<$< ./defuse | nfc | ./tokenize | ./filter-out-non-sro | sponge $@

bigrams.fdp.dot: bigrams.tsv create-fdp
	<$< ./create-fdp | sponge $@

wordlist.tsv: tokens.txt
	sort $< | uniq -c | sort -rn | awk '{ print $$2 "\t" $$1 }' | sponge $@

huffman-coding.tsv: unigrams.tsv huff
	<$< ./huff | sponge $@

%.pdf: %.fdp.dot
	fdp -Tpdf $< | sponge $@

syllabics.tsv

tokenize

#!/bin/sh
tr ' ' '\n'

unigrams.tsv