ruby - 搜索单词中是否包含特里集

Question

假设我有 2 组:

Set A: ['hi', 'there', 'hire', 'hih', 'hih543']

Set B: ['hihow', 'himan, 'fsdko45']

现在，这些集合实际上每个都包含近百万个元素。

简而言之，我需要做的就是用这种方式过滤集合 B

1) 对于集合 B 的每个元素，找到集合 A 中所有作为其前缀的元素。

所以在上面的示例中，当我根据 hihow 检查集合 A 时，我得到 2 个结果:hi 和 hih。

2) 假设我有 max_offset = 3。对于我在集合 A 中得到的每个结果，我应该添加 [0,1,2,3] 来设置 A 元素的长度，如果任何结果是等于设置B元素长度则返回true。

在这个例子中，假设我们从 hih 开始，所以我向它添加“1”，我向它添加“2”，然后我得到一个匹配项，hih.size + 2 == hihow.size。整个操作返回真。

现在，我怎样才能以一种不需要等待数小时才能完成此操作的方式来执行此操作？我认为我可以使用的一种方法是尝试第 1 组。假设我们让集合 B a 尝试允许快速查找。

现在，我遍历集合 A 的元素，并检查: 对于集合 B 的哪些元素，此元素是前缀？所以对于 'hi'，我会得到 ['hihow', 'himan']。现在我将 [0,1,2,3] 添加到 hi.size 并且如果结果匹配数组中任何 1 个元素的大小，则该元素匹配.

另一种方法是尝试将集合 A 设为 a，然后遍历集合 B，在其末尾去掉 0-3 个字符。所以说我采用 hihow，我生成 ['hihow', 'hiho', 'hih'] 并检查所有三个是否与 A 组尝试匹配。是的，有一个匹配项，所以返回 true。

恐怕我在这种方法中缺少一些正确性方面的东西，所以我把它贴在这里。另外，如果有人有更简单/更好的方法来做到这一点，请告诉我。谢谢!

Answer 1

有了这个gem , 查找以前缀开头的单词似乎比查找单词中包含的前缀更容易。

Trie 是从集合 B 完成的。对于每个匹配项，此代码检查后缀是否最多有 3 个字符:

# gem install triez
require 'triez'

prefixes = ['hi', 'there', 'hire', 'hih', 'hih543']
words =  ['hihow', 'himan', 'fsdko45']

word_trie = Triez.new
words.each do |word|
  word_trie[word] = 1
end

prefixes.each do |prefix|
  suffixes = word_trie.search_with_prefix(prefix).select{|suffix, id| suffix.size <=3 }
  suffixes.each do |suffix, id|
    word = prefix + '|' + suffix
    puts word
  end
end

# =>
# hi|man
# hi|how
# hih|ow