我相信在这种情况下，最好只使用一个平面文件，其中每个单词排成一行。使用此功能，您可以方便地使用正则表达式搜索的功能，该功能经过高度优化，可以击败您可以针对此问题设计的任何数据结构。

解决方案1：使用正则表达式

这是用于此问题的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个单词（可在此处下载）。该程序的查询输出为?r?te：

brute
crate
Crete
grate
irate
prate
write
wrote
0.013689

因此，只需花费37毫秒即可读取整个文件并在其中找到所有匹配项。即使在Trie非常慢的情况下，它也可以很好地扩展用于各种查询模式：

询问 ????????????????e

counterproductive
indistinguishable
microarchitecture
microprogrammable
0.018681

询问 ?h?a?r?c?l?

theatricals
0.013608

这对我来说足够快。

解决方案2：使用准备好的数据的正则表达式

如果您想走得更快，可以将单词表拆分为包含相等长度单词的字符串，然后根据您的查询长度搜索正确的单词。用此代码替换最后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

现在，建立数据结构大约需要0.4秒，但是所有查询的速度大约要快10倍（取决于该长度的单词数）：

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

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

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

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

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。

解决方案4：认真对待

以上所有解决方案都可以正常工作，并且对于许多用例都应该足够好。如果您真的想变得认真并且有很多空闲时间，请阅读一些好的文章：

• 近似字符串匹配的尝试 -如果实施得当，尝试可以具有非常紧凑的内存要求（比字典本身少50％的空间），而且速度非常快。
• Agrep-快速近似模式匹配工具 -Agrep基于一种新的高效灵活的算法，用于近似字符串匹配。
• Google学术搜索搜索近似的字符串匹配 -足以阅读该主题。