良好的algorithm和数据结构查找丢失字母的单词？

所以我需要编写一个有效的algorithm来查找字典中缺less字母的单词，并且我想要一组可能的单词。

例如，如果我有这个，我可能会回到这些，这些，主题，there.etc。

我想知道是否有人可以build议一些数据结构或我应该使用的algorithm。

谢谢！

编辑：一个Trie太空间效率太低，会使它太慢。 任何其他的想法修改？

更新：最多有两个问号，当两个问号出现时，它们将按顺序出现。

目前，我使用3个哈希表来表示完全匹配，1个问号和2个问号。 给定一个字典我散列所有可能的单词。 例如，如果我有WORD这个词。 我散列了WORD，ORD，W？RD，WO？D，WOR？，？RD，W？D，WO？。 进入字典。 然后，我使用链接列表将链接链接在一起。 所以说hash（W？RD）= hash（STR？NG）= 17。hashtab（17）将指向WORD和WORD指向STRING，因为它是一个链表。

平均查找一个单词的时间大约是2e-6s。 我期望做的更好，最好是1e-9。

编辑：我没有再次看到这个问题，但它花了0.5秒3m条目插入，并花了4秒3m条目查找。

谢谢！

Answer 1

我相信在这种情况下，最好只使用一个平面文件，每个单词排成一行。 有了这个，你可以方便地使用正则expression式search的function，这是高度优化，可能会击败任何数据结构，你可以为自己devise这个问题。

解决scheme＃1：使用正则expression式

这是针对这个问题的Ruby代码：

def query(str, data) r = Regexp.new("^#{str.gsub("?", ".")}$") idx = 0 begin idx = data.index(r, idx) if idx yield data[idx, str.size] idx += str.size + 1 end end while idx end start_time = Time.now query("?r?te", File.read("wordlist.txt")) do |w| puts w end puts Time.now - start_time 

文件wordlist.txt包含45425个单词（可在此下载）。 程序的查询输出是：

 brute crate Crete grate irate prate write wrote 0.013689 

所以只需要37毫秒就可以读取整个文件并find所有匹配的文件。 对于各种查询模式，即使在Trie很慢的情况下，它也能很好地扩展：

查询????????????????e

 counterproductive indistinguishable microarchitecture microprogrammable 0.018681 

查询?h?a?r?c?l?

 theatricals 0.013608 

这对我来说看起来足够快。

解决scheme2：使用准备好的数据的正则expression式

如果你想走得更快，你可以将单词表拆分成包含相同长度单词的string，并根据查询长度search正确的单词列表。 用这个代码replace最后5行：

 def query_split(str, data) query(str, data[str.length]) do |w| yield w end end # prepare data data = Hash.new("") File.read("wordlist.txt").each_line do |w| data[w.length-1] += w end # use prepared data for query start_time = Time.now query_split("?r?te", data) do |w| puts w end puts Time.now - start_time 

构build数据结构现在需要大约0.4秒，但是所有的查询速度要快10倍左右（取决于具有这个长度的单词的数量）：

• ?r?te 0.001112秒
• ?h?a?r?c?l? 0.000852秒
• ????????????????e 0.000169秒

解决scheme＃3：一个大的哈希表（更新的要求）

由于您已经改变了您的需求，您可以轻松扩展您的想法，只使用一个包含所有预先计算结果的大散列表。 但是，不要自己解决冲突，而要依靠正确实施的哈希表的性能。

在这里我创build了一个大的散列表，其中每个可能的查询映射到其结果列表：

 def create_big_hash(data) h = Hash.new do |h,k| h[k] = Array.new end data.each_line do |l| w = l.strip # add all words with one ? w.length.times do |i| q = String.new(w) q[i] = "?" h[q].push w end # add all words with two ?? (w.length-1).times do |i| q = String.new(w) q[i, 2] = "??" h[q].push w end end h end # prepare data t = Time.new h = create_big_hash(File.read("wordlist.txt")) puts "#{Time.new - t} sec preparing data\n#{h.size} entries in big hash" # use prepared data for query t = Time.new h["?ood"].each do |w| puts w end puts (Time.new - t) 

输出是

 4.960255 sec preparing data 616745 entries in big hash food good hood mood wood 2.0e-05 

