更快速地查看另一个字符串中是否包含大量字符串
我有一个存储在数组中的大约300k常用字的列表。 所以，数组的1个元素= 1个单词。
另一方面，我有一个庞大的字符串列表，其中可能包含其中一个或多个300k字。 示例字符串将是： ifdxawesome453 。
现在，我需要针对常用词检查每个长字符串。 如果在该字符串中找到单词，则立即返回。 所以，我需要再次检查300k字ifdxawesome453并查看其中是否包含任何字。
所以我做的是：
huge_list_of_words.any? do |word| random_long_word.include?(word) end
虽然对于随机长词的小样本来说这是可以的，但如果我有数百万个，那么突然需要几个小时才能完成这项工作。
有没有办法更快地做到这一点？ 我想到的唯一方法就是如果我抽样出来，说这些300k中最常见的10k字，并先与它进行比较，如果找不到匹配，则与完整列表进行比较。
另一种大幅加速的方法是按大小对300k字的数组进行分组。 当我然后将长随机字与它进行比较时，我首先检查单词的大小是否过滤掉任何更长的单词。 然后我留下相同大小或更少单词的索引，并从具有最小大小的单词开始搜索它们。
在这个特定用例中Trie gem和Triez gem之间的基准：
word count: 228982 user system total real trie 13.410000 0.050000 13.460000 ( 13.463473) triez 11.080000 0.010000 11.090000 ( 11.102195) trie tail 39.920000 0.140000 40.060000 ( 40.102285) triez tail 28.960000 0.030000 28.990000 ( 29.022630)
一般来说，Triez在Op的使用案例中更快。
require 'triez' require 'trie' require 'benchmark' DICT = '/usr/share/dict/web2' triez = Triez.new value_type: :object, default: nil trie = Trie.new count = 0 File.foreach(DICT) do |word| word.chomp! if word.size > 4 triez[word] = word trie.add word count += 1 end end puts "word count: #{count}" def in_trie?(str, trie) 0.upto(str.length - 1) do |i| node = trie.root i.upto(str.length - 1) do |j| break unless node.walk! str[j] if node.terminal? return str[i..j] end end end nil end def in_triez?(str, triez) triez.change_all(:substring, str) do |v| return v if v end nil end Benchmark.bm(12) do |b| b.report('trie') do 1_000_000.times { in_trie?('ifdxawesome45someword3', trie) } end b.report('triez') do 1_000_000.times { in_triez?('ifdxawesome45someword3', triez) } end b.report('trie tail') do 1_000_000.times { in_trie?('ifdx45someword3awesome', trie) } end b.report('triez tail') do 1_000_000.times { in_triez?('ifdx45someword3awesome', triez) } end end
对rambling-trie的 UPDATE基准，其中带有c前缀的行是压缩版本。 （注意：前缀基准测试中ROUND已减少到100K而不是1M）
Word count: 228982, ROUND: 100000 user system total real trie 1.510000 0.000000 1.510000 ( 1.511772) triez 1.170000 0.000000 1.170000 ( 1.176075) rambling 4.800000 0.010000 4.810000 ( 4.847021) c rambling 25.060000 0.050000 25.110000 ( 25.172771) trie tail 4.540000 0.010000 4.550000 ( 4.566233) triez tail 3.080000 0.010000 3.090000 ( 3.092655) rambling tail 4.780000 0.010000 4.790000 ( 4.803114) c rambling tail 23.470000 0.020000 23.490000 ( 23.525066)
似乎rambling-trie纯粹是用Ruby实现的，它不提供直接的方法来进行前缀匹配。 首先需要添加以下猴子补丁。 可能有更好的实施，但我没有进一步挖掘。
class Rambling::Trie::Container def match_prefix?(str) root.match_prefix?(str.chars) end end class Rambling::Trie::RawNode def match_prefix?(chars, i = 0) if children_tree.empty? true elsif i >= chars.size false else letter = chars[i].to_sym child = children_tree[letter] !!child && child.match_prefix?(chars, i + 1) end end end class Rambling::Trie::CompressedNode def match_prefix?(chars) if children_tree.empty? true if chars.empty? false else !!(recursive_get :match_prefix?, chars) end end end def in_r_trie?(str, r_trie) 0.upto(str.length - 1) do |i| if r_trie.match_prefix? str[i..-1] return true end end false end
解
Trie结构是朝着正确方向迈出的一步。 SuffixTree也可以提供帮助。
看起来Triez gem比Trie gem有更多function，但文档远未完整。 :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
测试
我用一个更大的字典（~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是如何工作的，以及它的目的是什么。 它似乎确实适合您的目的！ ¯\ _（ツ）_ /¯
简洁的方法是为巨大的列表中的所有单词创建一个trie 。 然后你需要遍历所有长字符串。 对于特定字符串，请执行自定义迭代以开始在字符串中搜索字符串中的每个字母以匹配您的所有单词。 如果您只需要找到一个包含的单词以获得额外的速度，您可以提前终止。
对于trie部分，这里似乎有一个甜蜜的实现。 它甚至有一个例子，非常类似于你应该能够调整的用例。
word = 'forestry' node = trie.root word.split('').each do |char| break unless node.walk!(char) if node.terminal? puts "Found me a word: #{node.full_state}" end end