張智星 (Roger Jang) 台大資工系 多媒體檢索實驗室

Presentation on theme: "張智星 (Roger Jang) 台大資工系 多媒體檢索實驗室"— Presentation transcript:

1 張智星 (Roger Jang) jang@mirlab.org http://mirlab.org/jang 台大資工系 多媒體檢索實驗室
MATLAB 程式設計：進階篇 通用運算式 張智星 (Roger Jang) 台大資工系 多媒體檢索實驗室

2 基本介紹：UNIX淵源 早期的電腦作業系統（例如 UNIX 系統）都是以文字為介面，因此對於文字的處理與運算也就有一套特別精心規劃的方式，其中最為人所津津樂道的產出，就是通用運算式（Regular Expressions）的制訂和其廣泛的應用。 通用運算式最早出現在 UNIX 的文字編輯程式，例如 ed、vi 、emacs ，也常被用在以 UNIX 為基礎的程式語言，例如 Perl 等。近年來在 Web 上使用的 JavaScript 以及 VBScript 也加入了通用運算式的功能。

3 基本介紹：通用性 如果照字面來翻譯，Regular Expressions 應該是翻成「正規運算式」，但我們採取的中文名稱是「通用運算式」或簡稱「通用式」，強調此方法能由「簡單的符號來代表複雜的字串」的特性 在本章所學習到的通用運算式，幾乎可以原封不動地搬到其他程式語言來使用，例如 JavaScript、C 、 Python、Perl、VBScript 等等。 MATLAB 6.x 的通用運算式並不支援中文，但在7.x 已經可以完全支援中文了！

4 基本介紹：終極目標 終極目標 你已經在用通用式的概念了！看看你常用到的「萬用符號」（Wildcards characters）：
dir *.txt dir data??.txt 終極目標 用簡單的符號來代表複雜的字串，以便進行特定字串的比對、抽取及代換

5 基本用法：尋找字串開始位置 使用 regexp 指令比對字串，可找出某一個特定型態的字串在另一個字串的出現位置。
例如，如果要找出「love」在一個字串「Love me tender, love me sweet, never let me go」出現的位置，可用下列程式碼： 範例4-1： regExp01.m 回傳結果為： startIndex = 17 代表「love」在 string 變數所出現的位置是 17。 string = 'Love me tender, love me sweet, never let me go'; pattern = 'love'; startIndex = regexp(string, pattern)

6 基本用法：大小寫均可 若要進行「大小寫均可」（Ignore Cases）的比對，則可以使用 regexpi 指令 ：
範例4-2： regExp02.m 回傳結果為：startIndex = 代表「Love」和「love」在 string 變數所出現的位置分別是 1 和 17。 string = 'Love me tender, love me sweet, never let me go'; pattern = 'love'; startIndex = regexpi(string, pattern)

7 基本用法：字串開始和結束位置 若要找出字串出現的開始和結束位置，可以在使用 regexp 時，多加一個輸出變數：
範例4-3： regExp03.m 回傳結果為： start = finish = 其中 start 和 finish 代表所比對到的三個「me」的開始和結束位置。 string = 'Love me tender, love me sweet, never let me go'; pattern = 'me'; [start, finish] = regexp(string, pattern)

8 方括弧：列舉欲比對字元 我們可以使用方括弧（[]）來列舉所要比對的字元，可見下列範例： 範例4-4： regExp10.m
string = 'I bet there is a bat on the boat'; pattern = 'b[aeiou]t'; [start, finish] = regexp(string, pattern); fprintf('Matched substrings:\n'); for i=1:length(start) % 列印出比對結果 fprintf('\t%d: %s\n', i, string(start(i):finish(i))); end 回傳結果為：Matched substrings: 1: bet 2: bat

