Trie树

有一堆key-value的数据,有人输入一个key的子串,我们希望很容易的得到前面那个key-value中所有key包含该子串的pairs.Trie树是一个不错的解决方案.

如名字所示,Trie树是一个字典树,它的大致方向是构造一个如下图所示的字典树:

Trie

它被用来存储to,tea,ted,ten,A,in,inn等若干字符串. (more…)

倒排索引的简单介绍和实现

在信息检索(Information Retrieval)领域, 有个重要而基础的方法, 倒排索引(Inverted Index), 它被广泛用于各种全文搜索. 在无知的时代, 区区曾经"自创"过一种牛掰的方法, 于是称之为"映射", 小数据集上居然颇有效果, 颇为自得, 后来了解了倒排索引后, 俺才切切实实的了解到 “你以为你的 idea 很牛B, 其实只是你文献看得太少了” 这句话的真谛...

(more…)

KNN 和 KD 树

机器学习中,knn(k-nearest neighbor , 又称k近邻法)是一种比较简单的模型。就是通过计算两个数据集之间的距离远近,然后把一堆数据分为k类。它是一种典型的判别模型(discriminative model).

老板教导曰,这个方法简单到爆了,为什么要介绍这个方法呢,因为解决具体问题的时候,用这个方法试试,调调参数,效果往往很赞,为什么不介绍?管你方法简单还是复杂,f1-measure最高、计算量最小的方法就是最好的方法。某些拿着各种复杂的计算,看起来各种高深莫测却无法说明什么让人信服的道理,也无法用f1-measure说话的,只能用来发paper。 (more…)