查询性能是O（1），它只是在哈希表中查找。 时间2.0e-05可能低于计时器的精度。 当运行1000次时，每个查询平均得到1.958e-6秒。 为了加快速度，我将切换到C ++，并使用Google Sparse Hash ，这非常有效，而且速度很快。

解决scheme4：真的很严重

以上所有的解决scheme都可以工作，并且应该足够用于许多用例。 如果你真的想要认真，并有很多的空闲时间，请阅读一些好的论文：

• 尝试近似string匹配 – 如果执行得很好，尝试可以有非常紧凑的内存要求（比字典本身less50％），并且速度非常快。
• Agrep – 快速近似模式匹配工具 – Agrep基于一种新的高效灵活的近似string匹配algorithm。
• Google Scholarsearch近似string匹配 – 绰绰有余阅读此主题。

Answer 2

鉴于目前的局限性：

• 将会有最多2个问号
• 当有两个问号时，它们一起出现
• 字典中有大约10万字，平均字长为6。

我有两个可行的解决scheme给你：

快速解决scheme：HASH

你可以用最多两个'？'来表示哪个键是你的单词，这些值是一个适合单词的列表。 这散列将有大约100,000 + 100,000 * 6 + 100,000 * 5 = 1,200,000条目（如果你有2个问号，你只需要find第一个地方…）。 每个条目可以保存一个单词列表，或者一个指向现有单词的指针列表。 如果您保存了一个指针列表，并且我们假设每个单词平均有不到20个单词与两个'？'匹配，那么额外的内存小于20 * 1,200,000 = 24,000,000。

如果每个指针大小是4个字节，则这里的存储器要求是（24,000,000 + 1,200,000）* 4字节= 100,800,000字节〜= 96兆字节。

总结这个解决scheme：

• 内存消耗：〜96 MB
• 每次search的时间：计算一个哈希函数，并跟随一个指针。 O（1）

注意：如果要使用较小大小的散列，则可以，但为了获得更好的性能，最好在每个条目而不是链接列表中保存一个平衡的search树。

精明的空间，但仍然非常快的解决scheme：TRIE变化

该解决scheme使用以下观察：

如果'？' 迹象是在词的结尾，特里将是一个很好的解决scheme。

在查特里的search将search这个词的长度，而对于最后几封信，DFS遍历将带来所有的结局。 速度非常快，而且非常了解内存。

因此，让我们使用这个观察，以build立一些像这​​样工作的东西。

你可以考虑词典中的每一个单词，就像一个以@结尾的单词（或者你的词典中不存在的任何其他符号）。 所以“空间”这个词就是“空间@”。 现在，如果你旋转每个单词，用'@'符号，你会得到以下内容：

 space@, pace@s, ace@sp, *ce@spa*, e@spac 

（没有@作为第一个字母）。

如果您将所有这些变体插入到TRIE中，您可以通过“旋转”您的单词，轻松地在单词的长度上find您正在寻找的单词。

例如：你想find所有符合'ce'的单词（其中一个是空格，另一个是分片）。 你build立这个词：s ?? ce @，并旋转它，以便？ 标志到底。 即'ce @ s ??'

所有的旋转变化都存在于树状结构中，特别是'ce @ spa'（用*标记）。 find开始之后 – 您需要以适当的长度遍历所有的延续，并保存它们。 然后，您需要再次旋转它们以使@是最后一个字母，walla – 您拥有所有正在查找的单词！

总结这个解决scheme：

• 内存消耗：对于每个单词，其所有旋转出现在特里。 内存大小的平均值* 6被保存在内存中。 特里的大小约为* 3（只是猜测…）内部保存的空间。 所以这个系统所需的总空间是6 * 3 * 100,000 = 180万字〜6.8兆字节。

• 每次search的时间：

  • 旋转字：O（字长）
  • 在trie中寻求开始：O（字长）
  • 遍历所有的结局：O（比赛数量）
  • 旋转结尾：O（答案的总长度）

  总结起来，速度非常快，取决于字长*小常数。

总结一下…

第二select具有很大的时间/空间复杂性，并且将是您使用的最佳select。 第二种解决scheme存在一些问题（在这种情况下，您可能需要使用第一种解决scheme）：

• 更复杂的实施。 我不确定是否有编程语言尝试内置的内置。 如果没有 – 这意味着你需要自己实现它…
• 不好扩展。 如果明天你决定，你需要在整个单词中传播你的问号，而不一定要连在一起，那么你需要努力思考如何使第二个解决scheme适合它。 在第一种解决scheme的情况下 – 这是很容易推广。