9 方括弧：使用範圍符號 若是連續字母或數字，就可以使用範圍符號「-」來簡化方括弧中的列舉字元。例如，
數字 0 到 9，可以寫成 [ ]，或是簡化寫成 [0-9]。 26 個小寫英文字母可以簡化寫成 [a-z] 。 26 個大寫英文字母可以簡化寫成 [A-Z]。 英文字母：[a-zA-Z] 數字或英文字母：[0-9a-zA-Z]

10 方括弧：數字範圍 例如若要比對西元年份，可見下列範例： 範例4-5： regExp11.m
string = 'My brother and me were born in 1965 and 1962, respectively.'; pattern = '[0-9][0-9][0-9][0-9]'; [start, finish] = regexp(string, pattern); fprintf('Matched substrings:\n'); for i=1:length(start) % 列印出比對結果 fprintf('\t%d: %s\n', i, string(start(i):finish(i))); end 回傳結果為：Matched substrings: 1: 1965 2: 1962

11 向量化的輸入和輸出 事實上，regexp 指令也可以接收向量化的輸入，並產生向量化的輸出，例如： 範例4-6： regExp07.m
string = {'Barcelona', 'Y2K', 'MATLAB 7.3'}; pattern = {'lona', '[0-9]', '[A-Z]'}; [start, finish] = regexp(string, pattern) start = [6] [2] [1x6 double] finish = [9] [2] [1x6 double] 其中 start 和 finish 都是 1x3 的異值陣列，而且 start{i} 和 finish{i} 就是 regexp(string{i}, pattern{i}) 所得到的結果。

12 方括弧：範例列表 有關方括弧的使用，列表整理如下： 通用式 說明及範例 比對不成立之字串 [13579]
包含 "1" 或 "3" 或 "5" 或 "7" 或 "9" 的字串，例如："a3b", "1xy" "y2k" [0-9] 含數字之字串 不含數字之字串 [a-z0-9] 含數字或小寫字母之字串 不含數字及小寫字母之字串 [a-zA-Z0-9] 含數字或字母之字串 不含數字及字母之字串 b[aeiou]t "bat", "bet", "bit", "bot", "but" "bxt", "bzt" [^0-9] 不含數字之字串 （若要比對 ^，請使用 \^） [^aeiouAEIOU] 不含母音之字串 （若要比對 ^，請使用 \^） 含母音之字串 [^\^] 不含 "^" 之字串，例如 "xyz", "abc" "xy^", "a^bc" 像不像表情符號？

13 特定字元：列表 有些通用式會常被用到，因此已被定義為特定字元，以簡化整體通用式，這些字元列表說明如下： 通用式的特定字元 說明 等效的通用式
\d 數字 [0-9] \D 非數字 [^0-9] \w 數字、字母、底線 [a-zA-Z0-9_] \W 非 \w [^a-zA-Z0-9_] \s 空白字元 [ \r\t\n\f] \S 非空白字元 [^ \r\t\n\f] . 任一個字元，但不包含換行字元（\n） 無 若是針對中文，可以加上全型空白。

14 特定字元：比對數字 我們可以用「\d」來比對由 0 到 9 的數字，並用「\D」來比對非數字。假設我們要找出「兩個非數字夾一個數字」的子字串，可使用「\D\d\D」。 範例4-7： regExp04.m string = 'Some terms: RU486, Y2K, 900GHz, B2B, B2C'; pattern = '\D\d\D'; [start, finish] = regexp(string, pattern); fprintf('Matched substrings:\n'); for i=1:length(start) fprintf('\t%d: %s\n', i, string(start(i):finish(i))); end 回傳結果為： Matched substrings: 1: Y2K : B2B : B2C

15 特定字元：句點的使用 我們也可以抓出來「兩個 t 中間夾 4 個任意字元」的子字串，請見下例範例： 範例4-8： regExp13.m
string = 'I like the tidbit given by pattern = 't....t'; [start, finish] = regexp(string, pattern); fprintf('Matched substrings:\n'); for i=1:length(start) fprintf('\t%d: %s\n', i, string(start(i):finish(i))); end 回傳結果為： Matched substrings: 1: tidbit :

