How to Write a Spelling Corrector (2007)

https://github.com/grantjenks/python-wordsegment https://github.com/InstantDomain/instant-segment (rust)

I used the latter to process pdf plain text output quite successfully.

    import collections
    import math
    import heapq

    with open('count_1w.txt', 'r') as f:
        unigrams = [l.split() for l in f]
    unigram_map = collections.defaultdict(lambda: 0)
    for word, count in unigrams:
        unigram_map[word] = int(count)
    with open('count_2w.txt', 'r') as f:
        bigrams = [l.split() for l in f]
    bigram_map = collections.defaultdict(lambda: collections.defaultdict(lambda: {}))
    for word0, word1, count in bigrams:
        bigram_map[word0][word1] = int(count)
    log_p_unseen = collections.defaultdict(lambda: 0.)
    for word0, counts in bigram_map.items():
        for word1, count in counts.items():
            unigram_map[word1] += count
        total = sum(counts.values())
        #smoothing for unseen words
        mn, mx = min(counts.values()), max(counts.values())
        if mn == mx:
            p_unseen = 0.5
        else:
            #geometric series approximation
            r = (mn / mx) ** (1. / (len(counts) - 1))
            n = mn * r / (1. - r)
            p_unseen = n / (n + total)
        log_p_unseen[word0] = math.log(p_unseen)
        c = (1. - p_unseen) / total
        bigram_map[word0] = {word1: math.log(c * count) for word1, count in counts.items()}
    c = 1. / sum(unigram_map.values())
    unigram_map = {word: math.log(c * count) for word, count in unigram_map.items()}
    max_len = max(map(len, unigram_map))

    def optimal_parse(text):
        word_spans = {j: [] for j in range(len(text) + 1)}
        for i in range(len(text)):
            for j in range(i + 1, min(i + max_len, len(text)) + 1):
                if text[i:j] in unigram_map:
                    word_spans[i].append(j)
        min_cost = collections.defaultdict(lambda: float('inf'))
        parent = {}
        queue = [(0., 0, 0)]
        while queue:
            cost, i, j = heapq.heappop(queue)
            if cost > min_cost[(i, j)]:
                continue
            if j == len(text):
                break
            if j == 0:
                word0 = ''
            else:
                word0 = text[i:j]
            for k in word_spans[j]:
                word1 = text[j:k]
                if word1 in bigram_map[word0]:
                    word1_cost = -bigram_map[word0][word1]
                else:
                    #It would technically be more correct to normalize the unigram probability only over unseen words.
                    word1_cost = -(log_p_unseen[word0] + unigram_map[word1])
                cost1 = cost + word1_cost
                if cost1