Date post: | 05-Apr-2015 |
Category: |
Documents |
Upload: | tillo-kappeler |
View: | 115 times |
Download: | 1 times |
1
Abstrakte Operatoren für komplexe reguläre Ausdrücke
Karin Haenelt
5.7.2010
Themen
Einführung Notationskonventionen Abstrakte Operatoren
Enthaltensein Restriktion Ersetzungen
Theoretische Basis des Ersetzungsoperators: Einschränkung der Mächtigkeit kontextsensitiver Regeln
Anwendungsbeispiele Restriktionsoperator: Parsing Ersetzungsregel: Regelhafte Pluralbildung
© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
2
Abstrakte Operatoren für komplexe reguläre Ausdrücke
erweitern die Notation für reguläre Ausdrücke zur einfacheren Formulierung linguistischer Regeln
Konstrukte Enthaltensein $ Restriktionen Ersetzungen → und @→
erweitern nicht die deskriptive Mächtigkeit regulärer Ausdrücke stellen eine höhere Abstraktionsebene zur Verfügung
Quellen: Koskenniemi (1983), Karttunen (1995) und Beesley/Karttunen (2003))
3© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Themen
Einführung Notationskonventionen Abstrakte Operatoren
Enthaltensein Restriktion Ersetzungen
Theoretische Basis des Ersetzungsoperators: Einschränkung der Mächtigkeit kontextsensitiver Regeln
Anwendungsbeispiele Restriktionsoperator: Parsing Ersetzungsregel: Regelhafte Pluralbildung
4© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Notationskonventionen
5
Karttunen, Chanod, Grefenstette, Schiller 1997
© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Themen
Einführung: Komplexe Reguläre Ausdrücke Notationskonventionen: Basisoperatoren Definitionen komplexer regulärer Ausdrücke
Enthaltensein Restriktion Ersetzungen
Theoretische Basis des Ersetzungsoperators: Einschränkung der Mächtigkeit kontextsensitiver Regeln
Anwendungsbeispiele Restriktionsoperator: Parsing Ersetzungsregel: Phonologisches Beispiel
6© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Enthaltensein-Operator $Definition
$A =def [?* A ?*]
Beispiel: $[a|b] bezeichnet alle Zeichenketten, die mindestens ein „a“ oder „b“ enthalten
Beispiel: $a bezeichnet alle Zeichenketten, die ein „a“ enthalten
7
Karttunen, Chanod, Grefenstette, Schiller 1997
a
a , ??
[?* a ?*]
© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Restriktionsoperator =>Definition
A B _ C =def [~[[~[?* B] A ?*] | [?* A ~[C ?*]]]] 1) oder auch
A B _ C =def ~ [ ~ [?* B] A ?*] & ~ [?* A ~[C ?*]] 2)
Jedes A muss einen Vorgänger B und einen Nachfolger C haben
8
1) Beesley, Karttunen 2003 Karttunen, Chanod, Grefenstette, Schiller 19972) Karttunen, 2005, Folie 443) Graphik: Karttunen 2005, Folie 44
?, c
b
?,c
b
a
c
Σ = {a,b,c,?}
© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Restriktionsoperator
kodiert auf kompakte Art eine nützliche Bedingung, die mit primitiveren Operatoren nur sehr umständlich auszudrücken ist
kompakte Darstellung a b _ c äquivalente reguläre Ausdrücke (Definition):
Version 1) ~ [ ~ [?* b] a ?*] & ~ [?* a ~[c ?*]]
Version 2)
[~[[~[?* b] a ?*] | [?* a ~[c ?*]]]]
9
1) Beesley, Karttunen 2003 Karttunen, Chanod, Grefenstette, Schiller 19972) Karttunen, 2005, Folie 44
?, c
b
?,c
b
a
c
Σ = {a,b,c,?}
© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Restriktionsoperator
äquivalente reguläre Ausdrücke (Definition): ~ [~[?* b] a ?*] & ~ [?* a ~[c ?*]] [~[ [~[?* b] a ?*] | [?* a ~[c ?*]] ]]
De Morgansches Gesetz: ~(x|y) = ~x & ~y
Paraphrase [~[?* B] A ?*] (entspricht x) – direkt vor A steht kein B [?* A ~[C ?*]] (entspricht y) – direct hinter A steht kein C beide Definitionen schließen diese beiden Fälle aus.
10© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
XEROX Finite State Compiler
11
1) nicht mehr online, download: http://www.fsmbook.com auch auf CD in Beesley/Karttunen 2003
© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
RestriktionsoperatorVergleich der beiden Definitionsvarianten
12
XEROX Finite State Compiler
(nicht mehr online, download: http://www.fsmbook.com & auf CD in Beesley/Karttunen 2003)
© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Ersetzungsoperator →Definition
A → B =def [ [~$[A - []] [A .x. B]]* ~$[A – []]]
ersetze A durch B A und B bezeichnen reguläre Sprachen, aber der Ausdruck als
Ganzes bezeichnet eine Relation Die [A → B] Relation
bildet jede Zeichenkette, die kein A enthält, auf sich selbst ab
Zeichenketten, die ein A enthalten, werden Kopien zugeordnet, in denen jedes A gegen ein B ausgetauscht ist, die sonst aber mit der Kette identisch sind
13
Karttunen, Chanod, Grefenstette, Schiller 1997
© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Ersetzungsoperator Graphische Darstellung
14
(Karttunen, 1993)
Transduktor zur Regel ε → ab / _b (optional)
© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Themen
Einführung Notationskonventionen Abstrakte Operatoren
Enthaltensein Restriktion Ersetzungen
Theoretische Basis des Ersetzungsoperators: Einschränkung der Mächtigkeit kontextsensitiver Regeln
Anwendungsbeispiele Restriktionsoperator: Parsing Ersetzungsregel: Regelhafte Pluralbildung
15© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Theoretische Basis des Ersetzungsoperators
Entwicklung stammt ursprünglich aus dem Bereich der Modellierung phonologischer Regeln
Regeln der Form α→β/ γ_δ Chomsky /Halle
(1968) ersetze α, das zwischen γ und δ steht, durch β kontextsensitiv
kontextsensitive Regeln sind nicht so mächtig wie es scheint,wenn man bestimmte Einschränkungen annimmt
16© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Theoretische Basis komplexer regulärer Ausdrücke
Schützenberger (1961): für jedes Paar sequentiell anwendbarer Transduktoren
existiert ein äquivalenter einzelner Transduktor Johnson (1972) (seinerzeit nicht beachtet und vergessen)
Kaplan und Kay (um 1980) (neu entdeckt): Eingabe-Ausgabepaare einer kontextsensitiven Regel
stellen reguläre Relationen dar, wenn eine kontextsensitive Regel im nächsten Zyklus nicht wieder auf ihre eigene Ausgabe angewendet werden darf
17© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Theoretische BasisFolgerung aus der Beobachtung Schützenbergers
18
(Karttunen, 2005 (1), Folie 21)
Folgerung:jede sequentielleRegelanwendungkann äquivalent durcheine Regel beschriebenwerden
© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Theoretische BasisBeobachtungen von Johnson und Kaplan und Kay
Effekt der Einschränkung der Anwendungsposition kontextsensitiver Regeln
Regel ε → ab / _b (optional)füge optional die Zeichenkette ab vor einem b ein
zwei Arten der Anwendung:
19
a ba a b ba a a b b b. . .a an bn b
a ba a b ba a b a b b. . .a [a b]n b
(Karttunen, 1993)
kontextfreie Sprache reguläre Sprache
© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Themen
Einführung Notationskonventionen Abstrakte Operatoren
Enthaltensein Restriktion Ersetzungen
Theoretische Basis des Ersetzungsoperators: Einschränkung der Mächtigkeit kontextsensitiver Regeln
Anwendungsbeispiele Restriktionsoperator: Parsing Ersetzungsregel: Regelhafte Pluralbildung
20© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Restriktionsoperator: AnwendungsbeispielGrefenstette (1999), Regeln für Nominalphrasen
vereinfachte Regel für französische Nominalphrasen
Kompilationsschritte Überführung der Einzelregeln in endliche Automaten Intersektion der Einzelautomaten (Ausführung der &-
Verknüpfung)
21
NounGroup = [ [ Art => _ [ Noun ] ] &
[ Noun => _ [ PAdj | Prep | .#. ] ] &
[ PAdj => _ [ PAdj | Prep | .#. ] ] &
[ Prep => _ [ Art | Noun ] ] ] &
[ [ Art | Noun ] [ Art | Noun | PAdj | Prep ] * ] ;
© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Restriktionsoperator: AnwendungsbeispielGrefenstette (1999), Erläuterung -1-
[Noun => _ [ PAdj | Prep | .#. ] ] hinter einem Nomen steht
ein PAdj (nachgestelltes prädikatives Adjektiv) oder eine Präposition das Ende der Eingabe ist erreicht .#.
22
0 1
?, PAdj,Prep
PAdj,Prep
Noun
A 2: [ Noun _ [PAdj | Prep | .#. ]]
Σ
? Noun PAdj Prep
0 1 0 0
- - 0 0
© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Restriktionsoperator: AnwendungsbeispielGrefenstette (1999), Erläuterung -2-
[ Art | Noun ] [ Art | Noun | PAdj | Prep ] * Art oder Noun, dann dürfen folgen Art | Noun | PAdj | Prep
23
0 1
Art,Noun
Art,Noun,PAdj,Prep
A 5: [ [Art | Noun ] [Art | Noun | PAdj | Prep
Q Σ
Art Noun PAdj Prep
0 1 1 - -
1 fs 1 1 1 1
© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Restriktionsoperator: AnwendungsbeispielGrefenstette (1999), Erläuterung -3-
A9: Schnittbildung der Automaten
[ Art _ [Noun] & [ Noun _ [PAdj | Prep | .#. ] & [ PAdj _ [PAdj | Prep | .#. ] & [ Prep _ [Art | Noun]
24
0 1
?
Art2
Noun
Noun, PAdj
3
Prep
Prep
PAdj
Art
Noun
© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Restriktionsoperator: AnwendungsbeispielGrefenstette (1999), Erläuterung -4-
25
A10: A5 ⋂ A9
Q Σ
A5 A9 A5 A9 A5 A9 A5 A9 A5 A9
A10 A5 A9 Art Art Noun Noun PAdj PAdj Prep Prep ? ?
0 [0 0 f] [1 1] [1 2] [- 2] [- 3] [- 0]
1 [1 f 1 ] [1 -] [1 2] [1 -] [1 -] [- -]
2 f [1 f 2 f] [1 -] [1 -] [1 2] [1 3] [- -]
3 [1 f 3 ] [1 1] [1 2] [1 -] [1 -] [- -]
© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Restriktionsoperator: AnwendungsbeispielGrefenstette (1999), Erläuterung -5-
26
NounGroup = [ [ Art => _ [ Noun ] ] &
[ Noun => _ [ PAdj | Prep | .#. ] ] &
[ PAdj => _ [ PAdj | Prep | .#. ] ] &
[ Prep => _ [ Art | Noun ] ] ] &
[ [ Art | Noun ] [ Art | Noun | PAdj | Prep ] * ] ;
0 1
Art
3Prep
2
NounNoun
PAdj
Art
Noun PAdj
0 1Art
Prep2
NounNounminimieren
© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Themen
Einführung Notationskonventionen Abstrakte Operatoren
Enthaltensein Restriktion Ersetzungen
Theoretische Basis des Ersetzungsoperators: Einschränkung der Mächtigkeit kontextsensitiver Regeln
Anwendungsbeispiele Restriktionsoperator: Parsing Ersetzungsregel: Regelhafte Pluralbildung
27© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Ersetzungsoperator: Anwendungsbeispiel
2828
Jurafsky/Martin, 2000, S. 78
#__^/ szsx
e
r0 r1 r2 r3 r4
r5
s
#
:e^:
z,x
z,s,x
#,other
z,s,x
^:#other ^:s
z,s,x
#,other
#,other
Regel für die Einfügung von –eim Plural der englischen Nomina,die auf x,s,z enden („foxes“)
© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Literatur
Beesley Kenneth R. und Lauri Karttunen (2003). Finite-State Morphology. Distributed for the Center for the Study of Language and Information. 696 p. (est.). 2003 Series: (CSLI-SCL) Studies in Computational Linguistics
Chomsky, Noam and Morris Halle. 1968. The Sound Pattern of English. NewYork: Harper and Row.
Grefenstette, Gregory (1999). Light Parsing as Finite State Filtering. In: Kornai 1999, S. 86-94. frühere Version: In: Workshop on Extended finite state models of language, Budapest, Hungary, Aug 11--12, 1996. ECAI'96." http://citeseer.ist.psu.edu/grefenstette96light.html
Johnson, C. Douglas (1972). Formal Aspects of Phonological Description. Mouton. Jurafsky, Daniel und James H. Martin (2000): Speech and Language Processing. An
Introduction to Natural Language Processing, Computational Linguistics and Speech Recognition. New Jersey: Prentice Hall. S. 21-56.
Kaplan, R. M. and Kay, M. (1981). Phonological rules and finite-state transducers. In Linguistic Society of America Meeting Handbook, Fifty-Sixth Annual Meeting, New York. Abstract.
Kaplan, R. M. and Kay, M. (1994). Regular models of phonological rule systems. In: Computational Linguistics, 20(3):331–378.
29© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Literatur
Karttunen, Lauri (2005). Finite-State Methods in Natural Language Processing. LSA Summer Institute. Lecture Notes, 1 : 18.07.2005, 2 : 20.07.2005, 3 : 25.07.2005, 4 : 27.07.2005, 5 : 01.08.2005, 6 : 03.08.2005- http://www.stanford.edu/~laurik/fsmbook/LSA-207/Slides/LSA2005-Lecture1.ppt- http://www.stanford.edu/~laurik/fsmbook/LSA-207/Slides/LSA2005-Lecture2.ppt - http://www.stanford.edu/~laurik/fsmbook/LSA-207/Slides/LSA2005-Lecture3.ppt
Karttunen, Lauri (1995) . The Replace Operator. In: Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics. ACL-95, S. 16-23, Boston, Massachusetts. http://www.xrce.xerox.com/Publications/Attachments/1995-017/mltt-95-03.pdf
Karttunen, Lauri (1993). Finite-state Constraints. http://www2.parc.com/istl/members/karttune/publications/fsc-91/fsc91.pdf
Karttunen, Lauri und Kenneth R. Beesley (2005). Twenty-Five Years of Finite-State Morphology. In: Antti Arppe, Lauri Carlson, Krister Lindén, Jussi Piitulainen, Mickael Suominen, Martti Vainio, Hanna Westerlund and Anssi Yli-Jyrä (Eds.). Inquiries into Words, Constraints and Contexts. Festschrift for Kimmo Koskenniemi on his 60th Birthday. S. 71-83. http://csli-publications.stanford.edu/koskenniemi-festschrift/8-karttunen-beesley.pdf
30© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Literatur
Karttunen, Lauri; Jean-Pierre Chanod, Gregrory Grefenstette und Anne Schiller (1997). Regular Expressions for Natural Language Engineering. In: Natural Language Engineering, S. 1-24. http://www2.parc.com/istl/members/karttune/publications/jnle-97/rele.pdf
Koskenniemi, K. (1983). Two-level morphology: A general computational model for word-form recognition and production. Publication 11, University of Helsinki, Department of General Linguistics, Helsinki.
Schützenberger, Marcel-Paul. (1961). A remark on finite transducers. Information and Control 4:185–196.
Anssi Yli-Jyrä and Kimmo Koskenniemi (2004). Compiling Contextual Restrictions on Strings into Finite-State Automata. Post-proceedings of Eindhoven Fastar Days, September 3-4, 2004
XEROX Finite State Compiler http://www.xrce.xerox.com/competencies/content-analysis/fsCompiler/fsnetwork.html (nicht mehr unter dieser Adresse online) Download unter http://www.fsmbook.com; auch enthalten auf CD in Beesley/Karttunen 2003, Finite State Morphology (CLSI Publications 2003)
31© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Versionen
5.7.2010, 20.6.2010
32© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010
Copyright
© Karin Haenelt, 2009, 2010All rights reserved. The German Urheberrecht (esp. § 2, § 13, § 63 , etc.). shall be applied to these slides. In accordance with these laws these slides are a publication which may be quoted and used for non-commercial purposes, if the bibliographic data is included as described below.
Please quote correctly. If you use the presentation or parts of it for educational and scientific purposes, please observe the laws (copyright, Urheberrecht, etc.) Please include the bibliographic data (author, title, date, page, URL) in your publication (book, paper, course slides, etc.).
Deletion or omission of the footer (with name, data and copyright sign) is not permitted
Bibliographic data. Karin Haenelt. Komplexe reuläre Ausdrücke. 20.6.2010 (1 15.01.2003) http://kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_KomplexRegEx.pdf
For commercial use: No commercial use is allowed without written permission from the author. In case you are interested in commercial use please contact the author.
Court of Jurisdiction is Darmstadt, Germany
33© Karin Haenelt, Abstrakte Operatoren für komplexe reguläre Ausdrücke 5.7.2010