作者liyih ()
看板Perl
標題Re: [問題] 計算兩個中文字間的最小距離
時間Sun Jun 14 02:29:11 2009
※ 引述《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)
1F：推 dorwell:已經解決問題了~有點晚推文不好意思~感謝高手的幫忙 06/17 21:50