更快速地查看另一个字符串中是否包含大量字符串

Question

我有一个存储在数组中的大约300k常用字的列表.所以,数组的1个元素= 1个单词.

另一方面,我有一个巨大的字符串列表,其中可能包含其中一个或多个300k字.示例字符串将是:ifdxawesome453.

现在,我需要针对常用词检查每个长字符串.如果在该字符串中找到单词,则立即返回.所以,我需要再次检查300k字ifdxawesome453,看看它们中是否包含任何字.

所以我做的是:

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

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

有没有办法更快地做到这一点？我想到的唯一方法就是如果我抽样出来,说这些300k中最常见的10k字,并先与它进行比较,如果找不到匹配,则与完整列表进行比较.

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

Answer 1

解

Trie结构是朝着正确方向迈出的一步.SuffixTree也许会有所帮助.

看起来Triezgem有比Triegem更多的功能,但文档远未完成.: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它是如何运作的,它的目的是什么.它似乎确实适合您的目的!¯\ _(ツ)_ /¯

Answer 2

在这个特定用例中，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)

一般来说，对于 Op 的用例来说，Triez 更快。

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的更新基准，其中带有前缀的行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