Perl 模糊字串比對（Approximate Matching）String::Approx 模組

這裡介紹如何使用 Perl 的 String::Approx 模組進行模糊字串比對（approximate matching）。

模糊搜尋是實務上常用的搜尋方法，當使用者輸入的關鍵字有些誤差時，透過模糊搜尋還是可以找到使用者想要找的資訊，例如 color 與 colour 兩個字其實是一樣的，如果使用者輸入其中一個，使用一般性的比對就找不到另外一個，或是說使用者根本把單字拼錯，那一般的搜尋就更找不到了。

首先安裝 String::Approx 這個 Perl 模組，在 Ubuntu Linux 中可以用 apt 安裝：

apt-get install libstring-approx-perl

接著就可以使用了，下面這個是一個簡單的 Hello, World 程式：

#!/usr/bin/perl
use String::Approx qw(amatch);

@list = <DATA>;
$pattern = "strong";

@matches = amatch($pattern, @list);
print @matches;

__DATA__
steamer
strait
string
stringed
strings
strong
strophe
stream
stem
stemming

這裡我們首先引入 String::Approx 模組的 amatch 函數，然後利用 amatch 比對 @list 中的字串，搜尋 $pattern 這個關鍵字，並輸出比對成功的字串結果。

這裡我們將 $pattern 設為 strong，而程式執行之後，搜尋出來的結果會像這樣：

string
stringed
strings
strong

除了找出 strong 之外，幾個類似的字眼也會一併找出來，如果使用者是要找 string，但是打錯字輸入成 strong，用模糊搜尋還是可以找得出來，這就是模糊搜尋的好處。

如果只是要判斷是否有比對成功，可以這樣做：

if (amatch($pattern, @list)) {
	# matched
}

在預設的情況下，amatch 會比對兩個字串之間的差異，如果差異在一定的門檻值以內（預設為 $pattern 長度的十分之一），就會視為比對成功，差異的計算是看 $pattern 與比對的字串之間增加、減少或是改變了幾個字元，實際的計算方式請參考 Levenshtein distance 的說明。

您可以直接指定這個字串差異的門檻值，可以使用百分比，或是差異數目（edit），或是兩者同時使用：

amatch($pattern, ["3 30%"], @list);

當同時指定多個值的時候，amatch 會檢查每一個門檻值，當每一個門檻值都符合的時候，才會視為比對成功。

另外也可以針對插入（Insertions）、刪除（Deletions）與替換（Substitutions）的門檻值做指定：

amatch($pattern, ["I2 D20% S0"], @list);

加入 i 可以讓比對時忽略大小寫的差異：

amatch($pattern, ["i I2 D20% S0"], @list);

如果想要檢查 字串之間的 Levenshtein distance，可以使用 adist：

use String::Approx 'adist';
$dist = adist("pattern", $input);
@dist = adist("pattern", @input);

另外也可以使用 adistr 計算相對的距離，如果距離為 0 代表完全符合，若是 1 代表完全不符合：

use String::Approx 'adistr';
$dist = adistr("pattern", $input);
@dist = adistr("pattern", @inputs);

您可以結合 adist 或 adistr 將多個字串依照相似性來排序，這個排序方法在許多應用上都常常用到：

my %d;
@d{@inputs} = map { abs } adistr("pattern", @inputs);
my @d = sort { $d{$a} <=> $d{$b} } @inputs;

如果您只是想要計算字串之間的 Levenshtein distance，那麼也可以使用 Perl 的 Text::Levenshtein 與 Text::LevenshteinXS 模組，另外 Text::WagnerFischer 與 Text::PhraseDistance 也可以做類似的事情。

最後要提醒一點，String::Approx 的執行速度通常比 Perl 內建的比對函數慢上數十倍，所以如果您需要比對大量的字串時，建議還是盡量使用一般的常規表達式來處理，真的沒辦法才使用 String::Approx 模組。

參考資料：Safari Books Online