一个字符串算法的优化

litaoye

能否详细说明一下？

无限长保持高效很困难，RK算法已经不错啦。不过用在你这里要构造阶梯哈希表，随着长度增长，效率无限下降……
nlrte13 发表于 2009-6-24 12:21

mathe

先扫描1位长的有时候会有问题，比如：

dvddvddvddvd

就会变为d(vd*2)*3vd 而不是dvd *4


litaoye 发表于 2009-6-24 13:45

这个只能说有歧异,其实这时要找最佳匹配本来就很难.
比如说dvdvddvddvd结果应该是(dv)*2d(dvd)*2呢?还是dv(dvd)*3呢?这个本来就没有明确定义

litaoye

确实存在歧义的情况，我也想了一些例子，比如
ddvddvddvddvd
可以分为2种情况
d dvd dvd dvd dvd
ddv ddv ddv ddv d

我觉得随便找出一种就可以，当然最好是都可以找出来，此外尽量匹配长的情况。

这个只能说有歧异,其实这时要找最佳匹配本来就很难.
比如说dvdvddvddvd结果应该是(dv)*2d(dvd)*2呢?还是dv(dvd)*3呢?这个本来就没有明确定义
mathe 发表于 2009-6-24 15:07

litaoye

btw，这个问题是在实际应用中产生的，出现特殊情况的概率并不高，我也希望把情况考虑的更加周全一些，感谢大家的出谋划策。

仙剑魔

RLE算法吗?
或者说是RLE的加强版?LZ这个方法里似乎有字典的概念存在...