Generate readable English words from given letters

Question

I was redirected from StackOverflow to your community in hope to get some help and improve my script.

The script receives letters as input and generates possible words, then extracts readable words from comparing my list items with file containing English words.

For example when I enter as input : eys

this will generate a list like:

["esy", "eys", "sey", "sye", "yes", "yse"] and return the correct readable word "yes" as a final result.

The problem is when the length of input is greater than 8 characters it takes much time and I want to use Threading or Multiprocessing to reduce the latency.

My script

'''Create script that generate readable english words from given letters'''

from math import factorial
from itertools import permutations
from time import time, ctime
from threading import Thread
import multiprocessing as mp

class GetReadableWords:

    def __init__(self, letters):
        self.letters = letters

    def prob_words(self):
        
        self.comb = factorial(len(self.letters))
        print('Nomber of combinitions that we have is : ', self.comb)

        self.prob = [''.join(ltr) for ltr in permutations(self.letters)]
        return self.prob

    def chek_word(self):

        result = []

        for word in set(self.prob_words()):

            with open('corncob_lowercase.txt', 'r') as f:

                for line in f.readlines():
                    line = line.rstrip()

                    if word == line:
                        result.append(word)

                    else:
                        continue

                f.close()

        return result

    '''def run(self):
        with mp.Pool() as pool:
            pool.map(self.chek_word(), self.prob, chunksize=1)'''


if __name__ == "__main__":

    user_input = input('Enter your random characters : ')
    
    sart_time = time()
    print("starting time at : ", ctime(sart_time).split(' ')[3])

    c = GetReadableWords(user_input)
'''
    threads = []
    for word in c.prob_words():
        p = mp.Process(target=c.chek_word(), args=(word,))
        threads.append(p)
        p.start()

    for job in jobs:
        job.join()
'''
    #print(c.run())
    print(c.chek_word())
    end_time = time()
    print("ending time at : ", ctime(end_time).split(' ')[3])

    elaps_t = (end_time - sart_time)
    print("time taken is : %.2f sec" % elaps_t)

Answer 1

Algorithm

The problem here is that your algorithm isn't scalable. For any given n-letter word, prob_words() generates n! candidate words. That's 40320 candidates for an 8-letter input.

To compound your performance problem, check_word() opens and scans the word list file once for each candidate word. Since the entire word list should fit quite comfortably memory on any general-purpose computer these days, you should read the word list just once.

So, forget about multithreading or multiprocessing. Work smarter, not harder! If you want to determine whether two words are anagrams of each other, all you need is to count or sort the letters. You don't need to generate a combinatoric explosion.

Design

GetReadableWords is not a well designed class. A good hint that the design is wrong is that classses (and objects) should be named like a noun, not a verb phrase. A second hint that you've gone wrong is that letters is really an input for just prob_words(), and not so much for chek_words().

In addition, neither prob_words() nor chek_words() is a good method name. Those names make no sense to me.

There is way too much code under if __name__ == "__main__". If you have that much code, then you should put it in a main() function and call it.

Suggested solution

'''Generate English words from given letters'''

class AnagramWordFinder:
    def __init__(self, word_list_filename='corncob_lowercase.txt'):
        self.vocab = {}
        with open(word_list_filename) as f:
            for line in f:
                word = line.rstrip()
                self.vocab.setdefault(''.join(sorted(word)), []).append(word)

    def words_from_letters(self, letters):
        return self.vocab.get(''.join(sorted(letters)), [])

def main():
    word_finder = AnagramWordFinder()
    print(word_finder.words_from_letters(input('Enter your characters: ')))

if __name__ == '__main__':
    main()

Arguably, you don't even need a class, especially if you only need to ask for input only once.

def unscramble_letters(letters, word_list_filename='corncob_lowercase.txt'):
    letters = ''.join(sorted(letters))
    with open(word_list_filename) as f:
        for line in f:
            if ''.join(sorted(line.rstrip())) == letters:
                yield line.rstrip()

if __name__ == '__main__':
    print(list(unscramble_letters(input('Enter your characters: '))))

Answer 2

Anagram lookup:

Unless capitalization is important, fold everything to, say, lowercase.

1. Prep the list of valid rows by building a hash (associative array) mapping sorted letters to the word.
2. When you have a set of letters, sort those letters, too.
3. Then do a hashed lookup of step 2 in the array of step 1.

Step 1 might produce, for example:

amp => amp
amp => map
oot => too