作者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