搜索如果特里集包含在一個字

說我有2套：搜索如果特里集包含在一個字

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

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

現在，這些套在現實中都包含接近每百萬個元素。

我需要簡而言之做什麼，是過濾集B，這樣

1）對於集合B中的每個元素，找到集合A中的是它的前綴的所有元素。

所以在上面的例子中，當我檢查集合A對hihow，我得到2個結果：hi和hih。

2）說我有max_offset = 3。對於我在集合A中獲得的每個結果，我應該添加[0,1,2,3]來設置A元素長度，如果ANY結果等於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嘗試，然後遍歷集合B，在集合B的末尾取走0-3個字符。所以說我拿hihow，我產生['hihow', 'hiho', 'hih']，並檢查所有三個，如果任何匹配對集合A嘗試。是的，有一場比賽，所以這返回true。

恐怕我在正確性方面錯過了這種方法，所以我在這裏發佈了它。此外，如果任何人有更簡單/更好的方法來做到這一點，請讓我知道。謝謝！

來源

2017-01-25 anemaria20

如果您已經有工作的代碼，但你只是想加快速度，你也可以詢問[codereview.se] – thesecretmaster

使用此gem，似乎更容易找到以前綴開頭的單詞，而不是查找包含在單詞中的前綴。

特里是從集合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

來源

2017-01-25 13:41:09

搜索如果特里集包含在一個字

回答

相關問題