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

Pierre M. Nugues

Springer, May 11, 2006 - 513 pages

The areas of natural language processing and computational linguistics have continued to grow in recent years, driven by the demand to automatically process text and spoken data. With the processing power and techniques now available, research is scaling up from lab prototypes to real-world, proven applications.This book teaches the principles of natural language processing, first covering linguistics issues such as encoding, entropy, and annotation schemes; defining words, tokens and parts of speech; and morphology. It then details the language-processing functions involved, including part-of-speech tagging using rules and stochastic techniques; using Prolog to write phase-structure grammars; parsing techniques and syntactic formalisms; semantics, predicate logic and lexical semantics; and analysis of discourse, and applications in dialog systems. The key feature of the book is the author's hands-on approach throughout, with extensive exercises, sample code in Prolog and Perl, and a detailed introduction to Prolog. The reader is supported with a companion website that contains teaching slides, programs, and additional material. The book is suitable for researchers and students of natural language processing and computational linguistics.

What people are saying

User Review - -

The book is good for beginners. the book needs more explanation for its concepts

Contents

• An Overview of Language Processing: 1
• 12 Applications of Language Processing: 2
• 13 The Different Domains of Language Processing: 3
• 14 Phonetics: 4
• 15 Lexicon and Morphology: 6
• 16 Syntax: 8
• 162 Syntax as Relations and Dependencies: 10
• 17 Semantics: 11
• 18 Discourse and Dialogue: 14
• 191 Ambiguity: 15
• 192 Models and Their Implementation: 16
• the Persona Project: 17
• 1102 The Personas Modules: 18
• 111 Further Reading: 19
• Corpus Processing Tools: 23
• 212 Corpora and Lexicon Building: 24
• 213 Corpora as Knowledge Sources for the Linguist: 26
• 22 FiniteState Automata: 27
• 222 Mathematical Definition of FiniteState Automata: 28
• 223 FiniteState Automata in Prolog: 29
• 224 Deterministic and Nondeterministic Automata: 30
• 225 Building a Deterministic Automata from a Nondeterministic One: 31
• 227 Operations on FiniteState Automata: 33
• 23 Regular Expressions: 35
• 231 Repetition Metacharacters: 36
• 232 The Longest Match: 37
• 233 Character Classes: 38
• 234 Nonprintable Symbols or Positions: 39
• 235 Union and Boolean Operators: 41
• 24 Programming with Regular Expressions: 42
• 243 Substitutions: 43
• 244 Translating Characters: 44
• 246 Back References: 45
• 25 Finding Concordances: 46
• 252 Concordances in Perl: 48
• 26 Approximate String Matching: 50
• 262 Minimum Edit Distance: 51
• 263 Searching Edits in Prolog: 54
• 27 Further Reading: 55
• Encoding Entropy and Annotation Schemes: 58
• 32 Character Sets: 60
• 322 Unicode: 61
• 323 The Unicode Encoding Schemes: 63
• 33 Locales and Word Order: 66
• 332 The Unicode Collation Algorithm: 67
• 34 Markup Languages: 69
• 343 Writing a DTD: 71
• 344 Writing an XML Document: 74
• 345 Namespaces: 75
• 35 Codes and Information Theory: 76
• 352 Huffman Encoding: 77
• 353 Cross Entropy: 80
• 354 Perplexity and Cross Perplexity: 81
• 36 Entropy and Decision Trees: 82
• 37 Further Reading: 84
• Counting Words: 87
• Tokenization: 88
• 43 Tokenizing Texts: 89
• 432 Tokenizing Texts in Perl: 91
• 44 Ngrams: 92
• 442 Counting Unigrams in Prolog: 93
• 444 Counting Bigrams with Perl: 95
• 452 Using ML Estimates with Nineteen EightyFour: 97
• 46 Smoothing Ngram Probabilities: 99
• 462 Laplaces Rule: 100
• 463 GoodTuring Estimation: 101
• 47 Using Ngrams of Variable Length: 102
• 471 Linear Interpolation: 103
• 472 Backoff: 104
• 482 Entropy Rate: 105
• 484 Perplexity: 106
• 491 Word Preference Measurements: 107
• 492 Extracting Collocations with Perl: 108
• Retrieval and Ranking of Documents on the Web: 109
• 411 Further Reading: 111
• Words Parts of Speech and Morphology: 113
• 512 Features: 114
• The Noun and the Verb: 115
• 52 Lexicons: 117
• 521 Encoding a Dictionary: 119
• 522 Building a Trie in Prolog: 121
• 523 Finding a Word in a Trie: 123
• 532 Morphs: 124
• 533 Inflection and Derivation: 125
• 534 Language Differences: 129
• 54 Morphological Parsing: 130
• 542 Interpreting the Morphs: 131
• 544 Conjugating a French Verb: 133
• 545 Prolog Implementation: 134
• 546 Ambiguity: 136
• 547 Operations on FiniteState Transducers: 137
• 55 Morphological Rules: 138
• 552 Rules and FiniteState Transducers: 139
• An Example with French Irregular Verbs: 141
• 56 Application Examples: 142
• PartofSpeech Tagging Using Rules: 146
• 62 Tagging with Rules: 149
• 622 Implementation in Prolog: 151
• 623 Deriving Rules Automatically: 153
• 624 Confusion Matrices: 154
• 64 Standardized PartofSpeech Tagsets: 156
• 642 Parts of Speech for English: 158
• 643 An Annotation Scheme for Swedish: 160
• 65 Further Reading: 162
• PartofSpeech Tagging Using Stochastic Techniques: 163
• 712 The TVgram Approximation: 164
• 713 Tagging a Sentence: 165
• An Intuitive Presentation: 166
• 72 Markov Models: 167
• 722 Hidden Markov Models: 169
• 723 Three Fundamental Algorithms to Solve Problems with HMMs: 170
• 724 The Forward Procedure: 171
• 725 Viterbi Algorithm: 173
• 726 The Backward Procedure: 174
• 727 The ForwardBackward Algorithm: 175
• 73 Tagging with Decision Trees: 177
• 74 Unknown Words: 179
• Language Models for Machine Translation: 180
• 762 Alignment: 181
• 763 Translation: 183
• 77 Further Reading: 184
• PhraseStructure Grammars in Prolog: 185
• 822 Tree Structures: 186
• 823 PhraseStructure Rules: 187
• 824 The Definite Clause Grammar DCG Notation: 188
• 83 Parsing with DCGs: 190
• 832 Parsing and Generation: 192
• 833 LeftRecursive Rules: 193
• 84 Parsing Ambiguity: 194
• 85 Using Variables: 196
• 852 Obtaining the Syntactic Structure: 198
• Tokenizing Texts Using DCG Rules: 200
• 862 Recognition of Sentence Boundaries: 201
• 87 Semantic Representation: 202
• 872 Embedding λExpressions into DCG Rules: 203
• 873 Semantic Composition of Verbs: 205
• 88 An Application of PhraseStructure Grammars and a Worked Example: 206
• 89 Further Reading: 210
• Partial Parsing: 213
• 922 Word Spotting in Prolog: 214
• 93 Multiword Detection: 217
• 933 Detecting Multiwords with Rules: 219
• 935 Running the Program: 220
• 94 Noun Groups and Verb Groups: 222
• 941 Groups Versus Recursive Phrases: 223
• 943 DCG Rules to Detect Verb Groups: 225
• 944 Running the Rules: 226
• 95 Group Detection as a Tagging Problem: 227
• 952 Tagging Words: 228
• 953 Using Symbolic Rules: 229
• 96 Cascading Partial Parsers: 230
• 97 Elementary Analysis of Grammatical Functions: 231
• 972 Extracting Other Groups: 232
• 98 An Annotation Scheme for Groups in French: 235
• The FASTUS System: 237
• 992 The Syntactic Layers of the FASTUS System: 238
• 993 Evaluation of Information Extraction Systems: 239
• 910 Further Reading: 240
• Syntactic Formalisms: 243
• 102 Chomskys Grammar in Syntactic Structures: 244
• 1022 Transformations: 246
• 1023 Transformations and Movements: 248
• 1025 Gap Threading to Parse Relative Clauses: 250
• 103 Standardized Phrase Categories for English: 252
• 104 UnificationBased Grammars: 254
• 1042 Representing Features in Prolog: 255
• 1043 A Formalism for Features and Rules: 257
• 1044 Features Organization: 258
• 1045 Features and Unification: 260
• 1046 A Unification Algorithm for Feature Structures: 261
• 105 Dependency Grammars: 263
• 1052 Properties of a Dependency Graph: 266
• 1053 Valence: 268
• 1054 Dependencies and Functions: 270
• 106 Further Reading: 273
• Exercises: 274
• Parsing Techniques: 276
• 112 Bottomup Parsing: 278
• 1122 Implementing ShiftReduce Parsing in Prolog: 279
• 1123 Differences Between Bottomup and Topdown Parsing: 281
• 113 Chart Parsing: 282
• 1133 The Active Chart: 283
• 1134 Modules of an Earley Parser: 285
• 1135 The Earley Algorithm in Prolog: 288
• 1136 The Earley Parser to Handle LeftRecursive Rules and Empty Symbols: 293
• 114 Probabilistic Parsing of ContextFree Grammars: 294
• 1151 The Bottomup Chart: 297
• 1152 The CockeYoungerKasami Algorithm in Prolog: 298
• 1153 Adding Probabilities to the CYK Parser: 300
• 116 Parser Evaluation: 301
• 1162 DependencyBased Evaluation: 302
• 117 Parsing Dependencies: 303
• 1171 Dependency Rules: 304
• 1172 Extending the ShiftReduce Algorithm to Parse Dependencies: 305
• 1173 Nivres Parser in Prolog: 306
• 1174 Finding Dependencies Using Constraints: 309
• 1175 Parsing Dependencies Using Statistical Techniques: 310
• 118 Further Reading: 313
• Semantics and Predicate Logic: 317
• 123 Formal Semantics: 319
• 1241 Variables and Constants: 320
• 125 Querying the Universe of Discourse: 322
• 1261 Representing Nouns and Adjectives: 323
• 1262 Representing Noun Groups: 324
• 127 The Case of Determiners: 325
• 1272 Translating Sentences Using Quantifiers: 326
• 1273 A General Representation of Sentences: 327
• 128 Compositionality to Translate Phrases to Logical Forms: 329
• 1282 Translating the Verb Phrase: 330
• 129 Augmenting the Database and Answering Questions: 331
• 1291 Declarations: 332
• 1293 Prolog and Unknown Predicates: 334
• 1294 Other Determiners and Questions: 335
• 12102 Compositional Semantics: 336
• 12103 Semantic Representation Transfer: 338
• 1211 Further Reading: 340
• Lexical Semantics: 342
• 132 Lexical Structures: 344
• 1323 Lexical Classes and Relations: 345
• 1324 Semantic Networks: 347
• 1331 The Lexicon and Word Senses: 349
• 1332 Verb Models: 350
• 1333 Definitions: 351
• WordNet: 352
• 1341 Nouns: 353
• 1342 Adjectives: 354
• 1343 Verbs: 355
• 135 Automatic Word Sense Disambiguation: 356
• 1352 Associating a Word with a Context: 357
• 1354 Naïve Bayes: 358
• 1355 Using Constraints on Verbs: 359
• 1357 An Unsupervised Algorithm to Tag Senses: 360
• 1358 Senses and Languages: 362
• 136 Case Grammars: 363
• 1362 Cases and Thematic Roles: 364
• 1363 Parsing with Cases: 365
• 1364 Semantic Grammars: 366
• 137 Extending Case Grammars: 367
• 1372 A Statistical Method to Identify Semantic Roles: 368
• EVAR: 371
• 1382 Cases in EVAR: 373
• Discourse: 377
• A Minimalist Definition: 378
• An ApplicationOriented View: 379
• 1432 Finding Names Proper Nouns: 380
• 144 Coreference: 381
• 1442 Solving Coreferences in an Example: 382
• 1443 A Standard Coreference Annotation: 383
• A More Formal View: 384
• Definite Descriptions: 385
• The Universal Quantifier: 386
• A Theory on Discourse Structure: 387
• 147 Solving Coreferences: 388
• Using Syntactic and Semantic Compatibility: 389
• 1472 Solving Coreferences with Shallow Grammatical Information: 390
• 1473 Salience in a Multimodal Context: 391
• Ellipses: 396
• An Outline: 397
• 1483 Types of Relations: 399
• 1484 Implementing Rhetorical Structure Theory: 400
• 149 Events and Time: 401
• 1491 Events: 403
• 1492 Event Types: 404
• 1494 Events and Tenses: 406
• 1410 TimeML an Annotation Scheme for Time and Events: 407
• 1411 Further Reading: 409
• Dialogue: 411
• 153 Simple Dialogue Systems: 412
• 1532 Dialogue Modeling: 413
• A Theory of Language Interaction: 414
• 155 Speech Acts and HumanMachine Dialogue: 417
• 1552 Speech Acts Tags Used in the SUNDIAL Project: 418
• 1553 Dialogue Parsing: 419
• 1554 Interpreting Speech Acts: 421
• A Dialogue Application Using Speech Acts: 422
• 156 Taking Beliefs and Intentions into Account: 423
• 1561 Representing Mental States: 425
• 1562 The STRIPS Planning Algorithm: 427
• 1563 Causality: 429
• 157 Further Reading: 430
• An Introduction to Prolog: 432
• A2 Basic Features of Prolog: 434
• A22 Terms: 435
• A23 Queries: 437
• A25 Shared Variables: 438
• A26 Data Types in Prolog: 439
• A27 Rules: 440
• A3 Running a Program: 442
• A4 Unification: 443
• A42 Terms and Unification: 444
• A43 The Herbrand Unification Algorithm: 445
• A45 The OccursCheck: 446
• A5 Resolution: 447
• A53 Derivation Trees and Backtracking: 448
• A6 Tracing and Debugging: 450
• A7 Cuts Negation and Related Predicates: 452
• A72 Negation: 453
• A73 The once1 Predicate: 454
• A8 Lists: 455
• A9 Some ListHandling Predicates: 456
• A92 The append3 Predicate: 457
• A93 The delete3 Predicate: 458
• A95 The reverse2 Predicate: 459
• A10 Operators and Arithmetic: 460
• A103 Comparison Operators: 462
• The length2 Predicate: 463
• A11 Some Other Builtin Predicates: 464
• A112 Term Manipulation Predicates: 465
• A12 Handling RunTime Errors and Exceptions: 466
• A13 Dynamically Accessing and Updating the Database: 467
• A132 Dynamic and Static Predicates: 468
• The retract1 and abolish2 Predicates: 469
• A135 Handling Unknown Predicates: 470
• A15 Fundamental Search Algorithms: 471
• A151 Representing the Graph: 472
• A152 DepthFirst Search: 473
• A153 BreadthFirst Search: 474
• A154 A Search: 475
• A16 InputOutput: 476
• A163 Opening and Closing Files with Edinburgh Prolog: 477
• A164 Reading and Writing Characters with Standard Prolog: 478
• A165 Reading and Writing Terms with Standard Prolog: 479
• A167 Writing Loops: 480
• A17 Developing Prolog Programs: 481
• A172 Improving Programs: 482
• Index: 487
• References: 497

