求个容错匹配算法

三月廿七

类似这个效果，

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

粗略的计算一下,...  

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

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

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

zhujiang73

粗略的计算一下,...   

"(两个句子中有80%以上的字相同就算匹配)" 这一步是省不了的，...
...
三月廿七 发表于 2011-10-21 16:19

    “二叉查找树（Binary Search Tree），或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值”

     按这个算法不容错呀，前面有一个字不对就跑到另一个分支去了。

三月廿七

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

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

zhujiang73

不如用 字符串哈希吧...
三月廿七 发表于 2011-10-21 17:17

    不是吧，一句里有一个字不同哈希也不同呀？

三月廿七

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

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

zhujiang73

本来就是两个不同的句子呀, 你不能事先假定他俩相同，
你还得比较啊，不然你比较什么呢？？
三月廿七 发表于 2011-10-21 17:26

     需要某种特征值，两个句子里相同的部分越多这个特征值越接近，特征值的差较小时认为这两个句子近似匹配。

三月廿七

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

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

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

AD8018

不好办啊，这样算匹配吗？

赵兄托你帮我半点事

事点半我帮你托兄赵

zhujiang73

隐约记得 编程之美中 有一道题是计算字符串相似度的...
三月廿七 发表于 2011-10-21 17:36

    我找找去 {:3_189:}

zhujiang73

不好办啊，这样算匹配吗？

赵兄托你帮我半点事

事点半我帮你托兄赵
AD8018 发表于 2011-10-21 17:37

    这个应该是不行的