Answer 3

对我来说，这个问题听起来像是一个很好的Trie数据结构。 input整个字典到你的单词中，然后查找单词。 对于一个丢失的信件，你将不得不尝试所有的子尝试，这应该是相对容易做一个recursion的方法。

编辑 ：我刚才在Ruby中写了一个简单的实现： http : //gist.github.com/262667 。

Answer 4

定向非循环词图将是这个问题的完美数据结构。 它结合了一个trie的效率（trie可以被看作是DAWG的一个特例），但是空间效率要高得多。 典型的DAWG将占用带有单词的纯文本文件的大小。

列举符合特定条件的单词是简单的，并且与trie中的单词相同 – 必须以深度优先的方式遍历graphics。

Answer 5

安娜的第二个解决scheme是这一个灵感。

首先，将所有单词加载到内存中，并根据单词长度将字典划分为多个部分。

对于每一个长度，对这些单词做一个指针数组的副本。 对每个数组进行sorting，以便在按一定数量的字母旋转时按顺序显示string。 例如，假设五个字母的原始列表是[平面，苹果，空间，火车，快乐，堆栈，黑客]。 那么你的五个指针数组将是：

 rotated by 0 letters: [apple, hacks, happy, plane, space, stack, train] rotated by 1 letter: [hacks, happy, plane, space, apple, train, stack] rotated by 2 letters: [space, stack, train, plane, hacks, apple, happy] rotated by 3 letters: [space, stack, train, hacks, apple, plane, happy] rotated by 4 letters: [apple, plane, space, stack, train, hacks, happy] 

（而不是指针，你可以使用整数来标识单词，如果这样可以节省平台上的空间。）

要进行search，只需要询问您需要旋转多less图案，以便问号出现在最后。 然后你可以在适当的列表中进行二进制search。

如果你需要find匹配的ppy，你必须把它旋转2来制作ppy。 因此，查看按2个字母旋转的顺序排列的数组。 快速的二进制search发现“开心”是唯一的匹配。

如果你需要find这个比赛的话，那么你必须把它旋转4秒才能得到更好的结果。 所以看看数组4，二进制search发现没有匹配。

不pipe有多less个问号，只要它们全部出现在一起，这就起作用了。

除字典本身外，还需要空间：对于长度为N的字，这需要空间（长度为N的字数的N倍）指针或整数。

每次查询的时间 ：O（log n）其中n是适当长度的字数。

在Python中的实现：

 import bisect class Matcher: def __init__(self, words): # Sort the words into bins by length. bins = [] for w in words: while len(bins) <= len(w): bins.append([]) bins[len(w)].append(w) # Make n copies of each list, sorted by rotations. for n in range(len(bins)): bins[n] = [sorted(bins[n], key=lambda w: w[i:]+w[:i]) for i in range(n)] self.bins = bins def find(self, pattern): bins = self.bins if len(pattern) >= len(bins): return [] # Figure out which array to search. r = (pattern.rindex('?') + 1) % len(pattern) rpat = (pattern[r:] + pattern[:r]).rstrip('?') if '?' in rpat: raise ValueError("non-adjacent wildcards in pattern: " + repr(pattern)) a = bins[len(pattern)][r] # Binary-search the array. class RotatedArray: def __len__(self): return len(a) def __getitem__(self, i): word = a[i] return word[r:] + word[:r] ra = RotatedArray() start = bisect.bisect(ra, rpat) stop = bisect.bisect(ra, rpat[:-1] + chr(ord(rpat[-1]) + 1)) # Return the matches. return a[start:stop] words = open('/usr/share/dict/words', 'r').read().split() print "Building matcher..." m = Matcher(words) # takes 1-2 seconds, for me print "Done." print m.find("st??k") print m.find("ov???low") 

在我的计算机上，系统字典大小为909KB，除了存储字（指针是4字节）外，该程序还使用了大约3.2MB的内存。 对于这本词典，你可以用2个字节的整数来代替指针，因为每个长度less于2 ^16个字。

测量：在我的机器上， m.find("st??k")在0.000032秒内运行， m.find("ov???low")在0.000034秒内运行，而m.find("????????????????e")在0.000023秒内。

