Autocompete with Trie

中关村村草

Autocompete with Trie

像微薄里面用户输入一个@会从服务器取出匹配的用户login name什么的。这种场景用前缀树比较节省空间并且效率高。fast trie——A super fast, efficiently stored Trie for Ruby。据作者说速度是灰常的快。。
地址：https://github.com/tyler/trie

Java代码

1. gem install fast_trie

复制代码

Ruby代码

1. require 'trie'
   
2. 
   
3. TRIE = Trie.new
   
4. 
   
5. #初始化数据
   
6. User.all.each do |user|
   
7.   TRIE.add(user.login_name, 0)
   
8. end
   
9. 
   
10. #js调用autocomplete
    
11. def autocomplete
    
12.     children = sort_by_weight(TRIE.children(params[:prefix]))
    
13. 
    
14.     respond_to do |format|
    
15.       format.js { render(:string => JSON.dump(children)) }
    
16.     end
    
17.   end
    

复制代码

根据用户的输入行为给某个key增加权重(用于搜索排序)：
def incr_weight(login_name, n = 1)
  weight = TRIE.get(login_name) || 0
  TRIE.add(login_name, weight + n)
end

#根据权重给结果排序
def sort_by_weight(login_name_list)
  login_name_list.sort_by{|login_name|  TRIE.get(login_name)}
end

这东西的性能不错啊 这是测试数据，看样子比那个redis的autocomplete要简单高效呀：

引用
Performance Characteristics

Here are some quick benchmarks on my 2.4ghz Intel Core 2 Duo MacBook Pro:

For keys that are 5 characters long:
31,344 adds/second
1,827,408 searches/second
38,453 prefixes searches/second

For keys that are 10 characters long:
30,653 adds/second
1,802,649 searches/second
13,553 prefix searches/second

For keys that are 20 characters long:
30,488 adds/second
1,851,461 searches/second
5,855 prefix searches/second

For keys that are 40 characters long:
30,710 adds/second
1,838,380 searches/second
2,762 prefix searches/second


不过好像不能被序列化。这样在多进程部署的时候有点麻烦呀。再研究一下。。

2gua

嗯，做搜索引擎的，可以考虑下，Ruby的库是越来越多了。