PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

轼喻
7 years ago
Views:

1 USTC Chapter 23 Text Processing 王子磊 (Zilei Wang)

2 Overview 应用领域字符串 I/O Maps 规则表达式

3 现在, 你已经知道了基础知识确实如此! 恭喜你! 不要继续关注编程语言特性了! 开始使用吧! 程序和应用是什么样的? 通过编程能够做好什么? 文本处理数值处理嵌入式系统编程银行医学应用科学可视化卡通制作路径规划物理设计

4 文本处理我们表达的都是文本往往都是的书籍论文事务日志 ( , phone, bank, sales, ) Web 网页 ( 甚至是布局指令 ) 图表 ( 数字 ) 邮件程序测量历史数据医疗记录 Amendment I Congress shall make no law respecting an establishment of religion, or prohibiting the free exercise thereof; or abridging the freedom of speech, or of the press; or the right of the people peaceably to assemble, and to petition the government for a redress of grievances.

5 字符串概览字符串 std::string <string> s.size() s1==s2 C 风格字符串 (0 结尾的字符数组 ) <cstring> 或 <string.h> strlen(s) strcmp(s1,s2)==0 std::basic_string<ch>, e.g. unicode 字符串 typedef std::basic_string<char> string; 其它私有字符串类

6 字符串转换简单的 to_string 例如 : template<class T> string to_string(const T& t) { ostringstream os; os << t; return os.str(); } string s1 = to_string(12.333); string s2 = to_string(1+5*6-99/7);

7 字符串转换简单地从字符串提取 template<class T> T from_string(const string& s) { istringstream is(s); T t; if (!(is >> t)) throw bad_from_string(); return t; } 例如 : 比 to_string 处理更复杂 double d = from_string<double>("12.333"); Matrix<int,2> m = from_string< Matrix<int,2> >("{ {1,2}, {3,4} }");

