Python scripts that generate valid ngrams for use in pseudoword generation

Question

These are the scripts I wrote to generate valid ngrams, the output will be filtered manually then used in Markov chain style pseudoword generation.

You will need PowerShell 7 and gcide_xml to make these scripts work.

I wanted to find an English corpus/dictionary library for Python, and didn't find one with enough number of words, but I found gcide instead.

The xml files in are broken, at least I can't view them in Firefox, though I found the entries can be extracted using this regex: (?<=<ent>)(\w*)(?=</ent>).

The entries are in 26 xml files with names match gcide_\w\.xml, I don't like the idea of using os.walk() with for loop to get the needed files, then opening reading processing and closing these 26 files in another for loop, so I used a PowerShell one-liner to get the job done, though if there is a Python library that can do this in one-loop I'd happily use that instead of PowerShell.

The entries may contain duplicates (homographs), invalid words (acronyms, especially ones with only consonants, words starting with numbers, roman numerals and other nonsense), and most entries are in Titlecase, while some are in lowercase, and the roman numerals are always in lowercase, so I preprocessed the entries.

I then used two other scripts to generate a list of potential candidates and pre-eliminated some.

Then I used another script to count the occurrences of each candidates in the entries (how many words in the list of words contain the candidates) to further eliminate invalid ngrams.

I then used another script to pull the ngrams directly from the words

By order of execution and importation, the scripts are:

getdict.py

import re
from itertools import chain
from pathlib import Path
from string import ascii_lowercase

folder = Path(r'D:\corpus\gcide_xml-0.51').rglob('*')
xml_files = [i for i in folder if re.search('gcide_\w.xml', str(i))]

words = [re.findall("(?<=<ent>)(\w*)(?=</ent>)", i.read_text()) for i in xml_files]
words = sorted(set(chain(*words)))

LETTERS = set(ascii_lowercase)
VOWELS = set('aeiouy')
CONSONANTS = LETTERS - VOWELS

words = [i for i in words if not re.match('^[cdilmvx]+$', i) and not re.search('\d', i)]
words = set(i.lower() for i in words)
words = [i for i in words if not set(i).issubset(CONSONANTS)]
words = sorted(words)

Path('D:/corpus/gcide_dict.txt').write_text('\n'.join(words))

validngrams.py

import json
import re
from collections import Counter
from collections import defaultdict
from pathlib import Path

def process(obj):
    obj = obj.most_common()
    obj = [(k, v) for k, v in obj if v >= 20]
    return dict(sorted(obj, key=lambda x: (-x[1], x[0])))

words = Path('D:/corpus/gcide_dict.txt').read_text().splitlines()
cngrams = Counter()
for w in words:
    slices = set()
    for i in range(1, len(w) + 1):
        for j in range(i):
            slices.update(re.findall('\w{%s}' % i, w[j:]))
    for k in slices:
        cngrams[k] += 1

cngrams = process(cngrams)
validngrams = defaultdict(lambda: defaultdict(dict))
for k, v in cngrams.items():
    validngrams[k[0]]['%sgrams' % len(k)].update({k: v})

validngrams = {k: v for k, v in sorted(validngrams.items())}

Path('D:/corpus/validngrams.json').write_text(json.dumps(validngrams, indent=4))

I want to ask about possible improvements on code style, structure, and performance, especially performance of the last script, it took about 20 minutes on my machine with Intel Core i5-4430 on PtIpython to get the count of occurrences of each candidate, I have tried list comprehension and of course nested for loops to achieve this, but none of them are much more performant than the map() method, and of course I have Google searched for a better method, and found nothing better than list comprehension.

How can the formatting, code style, structure, readability and most importantly, performance of my scripts be improved?

The last script desperately needs boost in performance. What are some libraries that can make the process of finding how many strings in list A contain a string from list B for each string in list B significantly faster?

---

Update:

Uploaded gcide_dict.txt to Google Drive as per request.

And I have found a faster way to get the count of ngrams, and updated the code.

In my testing, the map() way:

validngrams = list(map(lambda x: (sum(x in i for i in words), x), ngrams))

