如何根据 Ruby 中的单词列表有效地检查文本？

Question

给定 1,000 个单词的文本，检查 10,000 个单词的字典的有效方法是什么？我想计算非唯一匹配项的数量。

一个想法是将字典存储为散列。但随后我将不得不根据散列检查每个单词，这将是 1,000 次操作。这似乎效率不高。

另一个想法是 Postgres 文本搜索。但是是否可以在一个查询中进行此检查？

另一个想法是将单词存储在 Memcache 或 Redis 数据库中，但这将需要 1,000 次查询并且非常慢。

那么，有没有更高效的解决方案呢？

在Ruby工作。

编辑：为 :

添加基准

Cary 关于 dict_set 更快的断言是正确的：

aw.length
=> 250
dw.length
=> 1233
dict_set.length
=> 1223
t = Time.now; 1000.times{ aw & dw }; Time.now - t
=> 0.682465
t = Time.now; 1000.times{ aw.count{ |w| dict_set.include? w }}; Time.now - t
=> 0.063375

所以，Set#include? 看起来很有效率。

Answer 1

假设：

text = "The quick brown fox and the quick brown bear jumped over the lazy dog"

和

dictionary = ["dog", "lazy", "quick", "sloth", "the"]

我们先把dictionary转换成一个集合：

require 'set'
dict_set = dictionary.to_set
  #=> #<Set: {"dog", "lazy", "quick", "sloth", "the"}>

并将text转换为一个小写单词数组：

words = text.downcase.split
  #=> ["the", "quick", "brown", "fox", "the", "and", "quick",
  #    "brown", "bear", "jumped", "over", "the", "lazy", "dog"]

这里有几种计算 text 和 dictionary.

中单词数量的方法

#1：简单算一下

words.count { |w| dict_set.include?(w) }
  #=> 7

#2：将相同的单词分组并计数

words.group_by(&:itself).reduce(0) { |tot,(k,v)|
  tot + ((dict_set.include?(k)) ? v.size : 0) }  
  #=> 7

Object#itself 是在 v2.2 中引入的。对于早期版本，替换：

group_by(&:itself)

和

group_by { |w| w }

步骤：

h = words.group_by(&:itself)
  #=> {"the"  =>["the", "the", "the"],
  #    "quick"=>["quick", "quick"],
  #    "brown"=>["brown", "brown"],
  #    "fox"=>["fox"],
  #    ...
  #    "dog"=>["dog"]} 
h.reduce(0) { |tot,(k,v)| tot + ((dict_set.include?(k)) ? v.size : 0) }
  #=> 7}

考虑到 Set#include? 非常快，我预计 #1 通常是最快的。也就是说，我怀疑将相同单词分组的时间是否少于字典查找所节省的时间。

如何根据 Ruby 中的单词列表有效地检查文本？

How to efficiently check text against a word list in Ruby?

ruby

algorithm

text