16 定位符號：句首和句尾 在通用式裡，最常用的定位符號就是 ^ 和 $，其中 ^ 代表一個字串的開始位置，因此 ^xy 代表「以 xy 開始的字串」；而 $ 代表一個字串的結束位置，因此 xy$ 「代表以 xy 結束的字串」。 範例4-9： regExp14.m str1 = 'Chapter 5 is my favorite'; str2 = 'I like Chapter 2'; pat = '^Chapter'; fprintf('regexp(''%s'', ''%s'') = %d\n', str1, pat, regexp(str1, pat)); fprintf('regexp(''%s'', ''%s'') = %d\n', str2, pat, regexp(str2, pat)); 回傳結果為： regexp('Chapter 1 is my favorite', '^Chapter') = 1 regexp('I like Chapter 1', '^Chapter') =

17 定位符號：列表 以下是對於定位符號的列表與整理： 通用式 說明及範例 比對不成立之字串 ^xy
以 "xy" 開始的字串，例如 "xyz", "xyab" （若要比對 ^，請使用 \^） "axy", "bxy" xy$ 以 "xy" 結尾的字串，例如 "axy", "abxy" （若要比對 $，請使用 \$） "xya", "xyb"

18 字串的重複：範例列表 我們也可定義字元的重複次數，整理如下： 正規表示法 說明 a? 零或一個 a （若要比對‘?'字元，請使用 \?）
a.{5}b a 和 b中間夾五個（非換行）字元

19 字串的重複：基本範例 使用上表與字元重複次數相關的特殊符號，我們可以從字串「I like Chapter 2, Chapter 10, and Chapter 25 of this book!」抓出「Chapter 2」、「Chapter 10」，以及「Chapter 25」 範例4-10： regExp08.m string = 'I like Chapter 2, Chapter 10, and Chapter 25 of this book!'; pattern = 'Chapter [1-9][0-9]?'; [start, finish] = regexp(string, pattern); fprintf('Matched substrings:\n'); for i=1:length(start) fprintf('\t%d: %s\n', i, string(start(i):finish(i))); end 回傳結果為：Matched substrings: 1: Chapter : Chapter : Chapter 25

20 字串的重複：信用卡號碼 若要抓出信用卡號碼，可見下列範例： 範例4-11： regExp12.m
string = 'My credit number is " ".'; pattern = '\d{4}-\d{4}-\d{4}-\d{4}'; [start, finish] = regexp(string, pattern); fprintf('Matched substrings:\n'); for i=1:length(start) fprintf('\t%d: %s\n', i, string(start(i):finish(i))); end Matched substrings: 1:

21 字串的重複：身份證字號 如果要比對身份證字號，可用下列範例： 範例4-12： regExp05.m
事實上，身份證字號本身就有內在的編碼規則，這些規則和使用者的性別有關，還包含一個檢查碼，並非簡簡單單地由一個英文字母加上九個數字所構成。 string = 'My Id number is F '; pattern = '[A-Z]\d{9}'; start = regexp(string, pattern) start = 17

22 字串的重複：特定樣式比對 若要在一個字串中，找出「在 b 與 t 中間夾二或三個母音的子字串」，可見下列範例：
範例4-13： regExp09.m string = 'bt bat bet ban bit boat beet berp boaet baeiout'; pattern = 'b[aeiou]{2,3}t'; [start, finish] = regexp(string, pattern); fprintf('Matched substrings:\n'); for i=1:length(start) fprintf('\t%d: %s\n', i, string(start(i):finish(i))); end Matched substrings: 1: boat 2: beet 3: boaet

23 字串的重複：小括弧的使用 我們也可以利用小刮號，進行重複字串的比對： 範例4-14： regExp18.m
string = 'Two cards: and '; pattern = '(\d{4}-){3}\d{4}'; [start, finish] = regexp(string, pattern); fprintf('Matched substrings:\n'); for i=1:length(start) fprintf('\t%d: %s\n', i, string(start(i):finish(i))); end Matched substrings: 1: 2:

