StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>A few approaches occur to me;</p> <p>The first is to preprocess your dictionary into words[wordlength][offset][charAtOffset] = set(matching words); then your query becomes an intersection of all relevant word-sets. Very fast, but memory-intensive and a lot of set-up work.</p> <p>Ex:</p> <pre><code># search for 'r-n' matches = list(words[3][0]['r'] & words[3][2]['n']) </code></pre> <p>The second is a linear scan of the dictionary using regular expressions; much slower, but minimal memory footprint.</p> <p>Ex:</p> <pre><code>import re foundMatch = re.compile('r.n').match matches = [word for word in allWords if foundMatch(word)] </code></pre> <p>Third would be a recursive search into a word-Trie;</p> <p>Fourth - and it sounds like what you want - is a naive word-matcher:</p> <pre><code>with open('dictionary.txt') as inf: all_words = [word.strip().lower() for word in inf] # one word per line find_word = 'r-tt-r' matching_words = [] for word in all_words: if len(word)==len(find_word): if all(find==ch or find=='-' for find,ch in zip(find_word, word)): matching_words.append(word) </code></pre> <p><strong>Edit</strong>: full code for the first option follows:</p> <pre><code>from collections import defaultdict import operator try: inp = raw_input # Python 2.x except NameError: inp = input # Python 3.x class Words(object): @classmethod def fromFile(cls, fname): with open(fname) as inf: return cls(inf) def __init__(self, words=None): super(Words,self).__init__() self.words = set() self.index = defaultdict(lambda: defaultdict(lambda: defaultdict(set))) _addword = self.addWord for word in words: _addword(word.strip().lower()) def addWord(self, word): self.words.add(word) _ind = self.index[len(word)] for ind,ch in enumerate(word): _ind[ind][ch].add(word) def findAll(self, pattern): pattern = pattern.strip().lower() _ind = self.index[len(pattern)] return reduce(operator.__and__, (_ind[ind][ch] for ind,ch in enumerate(pattern) if ch!='-'), self.words) def main(): print('Loading dict... ') words = Words.fromFile('dict.txt') print('done.') while True: seek = inp('Enter partial word ("-" is wildcard, nothing to exit): ').strip() if seek: print("Matching words: "+' '.join(words.findAll(seek))+'\n') else: break if __name__=="__main__": main() </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload