搜索单词中是否包含trie集
假设我有两个集合：
Set A: ['hi', 'there', 'hire', 'hih', 'hih543']
Set B: ['hihow', 'himan, 'fsdko45']现在，这些集合实际上每个都包含近百万个元素。
简而言之，我需要做的就是以这种方式过滤集合B
1)对于集合B中的每个元素，找出集合A中作为其前缀的所有元素。
因此，在上面的示例中，当我将集合A与hihow进行比较时，我得到了两个结果：hi和hih。
2)假设我有max_offset = 3。对于我在set A中获得的每个结果，我应该添加[0,1,2,3]来设置A元素长度，如果有任何结果等于set B元素长度，则返回true。
在这个例子中，假设我们从hih开始，所以我给它加上了'1‘，我给它加上了'2’，我得到了一个匹配项，hih.size + 2 == hihow.size。整个操作返回true。
现在，我如何才能在不等待数小时完成此操作的情况下完成此操作？我认为我可以使用的一种方法是尝试1组。假设我们使集合B a尝试允许快速查找。
所以现在，我迭代集合A的元素，并检查:对于集合B的哪些元素，这个元素是前缀？因此，对于'hi'，我会选择['hihow', 'himan']。现在我将[0,1,2,3]添加到hi.size中，如果结果与数组中任何1个元素的大小匹配，那么该元素就是匹配的。
另一种方法是对集合A进行a次尝试，然后在集合B上迭代，在集合B的末尾去掉0-3个字符。因此，假设我使用hihow，我生成['hihow', 'hiho', 'hih']，并检查所有三个与集合A的尝试是否匹配。是的，有一个匹配，所以这将返回true。
我担心我在这种方法的正确性方面遗漏了一些东西，所以我把它贴在了这里。此外，如果有人有更简单/更好的方法来做这件事，请让我知道。谢谢!
回答 1
Stack Overflow用户
发布于 2017-01-25 21:41:10
使用此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|owhttps://stackoverflow.com/questions/41851404
复制相似问题
腾讯云开发者
