0
ユーザーが指定した文字を使用して可能なすべての単語を見つける必要があります。ユーザーは "？" - ワイルドカード（最大2つのワイルドカード）。最大入力は、これらのワイルドカードを含む15文字です。入力例： "abcdefghijklm ??"Trieでの単語検索の高速化
現在、私は2_700_000語をTrieに格納しています。私はそのようにそれを調べる：
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文字入力、1それは次のように記述することができない何
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
ワイルドカード：3,54秒 15文字入力、2ワイルドカード：15,59秒
オンラインでは1秒以下のタスクを行うスクラブルソルバーが多数あります。
質問 どのように処理を高速化するので、毎回1秒以下かかりますか？私は考えています： a）Cで検索方法を書いてください。 b）Trieを再編成して、アルファベット順にアルファベット順に並び替えられます（例：fast - > afst） - 検索回数を減らす 私は喜んで聞きますあなたがこの特定の仕事のためのよりよいアプローチを知っていたら。 c）Trieでハッシュテーブルを切り替える？