A Simple Fuzzy Match Method -- Dice's Coefficient

这两天做了一个帮助功能，需要在一串列表里面模糊匹配出一个结果集供玩家选择，上网搜了一下，一个挺简单又有效的算法。

这个算法的大致过程为：

1:对于输入的两个字符串A,B分别构造出Bigrams, Bg_A， Bg_B

2:对两个Bg_A，Bg_B,对其中Bg_A中的每一个元素到Bg_B里面去找，如果找到，++nMatched，并从Bg_B中移除找到的元素.如果没有找到，无处理

3: nMatched*2/(Bg_A.size()+Bg_b.size())为两个输入串的相似度

Bigrams 为输入串依次邻接的两个字符为元素而构成的一个集合，具体可参考Wiki上的例子。

 Fuzzy Match.txt   

小插曲：

在开发过程里面，在测试这个算法的效率时，发现CalBigrams的时间比CalSimiCoef还多，这显然有问题。跟一下原因在于vector::clear(),每次clear的时候allocator都会deallocate一下(VS 2003 版本STL),赶紧改成vector::resize(0)，性能一下就上来了

对于这个算法，复杂度在O(Len(A)*Len(B))，对于万量级的没有压力；另外后面想了下，嵌套的循环可以用hash_map取代，可以提升一定的性能。