通过写二进制search，而不是使用class RotatedArray bisect库，我得到的前两个数字下降到0.000016秒：两倍的速度。 在C ++中实现这一点会使其更快。

Answer 6

首先，我们需要一种方法来将查询string与给定条目进行比较。 让我们假设一个使用正则expression式的函数： matches(query,trialstr) 。

一个O（n）algorithm就是简单地遍历每一个列表项（你的字典将被表示为程序中的一个列表），将每个列表项与你的查询string进行比较。

通过一些预先计算，您可以通过为每个字母构build一个额外的单词列表来改善大量查询，因此您的字典可能如下所示：

 wordsbyletter = { 'a' : ['aardvark', 'abacus', ... ], 'b' : ['bat', 'bar', ...], .... } 

但是，这将是有限的使用，特别是如果您的查询string以未知的字符开始。 所以，我们可以做得更好，注意一个特定的字母在哪里，生成：

 wordsmap = { 'a':{ 0:['aardvark', 'abacus'], 1:['bat','bar'] 2:['abacus']}, 'b':{ 0:['bat','bar'], 1:['abacus']}, .... } 

正如你所看到的，没有使用索引，你将最终大幅度增加所需的存储空间 – 特别是一个n字的词典和平均长度m将需要nm ²的存储空间。 然而，你现在可以很快地做好你的查询，从每一套可以匹配的所有单词。

最后的优化（你可以在幼稚的方法上使用蝙蝠）也是把所有相同长度的单词分成不同的商店，因为你总是知道这个单词有多长。

这个版本是O（ kx ），其中k是查询词中已知字母的数量， x = x （ n ）是在你的实现中查找长度为n的字典中单个项目的时间（通常是log n ）。

