加快 Trie 中的单词搜索

Question

我需要找到所有可以使用用户指定的字母组成的单词。用户可以使用“？” - 作为通配符（最多 2 个通配符）。最大输入为 15 个字符，包括那些通配符。输入示例："abcdefghijklm??".

目前我有 2_700_000 个单词存储在 Trie 中。我是这样查的：

def search_word(node, wildcards, alphabet, tiles, output) 

  output.push(node.full_state) if node.terminal? # append output if its a word
  unless tiles.empty? && wildcards.zero?
    tiles.uniq.each do |tile|
      unless node.walk(tile).nil?  # choose only those letters that could possibly make a word
        next_node = node.walk(tile)
        remaining_tiles = take_away(tiles, tile)
        search_word(next_node, wildcards, alphabet, remaining_tiles, output) 
      end
    end
  end

  if wildcards > 0
    other_letters = take_away(alphabet, tiles.uniq)  # letters that weren't used in previous loop
    other_letters.each do |tile|
      unless node.walk(tile).nil? # only those that could make a word
        next_node = node.walk(tile)
        remaining_tiles = take_away(tiles, tile)
        remaining_wildcards = wildcards - 1
        search_word(next_node, remaining_wildcards, alphabet, tiles, output) 
      end
    end
  end

end

它的作用可以描述为：

def searchword(trie, wildcards, tiles, output):
    if trie is word:
        output.append(trie.word) # or send current letters as arguments to this function

    for each unique tile in tiles:
        if trie has tile:
            searchword(trie[tile], wildcards, (tiles - tile), output)

    if wildcards > 0:
        for each key in trie that has not already been searched in previous loop:
            searchword(trie[key], (wildcards - 1), tiles, output)

速度测试： 15 个字母输入，无通配符：0.45 秒 15 个字母输入，一个通配符：3,54 秒 15个字母输入，两个通配符：15,59s

网上有很多拼字游戏求解器，可以在 1 秒内完成此类任务。

问题如何加快这个过程，让我每次花费不到 1 秒？我正在考虑： a) 用 C 编写搜索方法 b) 重新组织 Trie，以便单词按字母顺序存储（例如 fast -> afst）——这将减少搜索次数如果您知道完成此特定任务的更好方法，我愿意倾听。 c) 将我的 Trie 切换为哈希 table?

Answer 1

您应该选择选项 b，按字母顺序存储所有字谜。不重温信件是一个巨大的胜利。

除非不按字母顺序排序。按以下顺序对字母进行排序：etaoinshrdlcumwfgypbvkjxqz。从最频繁到最不频繁。这个想法是只看最常见的字母最少次数，而不是一遍又一遍。

加快 Trie 中的单词搜索

Speeding up word search in a Trie

ruby

algorithm

search

trie