Personal Branding Roadmap Template

Size: px

Start display at page:

Download "Personal Branding Roadmap Template"

先蓝
5 years ago
Views:

1 文本数据管理与分析正则表达式 -- 语言的形式化描述邱锡鹏复旦大学

2 需求文本处理中的常见需求匹配 * 天气 * 抽取我要买明天从北京到上海的机票数据验证的合法性密码替换替换所有数字如何描述规则! 2

3 语言语言是在一个特定的字符集上, 通过一定的组合规则产生的字符序列的集合有限字母表 ( 词表 ) 英文英文字母中文汉字不是任何字符串都符合语言规则让一只猴子在打字机上随机地按键, 当按键时间达到无穷时, 几乎必然能够打出任何给定的文字, 比如莎士比亚的全套著作 -- 无限猴子定理 3

4 形式语言文法分成四种类型无限制文法上下文相关文法上下文无关文法正规文法 Avram Noam Chomsky 1928 年 12 月 7 日 - 4

5 字符串的属性字符串 (String) 是零个或多个字符组成的有限序列 E.g. tech 是长度为 4 的字符串属性长度空字符串 ϵ 前缀后缀子串子序列 5

6 字符串操作 - 拼接如果 x 和 y 是字符串, 那么 x 和 y 的拼接 ( concatenation)xy 是将 y 附加在 x 的后面 x 为 ba,y 为 na, 则 xy 为 bana,xyy 为 banana 对于一个字符串和它自身的连接, 我们可以用指数运算来表示 x 2 = xx, x 3 = xxx, etc. x 0 = ε. xy 2 = banana. 6

7 字符串集合操作字符串集合 ( 语言 ) 操作并拼接闭包 (Closure) 7

8 字符串集合操作并 L U M { s s is in L or in M} 拼接 LM {st s is in L and t is in M} Kleen 闭包 L * = {Є} U L U LL U LLL U LLLL U. 正则闭包 L + = L U LL U LLL U LLLL U. 8

9 例子 L = {A,B,.,Z,a,b,,z} D = {0,1,2,.,9} L D LD L4 = LLLL L * L(L D)* D 9

10 正则表达式 (Regular Expression) 正则表达式由字母表和算子组成, 可以表示字符串的集合和在这些集合上的运算字母表 {0,1} ASCII 英文字母汉字运算并连接闭包正则表达式 10

11 正则表达式的递归定义 ε 是正则表达式代表 {ε} 如果 a 字母表 Σ 中的符号, 则 a 是正则表达式代表 {a} 如果 r 和 s 是正则表达式, 则 r s 是正则表达式, 代表 L(r) U L(s) rs 是正则表达式, 代表 L(r)L(s) r* 是正则表达式, 代表 (L(r))* 11

12 优先级 * > 拼接 > 所有操作是左结合的例子 a(b c)*d e 12

13 简写如果 r 是正则表达式, 则 r+ 表示 r r* r? 表示 r Є. 表示 any chars a-z 表示 a 到 z 中的所有字母 13

14 例子 : 电话号码 (+86) d=0-9 nation= +d 2 area = d 2 phone = d 8 phone_number = '(' nation')-' area'-' phone 14

15 例子 : l=a-z a-z str = l + address = str '@' str '. str ('.' str)? 15

16 例子 : 无符号数 d=0-9 digits = d + opt_frac = '.' digits Є opt_exp (E('+' '-' Є) digits) Є num digits opt_frac opt_exp 16

17 题目构造四个正则表达式用于验证密码字符串, 依次满足如下要求 : 1. 只能由大小写字母数字和横线 (-) 组成 ; 2. 满足条件 1, 并且开头和结尾不允许是横线 ; 3. 满足条件 2, 并且不允许有连续 ( 超过一个 ) 的横线 4. 满足条件 3, 并且不允许全部是数字 ; 17

18 如何实现? 有限状态自动机 Finite Automata {Q,, δ, q 0, F} Q 状态集合输入符号集合 f 状态转移函数 Q x Q q 0, δ, 起始状态和终止状态 18

19 有限状态自动机 19

20 例子 20

21 例子 21

22 相互转换正则表达式到自动机自动机到正则表达式 22

23 正则表达式到自动机 For ε, For a, x ε y x a y 23

24 正则表达式到自动机 For s t, x ε ε N(s) N(t) ε ε y 24

25 正则表达式到自动机 For st, x N(s ) N(t) y 25

26 正则表达式到自动机 For s*, ε x ε N(s) ε y ε 26

27 例子 (a b)*abb 27

28 正则表达式引擎正则表达式引擎分为两类 NFA ( Nondeterministic Finite Automata, 非确定型有穷状态自动机 ) DFA ( Deterministic Finite Automaton, 确定型有穷状态自动机 ) 在 Java 中, 使用 NFA 和 DFA 结合方法 28

29 正则表达式的特点灵活性逻辑性和功能性非常强 ; 可以迅速地用极简单的方式达到字符串的复杂控制 29

30 正则表达式的不足可读性不高当描述一个复杂的语言集合时, 正则表达式的可读性就变得很差描述能力有限比如对与语言集合 anban (n 为变量 ) 正则表达式并不能描述这个集合正则表达式只适合匹配文本字面, 不适合匹配文本意义 ) 30

31 正则表达式的不足容易引起性能问题像.* 这种贪婪匹配符号很容易造成大量的回溯, 性能有时候会有上百万倍的下降, 编写好的正则表达式要对正则引擎执行方式有很清楚的理解才可以正则的替换功能较差 31

32 自然语言的文法 32

33 程序语言的文法 33

34 上下文无关文法上下文无关文法终止符 terminals T 非终止符 non-terminals N 开始符号 S ( 非终止符 ) 产生式 productions r X N X ε, or X Y1 Y2... Yn where Yi N T 34

35 如何生成语言? 替换规则 X Y1... Yn 表示 X 可以被 Y1... Yn 替换 X ε 表示 X 可以被删除生成语言 1. 由开始符号 S 开始 2. 替换其中的非终止符 X 3. 重复 (2), 直到字符串中全部为终止符 35

36 文法 G 对应的语言文法 G 的语言为 : { a 1 a n S => a 1 a n } 其中,a i 为终止符 36

37 例子 : 算术表达式 E E E E + E ( E) id 37

38 例子 : 匹配的括号 { (i )i i 0} 文法 S (S) S ε 38

39 总结正则表达式是文本处理中很重要的技术几乎用在所有的文本处理系统不足需要一定的专家知识, 维护成本很高不能处理自然语言的歧义现象只能描述部分语言现象, 只能在单一封闭的任务中使用对于更难的任务, 需要使用更加复杂的方法上下文无关文法机器学习 ( 正则表达式也可以作为一种特征使用 ) 39

40 谢谢 40