About the author

Pierre Nugues’ research is focused on natural language processing for advanced user interfaces and spoken dialogue. This includes the design and the implementation of conversational agents within a multimodal framework and text visualization. He led the team that designed a navigation agent - Ulysse - that enables a user to navigate in a virtual reality environment using language, and the team that designed the CarSim system that generates animated 3D scenes from written texts. Pierre Nugues has taught natural-language processing and computational linguistics at the following institutions: ISMRA, Caen, France; University of Nottigham, UK; Staffordshire University, UK; FH Konstanz, Germany; Lund University, Sweden; and Ghent University, Belgium.

Bibliographic information

• Title: An Introduction to Language Processing with Perl and Prolog: An Outline of Theories, Implementation, and Application with Special Consideration of English, French, and German; Cognitive Technologies
• Author: Pierre M. Nugues
• Edition: illustrated
• Publisher: Springer, 2006
• ISBN: 354025031X, 9783540250319
• Length: 513 pages
• Subjects: Artificial intelligence; Computational linguistics; Computer science; Computers / Digital Media / Desktop Publishing; Computers / Document Management; Computers / Intelligence (AI) & Semantics; Computers / Natural Language Processing; Computers / Programming / General; Computers / Programming Languages / General; Computers / Programming Languages / Perl; Computers / Programming Languages / Prolog; Electronic books; Language Arts & Disciplines / Linguistics / General; Natural language processing (Computer science); Perl (Computer program language); Prolog (Computer program language); Text processing (Translators (Computer programs)