求个容错匹配算法

三月廿七

类似这个效果，

      1.＊＊＊＊＊＊＊＊＊＊，本人数学不好大家帮忙，＊＊＊＊＊＊＊＊＊ ...
zhujiang73 发表于 2011-10-14 10:17

粗略的计算一下,...  

"(两个句子中有80%以上的字相同就算匹配)" 这一步是省不了的，...
0(n)
然后，BST的速度还可以， 如果BST能够适合要求， 还考虑什么rbtree...， 不是多此一举啊,  

你把第一篇文章包含的所有字符串的地址添加到 BST中，然后再用第二篇作对比
(2nlgn)
估计 字符串比较 和 计算字符串相似度 可以合在一个函数里处理

所以， 最终的复杂度就是 2nlgn

三月廿七

“二叉查找树（Binary Search Tree），或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子 ...
zhujiang73 发表于 2011-10-21 17:07

{:3_182:}
不如用 字符串哈希吧...

三月廿七

不是吧，一句里有一个字不同哈希也不同呀？
zhujiang73 发表于 2011-10-21 17:21

那我就只知道 两层 for  循环啦...{:3_183:}

三月廿七

需要某种特征值，两个句子里相同的部分越多这个特征值越接近，特征值的差较小时认为这两个句子近 ...
zhujiang73 发表于 2011-10-21 17:34

我知道我说错了, 你还 MARK 一下， 我晕哦
本来想得分的， 结果分没得到， 把脸给丢了 {:3_183:} ....

隐约记得 编程之美中 有一道题是计算字符串相似度的，你可以搜下...