查找缺少字母的单词的良好算法和数据结构？

Question

因此，我需要编写一种有效的算法来查找字典中缺少字母的单词，并且需要一组可能的单词。

例如，如果我有这个，我可能会找回这些主题主题等等。

我想知道是否有人可以建议我应该使用的某些数据结构或算法。

谢谢！

编辑：特里太太空间不足，并且会使其太慢。还有其他想法修改吗？

更新：最多会有两个问号，当两个问号确实出现时，它们将依次出现。

目前，我使用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左右。

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

谢谢！

Answer 1

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

解决方案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学术搜索搜索近似的字符串匹配 -足以阅读该主题。