8 一般化的字符串转换 template<typename Target, typename Source> Target lexical_cast(source arg) { std::stringstream ss; Target result; 参考 boost::lexical_cast if (!(ss << arg) // read arg into stream!(ss >> result) // read result from stream!(ss >> std::ws).eof()) // stuff left in stream? throw bad_lexical_cast(); } return result; string s = lexical cast<string>(lexical_cast<double>(" 12.7 ")); // ok // works for any type that can be streamed into and/or out of a string: XX xx = lexical_cast<xx>(lexical_cast<yy>(xx(whatever))); //!!!

9 I/O 概览 in >> x out << x in.get(c) getline(in,s) Stream I/O 根据 x 的格式从 in 读取到 x 中根据 x 的格式将 x 写入 out 中从 in 中读取一个字符到 c 中从 in 中读取一行到字符串 s 中 istream ostream istringstream ifstream iostream ofstream ostringstrea m stringstream fstream

10 Map 概览关联容器 <map>, <set>, <unordered_map>, <unordered_set> map multimap set multiset unordered_map unordered_multimap unordered_set unordered_multiset 文本操作的支柱找出一个单词看看是否已经有一个单词获取给定单词的相关信息具体示例参见 Chapter 23

11 Map 概览 multimap<string,messag e*> John Doe 使用 vector 作为一般存储, 采用其它数据结构用于特殊处理 John Doe John Q. Public Mail_file: vector<message>

12 问题 : 读取一个邮政编码美国州缩写和 ZIP 码两个字母紧接着是 5 个数字 string s; while (cin>>s) { if (s.size()==7 && isletter(s[0]) && isletter(s[1]) && isdigit(s[2]) && isdigit(s[3]) && isdigit(s[4]) && isdigit(s[5]) && isdigit(s[6])) cout << "found " << s << '\n'; } 脆弱的凌乱的绑定的 ( 不易维护 )

13 问题 : 读取一个邮政编码上述简单解决方案的问题它太冗长了 (4 行代码 8 个函数调用 ) 我们忽略了 ( 有意的?) 所有没有用空白符将自身与上下文分开的邮政编码 TX77845 TX 和 ATM77845 我们忽略了 ( 有意的?) 所有用空白符分割州名缩写和数字的邮政编码 TX 我们接受 ( 有意的?) 所有使用小写字母的邮政编码 tx77845 如果我们确定查找一个不同格式的邮政编码, 我们将不得不完全重新代码 CB3 0DS, DK-8000 Arhus

14 TX st 尝试 : 2 nd ( 记得 -1234): 如何表达特殊字符? 3 rd: 4 th ( 显示计数 ): 5 th ( 转义 ): 然而是可选的? 6 th: 我们想在 TX 后有一个可选的空格 7 th ( 看不到的空格 ): 8 th ( 空格可视化 ): 9 th (0 到多个空格 ): wwddddd wwddddd-dddd \w\w\d\d\d\d\d-\d\d\d\d \w2\d5-\d4 \w{2}\d{5}-\d{4} \w{2}\d{5}(-\d{4})? \w{2}?\d{5}(-\d{4})? \w{2}\s?\d{5}(-\d{4})? \w{2}\s*\d{5}(-\d{4})?

15 Regex 库可用它不属于 C++98 标准内 Technical Report 的一部分将纳入 C++0x 标准中使用 VS 9.0 C++, 使用 <regex>, std::tr1::regex GCC 4.3.0, 使用 <tr1/regex>, std::tr1::regex 使用 <boost/regex>, std::boost::regex

16 #include <boost/regex.hpp> #include <iostream> #include <string> #include <fstream> using namespace std; int main() { ifstream in("file.txt"); if (!in) cerr << "no file\n"; // input file regex pat ("\\w{2}\\s*\\d{5}(-\\d{4})?"); cout << "pattern: " << pat << '\n'; // ZIP code pattern } //

17 int lineno = 0; string line; // input buffer while (getline(in,line)) { ++lineno; smatch matches; // matched strings go here if (regex_search(line, matches, pat)) { cout << lineno << ": " << matches[0] << '\n'; // whole match if (1<matches.size() && matches[1].matched) cout << "\t: " << matches[1] << '\n ; // sub-match } }

18 结果 Input: address TX ffff tx asasasaa 2 ggg TX howdy 4 zzz TX sss ggg TX cvzcv TX sdsas 6 xxxtx77845xxx 7 TX Output: pattern: "\w{2}\s*\d{5}(-\d{4})?" 1: TX : tx : TX : : TX : Tx77845 : : TX : -1234

19 正则表达式语法正则表达式的完整理论基础是基于状态机的高效实现你能够干预语法, 但不要修改语义语法是简明神秘和烦人的, 但很有用学习它吧例如 : Xa{2,3} // Xaa Xaaa Xb{2} // Xbb Xc{2,} // Xcc Xccc Xcccc Xccccc \w{2}-\d{4,5} // \w is letter \d is digit (\d*:)?(\d+) // 124: : Subject: (FW: Re:)?(.*) //. (dot) matches any character [a-za-z] [a-za-z_0-9]* // identifier [^aeiouy] // not an English vowel

20 搜索 vs. 匹配搜索 (Searching ) 是在任意数据流中搜索与正则表达式匹配的字符串 regex_search() 在流中找出该模式作为子字符串匹配 (Matching) 是在一个给定大小的字符串中匹配字符串 regex_match() 找出模式的完整匹配及其字符串

21 从 web 上获取的表格 KLASSE ANTAL DRENGE ANTAL PIGER ELEVER IALT 0A A B A A A B A A B A G I A A MO P P B CE MO CE DCE MO CE CE CE REST Alle klasser 数值域文本域不可见的分隔符域语义独立性 i.e. 数字实际上表示某种含义 first row + second row == third row 最后一行是该列的总和

22 描述行第一行正则表达式 : ^[\w ]+( [\w ]+)*$ 字符串常量 : "^[\\w ]+( [\\w ]+)*$" 其他行正则表达式 : ^([\w ]+)( \d+)( \d+)( \d+)$ 字符串常量 "^([\\w ]+)( \\d+)( \\d+)( \\d+)$" 那些不可见的 tab 符号不讨厌吗? 定义一个 tab 符号类那些不可见的 space 符号不讨厌吗? 使用 \s

23 简单的布局检查 int main() { ifstream in("table.txt"); // input file if (!in) error("no input file\n"); string line; int lineno = 0; // input buffer } regex header( "^[\\w ]+( [\\w ]+)*$"); // header line regex row( "^([\\w ]+)( \\d+)( \\d+)( \\d+)$"); // data line // check layout

24 简单的布局检查 int main() { // open files, define patterns } if (getline(in,line)) { // check header line smatch matches; if (!regex_match(line, matches, header)) error("no header"); } while (getline(in,line)) { // check data line ++lineno; smatch matches; if (!regex_match(line, matches, row)) error("bad line", to_string(lineno)); }

25 验证该表 int boys = 0; int girls = 0; // column totals while (getline(in,line)) { smatch matches; // extract and check data if (!regex_match(line, matches, row)) error("bad line"); int curr_boy = from_string<int>(matches[2]); int curr_girl = from_string<int>(matches[3]); int curr_total = from_string<int>(matches[4]); // check row if (curr_boy+curr_girl!= curr_total) error("bad row sum"); if (matches[1]== Alle klasser ) { } // last line; check columns: if (curr_boy!= boys) error("boys don t add up"); if (curr_girl!= girls) error("girls don t add up"); return 0; } boys += curr_boy; girls += curr_girl;

26 应用领域文本处理仅仅是众多领域中的一个或者说其中的若干领域 ( 看你怎么算了 ) Browsers, Word, Acrobat, Visual Studio, 图形处理声音处理数据基础医学科学商业数值计算金融

~~ 1. 1 1648 2 3 4 5 2. 6 1 2 AD1618-1648 3 4 5 6 2

B85301345 E-mail zhu_dehming@dreamer.com.tw 490 1. 2. 1. 2. 1. 2. 1. 2. 3. 4. 1 ~~ 1. 1 1648 2 3 4 5 2. 6 1 2 AD1618-1648 3 4 5 6 2 490 490 1. 490 (freedom of thought) (freedom of expression) 7 1993-1995