24 字串的重複：比對原則 在通用式所採用的比對原則是「最大比對（Maximal Match）或是」「貪心比對」（Greedy Match），因此會盡量「貪」到越多的字元越好， 若使用通用式 'foo.*bar' 來比對字串 'The food is under the bar in the barn.'，所比對到的是長字串 ‘food is under the bar in the bar’，而不是另一個符合比對標準的短字串 ‘food is under the bar’。 若要使通用式進行極小比對（Minimal Match），也就是在符合比對的條件下，選擇最短的字串，那麼就要在星號之後加上問號。

25 字串的重複：最大與最小比對 「最大比對」與「最小比對」的範例： 範例4-15： regExp19.m
string = 'The food is under the bar in the barn.'; pattern1 = 'foo.*bar'; [start, finish] = regexp(string, pattern1); fprintf('\tGreedy match: %s\n', string(start:finish)); pattern2 = 'foo.*?bar'; [start, finish] = regexp(string, pattern2); fprintf('\tMinimal match: %s\n', string(start:finish)); Greedy match: food is under the bar in the bar Minimal match: food is under the bar

26 字串的重複：問號的意義 請注意，問號在通用式的意義是和內文相關（Context Dependent）的，可以分兩類情況來說明：
如果問號接在一般字元之後，代表「比對前一個字元零次或一次」。 如果問號接在星號或加號之後，代表「極小比對」。

27 Open Question 如何在使用通用運算式時，一次找到所有可能的比對成功的子字串？

28 選項的使用：「或」的使用 如果同時比對數個通用式，可使用「|」來他們串起來，而達到「或」（OR）的邏輯運算效果。如，我們可同時比對信用卡號碼、身份證字號、電話號碼。 範例4-16： regExp16 .m string = ' and A and '; pattern = '\d{4}-\d{4}-\d{4}-\d{4}|[A-Z]\d{9}|\d{7}'; [start, finish] = regexp(string, pattern); fprintf('Matched substrings:\n'); for i=1:length(start) fprintf('\t%d: %s\n', i, string(start(i):finish(i))); end 回傳結果為：Matched substrings: 1: : A :

29 小括弧用於「或」 若是要進行 OR 運算的通用式有共通的部分，我們就需要使用小括弧來進行更明確的規範，例如下列範例，可以同時比對 Chapter 和 Section，以及後續的數字： 範例4-17： regExp17 .m string = 'I like Chapter 12, particularly Section 4!'; pattern = '(Chapter|Section) [1-9]\d?'; [start, finish] = regexp(string, pattern); fprintf('Matched substrings:\n'); for i=1:length(start) fprintf('\t%d: %s\n', i, string(start(i):finish(i))); end Matched substrings: 1: Chapter 12 2: Section 4

30 小括弧：回傳比對符合的字串 小括弧還有一個重要的功能，就是可以將對應於小括弧的子字串傳回來，非常適用於特定子字串的抽取。
範例4-18： regExp20 .m string = 'I bet there is a bat on the boat'; pattern = 'b(\w*)t'; [start, finish, token] = regexp(string, pattern); fprintf('There are %d matched substrings:\n', length(start)); for i=1:length(start) fprintf('\t%d: matched="%s", token="%s"\n', i, string(start(i):finish(i)), string(token{i}(1):token{i}(2))); end 回傳結果為：There are 3 matched substrings: 1: matched="bet", token="e“ 2: matched="bat", token="a" 3: matched="boat", token="oa" 在上例中，token 就是由 b 和 t 所夾的字串。

