我有一个存储在数组中的大约 300k 常用单词的列表。因此，数组的 1 个元素 = 1 个单词。

另一方面，我有一个巨大的字符串列表，其中可能包含这 300k 个单词中的一个或多个。示例字符串为：ifdxawesome453.

现在，我需要根据常用单词检查每个长字符串。如果在该字符串中找到单词，则立即返回。所以，我需要再次检查一下这300k字ifdxawesome453并查看其中是否包含其中的任何一个。

所以我要做的是：

huge_list_of_words.any? do |word|
  random_long_word.include?(word)
end

虽然这对于随机长单词的小样本来说是可以的，但如果我有数百万个单词，突然需要几个小时才能完成这项工作。

有没有办法更快地做到这一点？我想到的唯一方法是，如果我抽样，从这 300k 中说出 10k 最常见的单词，然后首先与它进行比较，如果没有找到匹配项，则与完整列表进行比较。

另一种大幅加快速度的方法是按大小对 300k 单词的数组进行分组。然后，当我将长随机单词与它进行比较时，我首先检查单词的大小并过滤掉任何较长的单词。然后，我留下相同大小或更少单词的索引，并从大小最小的单词开始搜索它们。

Solution

Trie https://en.wikipedia.org/wiki/Trie结构是朝着正确方向迈出的一步。SuffixTree https://en.wikipedia.org/wiki/Suffix_tree也可能有帮助。

看起来像Triez gem https://github.com/luikore/triez具有比Trie gem https://github.com/tyler/trie，但文档还远未完成。:substring听起来很完美，但似乎你只能用它change_all :

# gem install triez
require 'triez'

huge_list_of_words = Triez.new value_type: :object, default: nil

%w(awesome someword anotherword).each do |word|
  huge_list_of_words[word] = word
end

class String
  def contains_word_from_dict?(dict)
    dict.change_all(:substring, self) do |v|
      return v if v
    end
    nil
  end
end

'ifdxawesome45someword3'.contains_word_from_dict?(huge_list_of_words)
# => "awesome"
'ifdxawsome45someword3'.contains_word_from_dict?(huge_list_of_words)
# => "someword"
'ifdxawsome45sameword3'.contains_word_from_dict?(huge_list_of_words)
# => nil

Test

我尝试使用更大的字典（~100k 单词）和一百万次查找：

huge_list_of_words = Triez.new value_type: :object, default: nil

dict = '/usr/share/dict/american-english'
File.foreach(dict) do |word|
  word.chomp!
  huge_list_of_words[word] = word if word.size > 4 # avoid finding `if` or `word`
end

1_000_000.times do
  'ifdxawesome45someword3'.contains_word_from_dict?(huge_list_of_words)
end

在我的速度较慢的笔记本电脑上，它在 22 秒后返回。

说实话，我不明白如何change_all有效，以及它的目的是什么。不过，它似乎确实可以很好地满足您的目的！ ˙\_(ツ)_/˙