An Introduction to Language Processing with Perl and Prolog: An Outline of Theories, Implementation, and Application with Special Consideration of English, French, and German

Contents......Page 8
1.1 Linguistics and Language Processing......Page 20
1.2 Applications of Language Processing......Page 21
1.3 The Different Domains of Language Processing......Page 22
1.4 Phonetics......Page 23
1.5 Lexicon and Morphology......Page 25
1.6.1 Syntax as Defined by Noam Chomsky......Page 27
1.6.2 Syntax as Relations and Dependencies......Page 29
1.7 Semantics......Page 30
1.9 Why Speech and Language Processing Are Difficult......Page 33
1.9.1 Ambiguity......Page 34
1.9.2 Models and Their Implementation......Page 35
1.10.1 Overview of Persona......Page 36
1.10.2 The Persona\'s Modules......Page 37
1.11 Further Reading......Page 38
2.1.1 Types of Corpora......Page 42
2.1.2 Corpora and Lexicon Building......Page 43
2.1.3 Corpora as Knowledge Sources for the Linguist......Page 45
2.2.1 A Description......Page 46
2.2.2 Mathematical Definition of Finite-State Automata......Page 47
2.2.3 Finite-State Automata in Prolog......Page 48
2.2.4 Deterministic and Nondeterministic Automata......Page 49
2.2.6 Searching a String with a Finite-State Automaton......Page 50
2.2.7 Operations on Finite-State Automata......Page 52
2.3 Regular Expressions......Page 54
2.3.1 Repetition Metacharacters......Page 55
2.3.2 The Longest Match......Page 56
2.3.3 Character Classes......Page 57
2.3.4 Nonprintable Symbols or Positions......Page 58
2.3.6 Operator Combination and Precedence......Page 60
2.4.2 Matching......Page 61
2.4.3 Substitutions......Page 62
2.4.5 String Operators......Page 63
2.4.6 Back References......Page 64
2.5.1 Concordances in Prolog......Page 65
2.5.2 Concordances in Perl......Page 67
2.6.1 Edit Operations......Page 69
2.6.2 Minimum Edit Distance......Page 70
2.6.3 Searching Edits in Prolog......Page 73
2.7 Further Reading......Page 74
3.1 Encoding Texts......Page 77
3.2.1 Representing Characters......Page 78
3.2.2 Unicode......Page 79
3.2.3 The Unicode Encoding Schemes......Page 81
3.3.1 Presenting Time, Numerical Information, and Ordered Words......Page 84
3.3.2 The Unicode Collation Algorithm......Page 85
3.4.2 An Outline of XML......Page 87
3.4.3 Writing a DTD......Page 89
3.4.4 Writing an XML Document......Page 92
3.4.5 Namespaces......Page 93
3.5.1 Entropy......Page 94
3.5.2 Huffman Encoding......Page 95
3.5.3 Cross Entropy......Page 98
3.5.4 Perplexity and Cross Perplexity......Page 99
3.6.2 Inducing Decision Trees Automatically......Page 100
3.7 Further Reading......Page 102
4.2.1 What Is a Word?......Page 104
4.2.2 Breaking a Text into Words: Tokenization......Page 105
4.3.1 Tokenizing Texts in Prolog......Page 106
4.3.2 Tokenizing Texts in Perl......Page 108
4.4.1 Some Definitions......Page 109
4.4.3 Counting Unigrams with Perl......Page 110
4.5.1 The Maximum Likelihood Estimation......Page 112
4.5.2 Using ML Estimates with Nineteen Eighty-Four......Page 114
4.6.1 Sparse Data......Page 116
4.6.2 Laplace\'s Rule......Page 117
4.6.3 Good–Turing Estimation......Page 118
4.7 Using N-grams of Variable Length......Page 119
4.7.1 Linear Interpolation......Page 120
4.8.1 Intuitive Presentation......Page 121
4.8.3 Cross Entropy......Page 122
4.9 Collocations......Page 123
4.9.1 Word Preference Measurements......Page 124
4.9.2 Extracting Collocations with Perl......Page 125
4.10 Application: Retrieval and Ranking of Documents on the Web......Page 126
4.11 Further Reading......Page 128
5.1.1 Parts of Speech......Page 130
5.1.2 Features......Page 131
5.1.3 Two Signifficant Parts of Speech: The Noun and the Verb......Page 132
5.2 Lexicons......Page 134
5.2.1 Encoding a Dictionary......Page 136
5.2.2 Building a Trie in Prolog......Page 138
5.3.1 Morphemes......Page 140
5.3.2 Morphs......Page 141
5.3.3 Inffection and Derivation......Page 142
5.3.4 Language Differences......Page 146
5.4.1 Two-Level Model of Morphology......Page 147
5.4.3 Finite-State Transducers......Page 148
5.4.4 Conjugating a French Verb......Page 150
5.4.5 Prolog Implementation......Page 151
5.4.6 Ambiguity......Page 153
5.4.7 Operations on Finite-State Transducers......Page 154
5.5.1 Two-Level Rules......Page 155
5.5.2 Rules and Finite-State Transducers......Page 156
5.5.3 Rule Composition: An Example with French Irregular Verbs......Page 158
5.7 Further Reading......Page 159
6.1.2 Which Method to Use to Automatically Assign Parts of Speech......Page 163
6.2.1 Brill\'s Tagger......Page 165
6.2.2 Implementation in Prolog......Page 167
6.2.3 Deriving Rules Automatically......Page 169
6.3 Unknown Words......Page 170
6.4.1 Multilingual Part-of-Speech Tags......Page 172
6.4.2 Parts of Speech for English......Page 174
6.4.3 An Annotation Scheme for Swedish......Page 176
6.5 Further Reading......Page 178
7.1.1 Presentation......Page 179
7.1.2 The N-gram Approximation......Page 180
7.1.3 Tagging a Sentence......Page 181
7.1.4 The Viterbi Algorithm: An Intuitive Presentation......Page 182
7.2.1 Markov Chains......Page 183
7.2.2 Hidden Markov Models......Page 185
7.2.3 Three Fundamental Algorithms to Solve Problems with HMMs......Page 186
7.2.4 The Forward Procedure......Page 187
7.2.5 Viterbi Algorithm......Page 189
7.2.6 The Backward Procedure......Page 190
7.2.7 The Forward–Backward Algorithm......Page 191
7.3 Tagging with Decision Trees......Page 193
7.5 An Application of the Noisy Channel Model: Spell Checking......Page 195
7.6.1 Parallel Corpora......Page 196
7.6.2 Alignment......Page 197
7.6.3 Translation......Page 199
7.7 Further Reading......Page 200
8.2.1 Constituents......Page 201
8.2.2 Tree Structures......Page 202
8.2.3 Phrase-Structure Rules......Page 203
8.2.4 The Definite Clause Grammar (DCG) Notation......Page 204
8.3.1 Translating DCGs into Prolog Clauses......Page 206
8.3.2 Parsing and Generation......Page 208
8.3.3 Left-Recursive Rules......Page 209
8.4 Parsing Ambiguity......Page 210
8.5.1 Gender and Number Agreement......Page 212
8.5.2 Obtaining the Syntactic Structure......Page 214
8.6.1 Word Breaking......Page 216
8.6.2 Recognition of Sentence Boundaries......Page 217
8.7.1 λ-Calculus......Page 218
8.7.2 Embedding λ-Expressions into DCG Rules......Page 219
8.7.3 Semantic Composition of Verbs......Page 221
8.8 An Application of Phrase-Structure Grammars and a Worked Example......Page 222
8.9 Further Reading......Page 226
9.2.1 ELIZA......Page 228
9.2.2 Word Spotting in Prolog......Page 229
9.3.2 A Standard Multiword Annotation......Page 232
9.3.4 The Longest Match......Page 234
9.3.5 Running the Program......Page 235
9.4 Noun Groups and Verb Groups......Page 237
9.4.2 DCG Rules to Detect Noun Groups......Page 238
9.4.3 DCG Rules to Detect Verb Groups......Page 240
9.4.4 Running the Rules......Page 241
9.5.1 Tagging Gaps......Page 242
9.5.2 Tagging Words......Page 243
9.5.4 Using Statistical Tagging......Page 244
9.6 Cascading Partial Parsers......Page 245
9.7.1 Main Functions......Page 246
9.7.2 Extracting Other Groups......Page 247
9.8 An Annotation Scheme for Groups in French......Page 250
9.9.1 The Message Understanding Conferences......Page 252
9.9.2 The Syntactic Layers of the FASTUS System......Page 253
9.9.3 Evaluation of Information Extraction Systems......Page 254
9.10 Further Reading......Page 255
10.1 Introduction......Page 258
10.2.1 Constituency: A Formal Definition......Page 259
10.2.2 Transformations......Page 261
10.2.4 Gap Threading......Page 263
10.2.5 Gap Threading to Parse Relative Clauses......Page 265
10.3 Standardized Phrase Categories for English......Page 267
10.4.1 Features......Page 269
10.4.2 Representing Features in Prolog......Page 270
10.4.3 A Formalismfor Features and Rules......Page 272
10.4.4 Features Organization......Page 273
10.4.5 Features and Unification......Page 275
10.4.6 A Unification Algorithm for Feature Structures......Page 276
10.5.1 Presentation......Page 278
10.5.2 Properties of a Dependency Graph......Page 281
10.5.3 Valence......Page 283
10.5.4 Dependencies and Functions......Page 285
10.6 Further Reading......Page 288
11.1 Introduction......Page 291
11.2.1 The Shift–Reduce Algorithm......Page 292
11.2.2 Implementing Shift–Reduce Parsing in Prolog......Page 293
11.2.3 Differences Between Bottom-up and Top-down Parsing......Page 295
11.3.2 Structure of a Chart......Page 296
11.3.3 The Active Chart......Page 297
11.3.4 Modules of an Earley Parser......Page 299
11.3.5 The Earley Algorithm in Prolog......Page 302
11.3.6 The Earley Parser to Handle Left-Recursive Rules and Empty Symbols......Page 307
11.5 A Description of PCFGs......Page 308
11.5.1 The Bottom-up Chart......Page 311
11.5.2 The Cocke–Younger–Kasami Algorithm in Prolog......Page 312
11.5.3 Adding Probabilities to the CYK Parser......Page 314
11.6.1 Constituency-Based Evaluation......Page 315
11.6.3 Performance of PCFG Parsing......Page 316
11.7 Parsing Dependencies......Page 317
11.7.1 Dependency Rules......Page 318
11.7.2 Extending the Shift–Reduce Algorithm to Parse Dependencies......Page 319
11.7.3 Nivre\'s Parser in Prolog......Page 320
11.7.4 Finding Dependencies Using Constraints......Page 323
11.7.5 Parsing Dependencies Using Statistical Techniques......Page 324
11.8 Further Reading......Page 327
12.2 Language Meaning and Logic: An Illustrative Example......Page 330
12.4 First-Order Predicate Calculus to Represent the State of Affairs......Page 332
12.4.2 Predicates......Page 333
12.6 Mapping Phrases onto Logical Formulas......Page 335
12.6.1 Representing Nouns and Adjectives......Page 336
12.6.3 Representing Verbs and Prepositions......Page 337
12.7.1 Determiners and Logic Quantifiers......Page 338
12.7.2 Translating Sentences Using Quantifiers......Page 339
12.7.3 A General Representation of Sentences......Page 340
12.8.1 Translating the Noun Phrase......Page 342
12.8.2 Translating the Verb Phrase......Page 343
12.9 Augmenting the Database and Answering Questions......Page 344
12.9.2 Questions with Existential and Universal Quantifiers......Page 345
12.9.3 Prolog and Unknown Predicates......Page 347
12.10.1 Translating Spoken Sentences......Page 348
12.10.2 Compositional Semantics......Page 349
12.10.3 Semantic Representation Transfer......Page 351
12.11 Further Reading......Page 353
13.1.2 Language and the Structure of the World......Page 355
13.2.2 Ontological Organization......Page 356
13.2.3 Lexical Classes and Relations......Page 357
13.3 Building a Lexicon......Page 359
13.3.1 The Lexicon and Word Senses......Page 361
13.3.2 Verb Models......Page 362
13.3.3 Definitions......Page 363
13.4 An Example of Exhaustive Lexical Organization: WordNet......Page 364
13.4.1 Nouns......Page 365
13.4.2 Adjectives......Page 366
13.4.3 Verbs......Page 367
13.5.1 Senses as Tags......Page 368
13.5.3 Guessing the Topic......Page 369
13.5.4 Naïve Bayes......Page 370
13.5.6 Using Dictionary Definitions......Page 371
13.5.7 An Unsupervised Algorithm to Tag Senses......Page 372
13.5.8 Senses and Languages......Page 374
13.6.1 Cases in Latin......Page 375
13.6.2 Cases and Thematic Roles......Page 376
13.6.3 Parsing with Cases......Page 377
13.6.4 Semantic Grammars......Page 378
13.7.1 FrameNet......Page 379
13.7.2 A Statistical Method to Identify Semantic Roles......Page 380
13.8.1 EVAR\'s Ontology and Syntactic Classes......Page 383
13.9 Further Reading......Page 385
14.1 Introduction......Page 388
14.2.2 Discourse Entities......Page 389
14.3.1 References and Noun Phrases......Page 390
14.3.2 Finding Names – Proper Nouns......Page 391
14.4.1 Anaphora......Page 392
14.4.2 Solving Coreferences in an Example......Page 393
14.4.3 A Standard Coreference Annotation......Page 394
14.5.1 Generating Discourse Entities: The Existential Quantifier......Page 395
14.5.2 Retrieving Discourse Entities: Definite Descriptions......Page 396
14.5.3 Generating Discourse Entities: The Universal Quantifier......Page 397
14.6 Centering: A Theory on Discourse Structure......Page 398
14.7 Solving Coreferences......Page 399
14.7.1 A Simplistic Method: Using Syntactic and Semantic Compatibility......Page 400
14.7.2 Solving Coreferences with Shallow Grammatical Information......Page 401
14.7.4 Using a Machine-Learning Technique to Resolve Coreferences......Page 402
14.8 Discourse and Rhetoric......Page 407
14.8.2 Rhetorical Structure Theory......Page 408
14.8.3 Types of Relations......Page 410
14.8.4 Implementing Rhetorical Structure Theory......Page 411
14.9 Events and Time......Page 412
14.9.1 Events......Page 414
14.9.3 Temporal Representation of Events......Page 415
14.9.4 Events and Tenses......Page 417
14.10 TimeML, an Annotation Scheme for Time and Events......Page 418
14.11 Further Reading......Page 420
15.2 Why a Dialogue?......Page 422
15.3.1 Dialogue Systems Based on Automata......Page 423
15.3.2 Dialogue Modeling......Page 424
15.4 Speech Acts: A Theory of Language Interaction......Page 425
15.5.1 Speech Acts as a Tagging Model......Page 428
15.5.2 Speech Acts Tags Used in the SUNDIAL Project......Page 429
15.5.3 Dialogue Parsing......Page 430
15.5.4 Interpreting Speech Acts......Page 432
15.5.5 EVAR: A Dialogue Application Using Speech Acts......Page 433
15.6 Taking Beliefs and Intentions into Account......Page 434
15.6.1 Representing Mental States......Page 436
15.6.2 The STRIPS Planning Algorithm......Page 438
15.6.3 Causality......Page 440
15.7 Further Reading......Page 441
A.1 A Short Background......Page 443
A.2.1 Facts......Page 444
A.2.2 Terms......Page 445
A.2.4 Logical Variables......Page 447
A.2.5 Shared Variables......Page 448
A.2.6 Data Types in Prolog......Page 449
A.2.7 Rules......Page 450
A.3 Running a Program......Page 452
A.4.1 Substitution and Instances......Page 453
A.4.2 Terms and Unification......Page 454
A.4.4 Example......Page 455
A.4.5 The Occurs-Check......Page 456
A.5.2 A Resolution Algorithm......Page 457
A.5.3 Derivation Trees and Backtracking......Page 458
A.6 Tracing and Debugging......Page 460
A.7.1 Cuts......Page 462
A.7.2 Negation......Page 463
A.7.3 The once/1 Predicate......Page 464
A.8 Lists......Page 465
A.9.1 The member/2 Predicate......Page 466
A.9.2 The append/3 Predicate......Page 467
A.9.4 The intersection/3 Predicate......Page 468
A.9.6 The Mode of an Argument......Page 469
A.10.2 Arithmetic Operations......Page 470
A.10.3 Comparison Operators......Page 472
A.10.5 Lists and Comparison: The quicksort/2 Predicate......Page 473
A.11.1 Type Predicates......Page 474
A.11.2 Term Manipulation Predicates......Page 475
A.12 Handling Run-Time Errors and Exceptions......Page 476
A.13.1 Accessing a Clause: The  clause/2 Predicate......Page 477
A.13.3 Adding a Clause: The asserta/1 and assertz/1 Predicates......Page 478
A.13.4 Removing Clauses: The retract/1 and  abolish/2 Predicates......Page 479
A.14 All-Solutions Predicates......Page 480
A.15 Fundamental Search Algorithms......Page 481
A.15.1 Representing the Graph......Page 482
A.15.2 Depth-First Search......Page 483
A.15.3 Breadth-First Search......Page 484
A.15.4 A* Search......Page 485
A.16.2 Reading and Writing Terms with Edinburgh Prolog......Page 486
A.16.3 Opening and Closing Files with Edinburgh Prolog......Page 487
A.16.4 Reading and Writing Characters with Standard Prolog......Page 488
A.16.6 Opening and Closing Files with Standard Prolog......Page 489
A.16.7 Writing Loops......Page 490
A.17.1 Presentation Style......Page 491
A.17.2 Improving Programs......Page 492
B......Page 497
C......Page 498
F......Page 499
J......Page 500
M......Page 501
P......Page 502
R......Page 503
T......Page 504
X......Page 505
Z......Page 506
References......Page 507