所以最后一个字典是这样的：

 allmap = { 3 : { 'a' : { 1 : ['ant','all'], 2 : ['bar','pat'] } 'b' : { 1 : ['bar','boy'], ... } 4 : { 'a' : { 1 : ['ante'], .... 

那么我们的algorithm就是：

 possiblewords = set() firsttime = True wordlen = len(query) for idx,letter in enumerate(query): if(letter is not '?'): matchesthisletter = set(allmap[wordlen][letter][idx]) if firsttime: possiblewords = matchesthisletter else: possiblewords &= matchesthisletter 

最后， possiblewords的字集将包含所有匹配的字母。

Answer 7

如果生成与模式相匹配的所有可能的单词（arate，arbte，arcte … zryte，zrzte），然后在字典的二叉树表示中查找它们，则平均性能特征为O（e ^ N1 * log（N2））其中N1是问号的数量，N2是字典的大小。 似乎对我来说足够了，但我相信有可能找出一个更好的algorithm。

编辑 ：如果你不止三个问号，请看看Phil H的回答和他的字母索引方法。

Answer 8

假设你有足够的内存，你可以build立一个巨大的散列图来提供恒定的答案。 这是python中的一个简单例子：

 from array import array all_words = open("english-words").read().split() big_map = {} def populate_map(word): for i in range(pow(2, len(word))): bin = _bin(i, len(word)) candidate = array('c', word) for j in range(len(word)): if bin[j] == "1": candidate[j] = "?" if candidate.tostring() in big_map: big_map[candidate.tostring()].add(word) else: big_map[candidate.tostring()] = set([word]) def _bin(x, width): return ''.join(str((x>>i)&1) for i in xrange(width-1,-1,-1)) def run(): for word in all_words: populate_map(word) run() >>> big_map["y??r"] set(['your', 'year']) >>> big_map["yo?r"] set(['your']) >>> big_map["?o?r"] set(['four', 'poor', 'door', 'your', 'hour']) 

Answer 9

你可以看看它是如何在aspell中完成的。 它提示拼写错误的单词的正确的单词的build议。

Answer 10

build立所有单词的哈希集合。 要find匹配项，请使用每个可能的字母组合来replace模式中的问号。 如果有两个问号，一个查询由26 ² = 676个快速，恒定期望的时间散列表查找组成。

 import itertools words = set(open("/usr/share/dict/words").read().split()) def query(pattern): i = pattern.index('?') j = pattern.rindex('?') + 1 for combo in itertools.product('abcdefghijklmnopqrstuvwxyz', repeat=ji): attempt = pattern[:i] + ''.join(combo) + pattern[j:] if attempt in words: print attempt 

这比我的其他答案使用更less的内存，但它增加了更多的问号指数慢。

Answer 11

如果80-90％的准确度是可以接受的，你可以用Peter Norvig的拼写检查器来pipe理。 实现小而优雅。

Answer 12

基于正则expression式的解决scheme将考虑您的字典中的每个可能的值。 如果性能是你最大的约束，那么可以build立一个索引来加速它的速度。

您可以从每个字长的索引开始，包含每个索引的索引=匹配字集的字符。 例如，对于长度为5的单词，例如， 2=r : {write, wrote, drate, arete, arite}, 3=o : {wrote, float, group}等。为了得到原始查询的可能匹配，在这种情况下，单词集合将被相交，导致{wrote, group} 。

这是假设唯一的通配符将是一个单一的字符，字长是事先知道的。 如果这些都不是有效的假设，我可以推荐基于n-gram的文本匹配，如本文所讨论的。

Answer 13

你想要的数据结构被称为trie – 请参阅维基百科文章的简短摘要。

树是一个树形结构，树中的path构成了你想要编码的所有字的集合 – 每个节点最多可以有26个子元素，在下一个字符位置上可能有每个字母。 看维基百科文章中的图表，看看我的意思。

Answer 14

你有没有考虑过使用三元 search 树 ？ 查找速度可以与一个trie相提并论，但是它更节省空间。

我已经多次实现了这个数据结构，在大多数语言中这是一个相当简单的任务。

Answer 15

我的第一篇文章有​​一个错误，杰森发现，它不工作的时候？ 是在开始。 我现在借用了安娜的循环class次..

我的解决scheme：引入单词结尾字符（@）并将所有循环移位的单词存储在sorting的数组中！ 每个字长使用一个sorting数组。 当查找“th ?? e @”时，移动string以将？标记移动到末尾（获得e @ th ??）并选取包含长度为5的单词的数组，并对发生的第一个单词进行二进制search在string“e @ th”之后。 数组中所有剩余的单词匹配，即，我们将find“e @ thoo（thoose），e @ thes（these）等。

该解决scheme的时间复杂度为Log（N），其中N是字典的大小，它将数据大小扩大了6倍左右（平均字长）

Answer 16

以下是我该怎么做：

1. 将字典中的单词连接成一个由非单词字符分隔的长string。
2. 将所有单词放入一个TreeMap中，其中键是单词，值是大string中单词开头的偏移量。
3. findsearchstring的基础; 即最大的领先子string，不包括'?' 。
4. 使用TreeMap.higherKey(base)和TreeMap.lowerKey(next(base))来查找将在其中find匹配的string范围。 （ next方法需要计算下一个更大的单词到相同或更less字符的基本string，例如next("aa")是"ab" ， next("az")是"b" 。
5. 为searchstring创build一个正则expression式，并使用Matcher.find()来search与该范围对应的子string。

步骤1和2预先完成，使用O(NlogN)空间给出数据结构，其中N是单词的数量。

这种方法退化为一个蛮力正则expression式search整个字典时， '?' 出现在第一个位置，但是越往右边，需要完成的匹配越less。

编辑 ：

在'?'情况下提高性能 是第一个字符，创build一个辅助查找表，logging第二个字符为“a”，“b”等单词的开始/结束偏移量。 这可以用在第一个非'？' 是第二个字符。 你可以用类似的方法处理第一个非“？” 是第三个字符，第四个字符等等，但是最终会有越来越多的越来越小的运行，最终这个“优化”变得无效。

另外一种需要更多空间的方法，但在大多数情况下要快得多，就是为字典中的单词的所有旋转准备上面的字典数据结构。 例如，第一次旋转将包括所有单词2个字符或更多，单词的第一个字符移动到单词的末尾。 第二次旋转将是3个字符或更多的单词，前两个字符移动到末尾，依此类推。 然后做search，寻找最长的序列非'？' searchstring中的字符。 如果此子string的第一个字符的索引为N ，则使用第Nth旋转查找范围，并在第N个旋转字词列表中search。

Answer 17

懒惰的解决scheme是让SQLite或其他DBMS为您完成这项工作。

只要创build一个内存数据库，加载你的文字并使用LIKE运算符运行一个select。

Answer 18

摘要：使用两个紧凑的二进制search索引（其中一个词）和一个反向词。 空间成本是指标的2N指针; 几乎所有的查询都非常快; 最坏的情况下，“?? e”，仍然是体面的。 如果你为每个单词长度分别制作表格，那么最糟糕的情况是非常快的。

详细信息： Stephen C.发表了一个好主意 ：search一个有序的词典来查找模式可以出现的范围。 但是，当模式以通配符开始时，这并没有帮助。 你也可以按字长索引，但是这里有另一个想法：在反转的字典单词上添加一个有序索引; 那么一个模式总是在正向指数或反向词指数中产生一个小范围（因为我们被告知没有像ABCD这样的模式）。 单词本身只需存储一次，两个结构的条目都指向相同的单词，查找过程可以正向或反向查看; 但要使用Python的内置二进制searchfunction，我已经做了两个单独的string数组，而不是浪费一些空间。 （我正在使用sorting的数组而不是像其他人所build议的那样使用树，因为它节省了空间，而且速度至less一样快）。

代码 ：

 import bisect, re def forward(string): return string def reverse(string): return string[::-1] index_forward = sorted(line.rstrip('\n') for line in open('/usr/share/dict/words')) index_reverse = sorted(map(reverse, index_forward)) def lookup(pattern): "Return a list of the dictionary words that match pattern." if reverse(pattern).find('?') <= pattern.find('?'): key, index, fixup = pattern, index_forward, forward else: key, index, fixup = reverse(pattern), index_reverse, reverse assert all(c.isalpha() or c == '?' for c in pattern) lo = bisect.bisect_left(index, key.replace('?', 'A')) hi = bisect.bisect_right(index, key.replace('?', 'z')) r = re.compile(pattern.replace('?', '.') + '$') return filter(r.match, (fixup(index[i]) for i in range(lo, hi))) 

Tests: (The code also works for patterns like ?AB?D?, though without the speed guarantee.)

 >>> lookup('hello') ['hello'] >>> lookup('??llo') ['callo', 'cello', 'hello', 'uhllo', 'Rollo', 'hollo', 'nullo'] >>> lookup('hel??') ['helio', 'helix', 'hello', 'helly', 'heloe', 'helve'] >>> lookup('he?l') ['heal', 'heel', 'hell', 'heml', 'herl'] >>> lookup('hx?l') [] 

Efficiency: This needs 2N pointers plus the space needed to store the dictionary-word text (in the tuned version). The worst-case time comes on the pattern '??e' which looks at 44062 candidates in my 235k-word /usr/share/dict/words; but almost all queries are much faster, like 'h??lo' looking at 190, and indexing first on word-length would reduce '??e' almost to nothing if we need to. Each candidate-check goes faster than the hashtable lookups others have suggested.

This resembles the rotations-index solution, which avoids all false match candidates at the cost of needing about 10N pointers instead of 2N (supposing an average word-length of about 10, as in my /usr/share/dict/words).

You could do a single binary search per lookup, instead of two, using a custom search function that searches for both low-bound and high-bound together (so the shared part of the search isn't repeated).

Answer 19

If you only have ? wildcards, no * wildcards that match a variable number of characters, you could try this: For each character index, build a dictionary from characters to sets of words. ie if the words are write, wrote, drate, arete, arite , your dictionary structure would look like this:

 Character Index 0: 'a' -> {"arete", "arite"} 'd' -> {"drate"} 'w' -> {"write", "wrote"} Character Index 1: 'r' -> {"write", "wrote", "drate", "arete", "arite"} Character Index 2: 'a' -> {"drate"} 'e' -> {"arete"} 'i' -> {"write", "arite"} 'o' -> {"wrote"} ... 

If you want to look up a?i?? you would take the set that corresponds to character index 0 => 'a' {"arete", "arite"} and the set that corresponds to character index 2 = 'i' => {"write", "arite"} and take the set intersection.

Answer 20

If you seriously want something on the order of a billion searches per second (though i can't dream why anyone outside of someone making the next grand-master scrabble AI or something for a huge web service would want that fast), i recommend utilizing threading to spawn [number of cores on your machine] threads + a master thread that delegates work to all of those threads. Then apply the best solution you have found so far and hope you don't run out of memory.

An idea i had is that you can speed up some cases by preparing sliced down dictionaries by letter then if you know the first letter of the selection you can resort to looking in a much smaller haystack.

Another thought I had was that you were trying to brute-force something — perhaps build a DB or list or something for scrabble?