Analyzing Shakespearean Plays for Specific Keywords
The content delves into the exploration of Shakespearean plays to identify instances where specific keywords like Brutus, Caesar, and Calpurnia are mentioned. It discusses techniques such as Boolean retrieval for efficient querying and examines excerpts from Antony and Cleopatra, Julius Caesar, and Hamlet. Additionally, it touches upon the challenges of handling unstructured data and proposes solutions for optimized text search operations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Unstructured data in 1600 In the Shakespeare s book; Which plays of Shakespeare contain the words Brutus AND Caesar but NOT Calpurnia? Answer: One could grep (in Linux command line: <comamand> | grep < search-tex>) all of Shakespeare s plays for Brutus and Caesar, then strip out lines containing Calpurnia? Is it good today?
Unstructured data Why is that not the answer? Slow (for large corpora: The amount of online data has grown at least as quickly as the speed of computers ) NOT Calpurnia is non-trivial Other operations (e.g., find the word Romans near countrymen) not feasible Ranked retrieval (best documents to return) Later lectures Solution: The way to avoid linearly scanning the texts for each queries to index the documents in advance.
Term-document incidence matrix Antony and Cleopatra Julius Caesar The Tempest Hamlet Othello Macbeth 1 1 0 0 0 1 Antony 1 1 0 1 0 0 Brutus 1 1 0 1 1 1 Caesar 0 1 0 0 0 0 Calpurnia 1 0 0 0 0 0 Cleopatra 1 0 1 1 1 1 mercy 1 0 1 1 1 0 worser
Incidence vectors So we have a 0/1 vector for each term (in row). To answer query: take the vectors for Brutus, Caesar and Calpurnia (complemented) bitwise AND. 110100 AND 110111 AND 101111 = 100100 Calpurnia 0 1 Antony and Cleopatra Julius Caesar The Tempest Hamlet Othello Macbeth 1 1 0 0 0 1 Antony 1 1 0 1 0 0 Brutus 1 1 0 1 1 1 Caesar 1 0 0 0 0 0 0 0 0 0 Cleopatra 1 0 1 1 1 1 mercy 1 0 1 1 1 0 worser
Answers to query Antony and Cleopatra, Act III, Scene ii Agrippa [Aside to DOMITIUS ENOBARBUS]: Why, Enobarbus, When Antony found Julius Caesardead, He cried almost to roaring; and he wept When at Philippi he found Brutus slain. Hamlet, Act III, Scene ii Lord Polonius: I did enact Julius Caesar I was killed i the Capitol; Brutus killed me.
Boolean Retrieval The Boolean retrieval model is a model for information BOOLEAN RETRIEVAL retrieval in which we MODEL, can pose any query which is in the form of a Boolean expression of terms, that is, in which terms are combined with the operators AND, OR, and NOT.
Boolean Retrieval In other words, this function is considered here: Where is the term query, a finite string provided by a user, is the result that retrieves from the repository.
The classic search model TASK Get rid of mice in a politically correct way Misconception? Info about removing mice without killing them Info Need Mistranslation? Verbal form How do I trap mice alive? Misformulation? Query mouse trap SEARCH ENGINE Query Refinement Results Corpus
Sec. 1.2 Inverted index For each term t, we must store a list of all documents that contain t. Identify each by a docID, a document serial number Can we used fixed-size arrays for this? Brutus 1 2 4 11 31 45 173 174 Caesar 1 2 4 5 6 16 57 132 Calpurnia 2 31 54 101 What happens if the word Caesar is added to document 14? 10
Sec. 1.2 Inverted index construction Documents to be indexed. Friends, Romans, countrymen. Tokenizer Friends Romans Countrymen Token stream. More on these later. Linguistic modules friend roman countryman Modified tokens. 2 4 Indexer friend 1 2 roman Inverted index. 16 13 countryman
Sec. 1.2 Indexer steps: Token sequence Sequence of (Modified token, Document ID) pairs. Doc 1 Doc 2 I did enact Julius Caesar I was killed i' the Capitol; Brutus killed me. So let it be with Caesar. The noble Brutus hath told you Caesar was ambitious
Sec. 1.2 Indexer steps: Sort Sort by terms And then docID Core indexing step
Sec. 1.2 Indexer steps: Dictionary & Postings Multiple term entries in a single document are merged. Split into Dictionary and Postings Doc. frequency information is added. Why frequency? Will discuss later.
Sec. 1.2 Where do we pay in storage? Lists of docIDs Terms and counts Later in the course: How do we index efficiently? How much storage do we need? Pointers 15
Sec. 1.3 Query processing: AND Consider processing the query: BrutusANDCaesar Locate Brutus in the Dictionary; Retrieve its postings. Locate Caesar in the Dictionary; Retrieve its postings. Merge the two postings: 2 4 8 16 32 64 128 Brutus Brutus Caesar Caesar 1 2 3 5 8 13 21 34 16
Sec. 1.3 The merge Walk through the two postings simultaneously, in time linear in the total number of postings entries 2 2 4 4 8 8 16 16 32 32 64 64 128 128 Brutus Brutus 2 8 Caesar Caesar 1 1 2 2 3 3 5 5 8 8 13 13 21 21 34 34 If the list lengths are x and y, the merge takes O(x+y) operations. Crucial: postings sorted by docID. 17
Intersecting two postings lists (a merge algorithm) 18
Sec. 1.3 Boolean queries: Exact match The Boolean retrieval model is being able to ask a query that is a Boolean expression: Boolean Queries are queries using AND, OR and NOT to join query terms Views each document as a set of words Is precise: document matches condition or not. Perhaps the simplest model to build an IR system on Primary commercial retrieval tool for 3 decades. Many search systems you still use are Boolean: Email, library catalog, Mac OS X Spotlight 19
Sec. 1.3 Boolean queries: More general merges Exercise: Adapt the merge for the queries: BrutusAND NOTCaesar BrutusOR NOTCaesar Can we still run through the merge in time O(x+y)? What can we achieve? 20
Sec. 1.3 Query optimization What is the best order for query processing? Consider a query that is an AND of n terms. For each of the n terms, get its postings, then AND them together. Brutus 2 4 8 16 32 64 128 1 2 3 5 8 16 21 34 Caesar Calpurnia 13 16 Query: BrutusANDCalpurniaANDCaesar 22
Sec. 1.3 Query optimization example Process in order of increasing freq: start with smallest set, then keep cutting further. This is why we kept document freq. in dictionary Brutus 2 4 8 16 32 64 128 1 2 3 5 8 16 21 34 Caesar Calpurnia 13 16 Execute the query as (CalpurniaANDBrutus)AND Caesar. 24
Sec. 1.3 More general optimization e.g., (madding OR crowd) AND (ignoble OR strife) Get doc. freq. s for all terms. Estimate the size of each ORby the sum of its doc. freq. s (conservative). Process in increasing order of OR sizes. 25
