Re: [問題] 計算兩個中文字間的最小距離

看板Perl作者liyih時間16年前 (2009/06/14 02:29)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串2/2 (看更多)

※ 引述《dorwell (這真的是很神奇~~)》之銘言： : 想請問板上的高手~ : 請問有沒有比較快的方法可以計算兩個字間的最短距離(linux指令處理也可以) : 例如: 火車快飛火車快飛，飛過高山 : 火車和高山的最短距離為5 : 謝謝想法是考慮以下兩種可能左 distance 右 1. substr1 ... substr2 2. substr2 ... substr1 用 regexp 來取代 index() 計算比對，使用 .*? 來取得最小的右邊界，而用 $substr1[^\b$substr1\b] 來取得最大的左邊界，match 到的就是兩字串間的最短距離。這想法只是初略的概念，或許還有較正確或更快的方式，您可以參考看看。 ------------------------------------------------------------------------------ #!/usr/bin/perl -w # use strict; use warnings; # use Encode; my $str = decode("utf-8", "火車快飛火車快飛，飛過高山"); #my $str = decode("utf-8", "火車快飛火車快飛，飛過高山高山"); #my $str = decode("utf-8", "火車快飛火車快飛，飛過高山高山"x10000000); my @parts = (decode("utf-8", "火車"), decode("utf-8", "高山"), ); if ($str =~ m/$parts[0]([^\b$parts[0]\b]*?)$parts[1]/) { print "Case 1: ", length($1), " => ", encode("utf-8", $1), "\n"; } if ($str =~ m/$parts[1]([^\b$parts[1]\b]*?)$parts[0]/) { print "Case 2: ", length($1), " => ", encode("utf-8", $1), "\n"; } ------------------------------------------------------------------------- Case 1: A----BA__B => 2 Case 2: A__BA----B => 2 Case 3: A--A_B---B => 1 my @matches = (); if (@matches = ($str =~ m/$parts[0]([^\b$parts[0]\b]*?)$parts[1]/g)) { for (@matches) { print "Case 1: ", length($_), " => ", encode("utf-8", $_), "\n"; } } if (@matches = ($str =~ m/$parts[1]([^\b$parts[1]\b]*?)$parts[0]/g)) { for (@matches) { print "Case 2: ", length($_), " => ", encode("utf-8", $_), "\n"; } } -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 59.104.150.240 ※ 編輯: liyih 來自: 211.74.245.31 (06/15 19:50)