Takes a grand total of 1395 seconds on my machine:

In [82]: %time validngrams = list(map(lambda x: (sum(x in i for i in words), x), ngrams))
Wall time: 23min 15s

Whereas the Counter() way takes only 1040 seconds:

In [48]: %time validngrams = Counter(i for i in ngrams for j in words if i in j)
Wall time: 17min 20s

It saves 355 seconds, and is 25.45 percent faster.

Though I am still looking for a way to make it down to about 12 minutes.

---

Update:

Found a Python 3 way to get the absolute paths of all files inside a directory and its subdirectories, without using os.walk(), the dinosaur from Python 2.

Using pathlib, listing files recursively can be done in simply by the .rglob() method of Path() class, instead of using a for loop like os.walk().

And with pathlib, reading the contents of multiple files can be simply done by loop through their Paths and call the read_text() method, instead of multiple with open() blocks.

The updated code eliminated the need of PowerShell and is tremendously faster than PowerShell, I edited the corresponding code above.

---

Update

I was thinking, instead of generating possible ngrams and verifying them, I could just directly get the ngrams from the words themselves by splitting the words using regex, and since re.findall() does not find combinations that whose index of first letter modulo the length of the combination is not zero, I used steps to find all combinations.

And then, because there might be duplicates, I used a set to eliminate the duplicates.

And of course, the results contain combinations that are unpronounceable by themselves and require linguistical analysis to filter out invalid ones, but the job of finding them is done.

And this approach is tremendously faster than the last one, it only takes about 9 seconds on PtIpython.

Answer 1

document parts of a program

It's good to document things in general, but it's especially important to document a data pipeline consisting of several process steps. Clearly label what each file is, and what each program takes in and outputs. For example:

gcide/*.xml: An english dictionary of words, in XML format. One file per dictionary letter.
getdict.py: Takes in the gcide english dictionary as multiple XML files (gcide/*.xml). Outputs a list of legitimate-looking words (gcide_dict.txt).
gcide_dict.txt: An english dictionary, one word per line in sorted order.
validngrams.py: Takes in a wordlist (gcide_dict.txt). Outputs n-grams found in that dictionary as JSON (validngrams.json). 
validngrams.json: Ngram data, as JSON. The JSON dictionary maps each ngram found to a count.

Recommended pipeline:
   Download GCIDE_XML to D:\corpus\gcide_xml-0.51
   Run python getdict.py
   Run python validngrams.py
   The output will be in D:/corpus/validngrams.json

I couldn't figure out what a "valid" vs an "invalid" ngram. I think a "valid" ngram is one that appears at least 20 times?

Your JSON format is a 4-layer nested dictionary: first letter -> #grams -> ngram -> count. Document this and give a few sample lines. A more natural format (at least it seems to me) is #grams -> ngram -> count. Also, it's useful to add total counts, so you can calculate frequency. Because you omit low-frequency 2-grams, the sum of all 2-gram counts beginning with "A" is not the same as the 1-gram count for "A".

misunderstanding ngrams

An n-gram is a series of characters that appears in an english text, typically with a frequency/count. For example, you could have a table of 2-grams: the frequency with which every pair of characters appears in English text.

I'm not sure it's best to mix together 1-grams, 2-grams, 3-grams and so on into a huge list. I'd probably write them to separate files. You most likely only want to use one at a time when you're using them anyway.

It probably makes no sense to use a wordlist as your corpus--this won't let you generate anything realistic-looking. You need the frequency data. You want to know that "the" is very common, and you may want spaces in your input. That said, go ahead and play around with the wordlist if you like.

Also you want some pre-calculated, Google produced some with its million books project as the corpus, which I think are relatively good.

performance

I couldn't test getdict.py, but for me validngrams.py takes about 10 seconds to run on /usr/share/dict/words (wikipedia links an example wordlist).

I'm not sure what you were doing before, but that seems fast enough to me now. It's best practice on Code Review not to update your program before it's reviewed--adding update notes is a little better, but not much. If you want to improve this further, I'd start by identifying which sections are slow. You're using %time which is a good sign.