作者tumc (HIHIHI)
看板Perl
标题[问题] 找出最接近的比对字串?
时间Mon May 18 17:42:32 2009
如果有一个字串$s,要与一个都是字串的阵列@s做比对,
但需找出@s中,与$a比对结果最接近的字串,有没有什麽好一点的作法...
(最接近字串的字义是: 有最多字元相同)
小弟想到的很麻烦:
foreach(@s){
if ($s=~/$_/){
push @match,$_;
}
}
接下来从@match中找出长度最长的字串...
,也就是最接近的字串...
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 59.124.185.18
1F：推 abliou:你说的"最接近"有更好的定义吗? 05/18 18:48
2F：→ tumc:ex: $s="abcd" , @s=qw/ab bcd/ =>则bcd最近似 05/18 19:08
3F：推 LiloHuang:先把要比较的 Pattern List 字串长度由长到短排序一下 05/18 19:42
4F：推 LiloHuang:再套用 Aho-Corasick Algorithm 或 Wu-Manber Algorithm 05/18 19:42
5F：推 LiloHuang:Pattern 数量少的话 建议使用 Wu-Manber 演算法比较好 05/18 19:42
6F：→ tumc:冉请问一下,patern list按长度排列,有什麽好方法吗.. 05/18 23:09
7F：推 LiloHuang:依照字串长度 sort 一下不就好了 @@" 看一下 下一篇 05/19 00:20
8F：→ tumc:谢啦.@s = reverse( sort{length($a) <=> length($b)} @s ); 05/19 11:42
9F：→ tumc:原来是卡在排序这里,原以为只有数值大小可以排序 05/19 11:44