31 小括弧：抽取網頁連結 我們可以利用「小括弧抽取字串」功能來抽取網頁的連結網址和連結文字，這在網頁搜尋引擎的製作上，是一個很重要的步驟，因為「網頁蒐集程式」（又稱為 Robot 或 Crawler）將網頁抓回來後，就是根據網頁內的連結網址，來決定下次要蒐集的網頁，如此依次（可根據 Depth-first Search 或 Breadth-first Search）反覆蒐集，就可以抓到很多網頁。 使用類似的方法，也可以抽取網頁中的電子郵件帳號，燒成 DM 電郵光碟牟利！

32 網頁範例 網頁範例： regExp.htm <html> <body>
List of important links: <ul> <li>…: <a href=" <li>…: <a href=" Jang</a>. <li>…: <a href=" </ul> </body> </html>

33 小括弧：抽取連結的範例 利用 regexp 指令所傳回來的第三個輸出變數，我們可以輕易地抓出此網頁的連結網址和連結文字：
範例4-20： linkExtraction .m string = fileread('regExp.htm'); pattern = '<a href="(.*?)">(.*?)</a>'; [start, finish, token] = regexp(string, pattern); fprintf('由檔案 "%s" 抽取出 %d 個連結：:\n', fileName, length(start)); for i=1:length(start) fprintf('\t%d: 連結文字："%s", 連結網址："%s"\n', i, string(token{i}(2,1):token{i}(2,2)), string(token{i}(1,1):token{i}(1,2))); end 由檔案 "regExp.htm" 抽取出 3 個連結：: 1: 連結文字："MathWorks", 連結網址：" 2: 連結文字："Roger Jang", 連結網址：" 3: 連結文字："Google", 連結網址："

34 字串的代換：基本範例 利用通用式來進行字串的代換，主要的指令是 regexprep。如，若要將所有「b 和 t 中間至少夾一個母音」的字串代換為 xxx。 範例4-21： regExpRep01 .m str = 'I bet there is a bat in the boat!'; pat = 'b[aeiou]+t'; newStr = regexprep(str, pat, 'xxx'); fprintf('%s\n', newStr); 回傳結果為： I xxx there is a xxx in the xxx!

35 What does this sentence mean?
字串的代換：壓縮空白 我們可將一列字串中，連續出現的多個空白字元，壓縮成一個空白字元： 範例4-22： regExpRep02.m string = 'Draft beer, not people.'; pattern = '\s+'; string2 = regexprep(string, pattern, ' '); % 將多個空白壓縮成一個 fprintf('原字串：%s\n', string); fprintf('修改後：%s\n', string2); 原字串：Draft beer, not people. 修改後：Draft beer, not people. What does this sentence mean?

36 字串的代換：使用暫存變數 在使用 regexprep 進行字串代換的過程中， 小括弧比對到的子字串會被儲存到變數 $1, $2, $3 等，以便於處理後再插回原字串，例如：： 範例4-23： regExpRep03.m str = 'I walk up, he walks up, we are all walking up.'; pat = 'walk(\w*) up'; newStr = regexprep(str, pat, 'sleep$1 tight'); fprintf('%s\n', newStr); I sleep tight, he sleeps tight, we are all sleeping tight.

37 字串的代換：對調英文字 使用類似的方法，我們也可以將一個字串的前兩個英文字對調，如下： 範例4-24： regExpRep04m
str = 'are you ready'; pat = '^([^ ]+) +([^ ]+)'; rep = '$2 $1'; str2 = regexprep(str, pat, rep); fprintf('原字串：%s\n', str); fprintf('修改後：%s\n', str2); 原字串：are you ready 修改後：you are ready

38 字串的代換：其它選項 在使用 regexprep 指令時，可以在第四個輸入變數輸入其他字串，以代表不同的代換方式。例如： ‘ignorecase’：進行「大小寫不分」的比對與代換。 ‘once’：只代換第一個比對符合的字串。 其他選項請查看 regexprep 的線上支援（在 MATLAB 輸入「doc regexprep」即可顯示線上支援）。