{"push_id":1333873402,"size":1,"distinct_size":1,"ref":"refs/heads/master","head":"cb261f7cd5e62405e82a22de61263c8f07239aa1","before":"d9e5f68b83fb48e633aaaad78c29df1ef5985372","commits":[{"sha":"cb261f7cd5e62405e82a22de61263c8f07239aa1","author":{"name":"Manav Bhanot","email":"8106f2c5bbbda0d3c219d1b5d750a589a913963c@live.in"},"message":"Committing the 1st milestone of the project. Below is the description of\nthe 1st milestone\nCECS 429 - Project Milestone 1\nMilestone demo due October 4.\nRevision History\n\u000F 12 September 2016: added restriction on using sets or maps outside of\nthe inverted index's main hash\nmap.\n\u000F 11 September 2016: removed defunct references to parentheses in the\nquery language. Changed\nSoundex query key from author: to :author to match style of other\nspecial queries.\nOverview\nIn this project milestone, you will piece together and extend many of\nthe search engine features you have\nalready programmed in this class. You may work in teams of up to 3\npeople, but as you will see, more people\nin a group will necessitate additional work.\nYou will program an application to index a directory of \u001Cles using a\npositional inverted index. You will\nask the user for the name of the directory to index, and then load all\nthe documents in that directory and\nconstruct your index with their contents. You will then process the\nuser's Boolean search queries on the\nindex you constructed.\nThe \u001Crst milestone will use a text-based interface as in your homework\nassignments. When processing a\nquery, you must display the name of each document that matches the\nrequest, and then allow the user to\n(optionally) select a document from the result list. If the user selects\na document, its original text (not\nprocessed, stemmed, etc.) should be displayed.\nRequirements\nThese mandatory requirements must be completed by all groups.\nCorpus:\nThe o\u001Ecial corpus for this project will be the full all-nps-sites.json\ncorpus, split into individual document\n\u001Cles. However, there will be a future need to support multiple corpi in\nthe search engine, so your program\nwill begin by asking the user to enter a folder to index. You will then\nbuild your index with the documents\nin that folder.\nBuilding the index:\nIndexes: You will maintain one index for your corpus: the\nPositionalInvertedIndex, a positional index\nas discussed in class, where postings lists consist of <documentID,\n[position1, position2, ...]> pairs. Use\nNaiveInvertedIndex as a reference point. You may need to write your own\nsimple PositionalPosting\nclass to pair an integer document ID with a list of integer document\npositions; your index can then map a\nstring term to a list of PositionalPosting objects. The addTerm method\nwill need an additional parameter\nfor the term's position.\nThe index should consist of a hash map from string keys (the terms in\nthe vocabulary) to (array) lists of\npostings. You must not use any other hash maps or any \u0010set\u0011 data\nstructures in your code, only lists.\nDocument processing: Using the framework already built for\nSimpleTokenStream (or writing your own),\nprocess each document. For each token read from the document, perform\nthese steps to normalize the token\nto a term:\n1. Remove all non-alphanumeric characters from the beginning and end.\n2. Remove all apostropes (single quotes).\n3. For hyphens in words, do both:\n(a) Remove the hyphens from the token and then proceed with the modi\u001Ced\ntoken;\n(b) Split the original hyphenated token into two tokens without a\nhyphen, and proceed with both.\n(So the token \u0010Hewlett-Packard\u0011 would turn into HewlettPackard, Hewlett,\nand Packard.)\n1\n4. Convert the token to lowercase.\n5. Stem the token using your Porter Stemmer.\nThen index the document using the term and its position in the \u001Cle\n(0-based).\nQuery language:\nWe will support user queries in the form\nQ1 + Q2 + \u0001 \u0001 \u0001 + Qk\nwhere the + represents \u0010OR\u0011, and each Qi is a sequence of query literals\nseparated by white space. A\nquery literal is one of the following:\n1. a single token\n2. a sequence of tokens that are within double quotes, representing a\nphrase query\nEach of these two cases are called positive literals, because they must\nbe present in a document if that\ndocument is to satisfy the corresponding Qi. (More on positive and\nnegative literals below.) Note that every\nQi has at least one positive literal. Examples:\n\u000F shakes \u0010Jamba Juice\u0011\nhere, there is one Q (k = 1) and two positive literals (shakes and\n\u0010Jamba Juice\u0011). We want all\ndocuments with shakes and with the phrase \u0010Jamba Juice\u0011.\n\u000F shakes + smoothies mango\nhere, we have Q1 =shakes and Q2 =smoothies mango. We want all documents\nwith shakes or both\nsmoothies and mango.\nAfter parsing a query, your index will process one Qi at a time, merging\nthe postings lists for each query\nliteral in the sequence. After each Qi has been processed, the \u001Cnal\nresult set will be combined with \u0010OR\u0011\nlogic and shown to the user. In the query \u0010Jamba Juice\u0011 shakes + mango\nsmoothies, you would \u001Crst\nmerge the results from \u0010Jamba Juice\u0011 and shakes; then merge mango and\nsmoothies; then OR the \u001Cnal\nresult sets.\nYou may assume that the user always types in a properly-formatted query,\nand do not need to do error\nchecking or reporting. Note that this query language does not support\nthe NOT operator. It also does not\nsupport queries of the form smoothies (mango + banana). Finally, note\nthat each token in the query should\nbe processed in the same way that the documents are.\nSpecial queries: Your engine must also handle a few \u0010special\u0011 queries\nthat do not represent information\nneeds, but instead are used for administrative needs. If the user query\nstarts with any of these strings, then\nperform the speci\u001Ced operation instead of doing a postings retrieval.\n\u000F :q \u0015 exit the program.\n\u000F :stem token \u0015 take the token string and stem it, then print the\nstemmed term.\n\u000F :index directoryname \u0015 index the folder speci\u001Ced by directoryname and\nthen begin querying it.\n\u000F :vocab \u0015 print all terms in the vocabulary of the corpus, one term per\nline. Then print the count of\nthe total number of vocabulary terms.\nProgram \u001Dow:\nYour program should follow this general \u001Dow of operation:\n1. At startup, ask the user for the name of a directory that they would\nlike to index. You may assume\nthat the directory is placed in the same folder that your project is\nlocated in.\n2. Index all documents in the directory using the positional index as\noutlined above.\n3. Loop:\n2\n(a) Ask for a search query.\ni. If it is a special query, perform that action.\nii. If it is not, then parse the query and merge the postings lists as\nnecessary.\nA. Output the names of the documents returned from the query. Ask the\nuser if they would\nlike to select a document to view.\nB. If the user selects a document to view, print the entire text of the\ndocument to the screen.\nAdditional Requirements\nYou must select and implement N additional features from the following\nlist, where N is equal to...\n\u000F the number of people in your group...\n\u000F plus 1, if at least one member of your group is enrolled in CECS 529.\nFinally, you must select at least one Category A option.\nCategory A:\nYour own corpus: Choose a corpus of documents to use with your search\nengine. Download (or otherwise\nretrieve) your chosen corpus, which must contain at least 10000\ndocuments totaling at least 10 MB of un-\ncompressed disk space.\nYou must submit a corpus proposal to me by September 15 in order to\nselect this feature for your project.\nYour proposal must be typed, and must contain: a description of the\ncorpus you would like to use; why you\nwould like to use this corpus; how you will retrieve the corpus; any\nspecial processing rules needed when\ntokenizing the corpus.\nI probably will not accept a corpus proposal if you simply plan to\ndownload some novel and index its\nchapters like we have done with Moby Dick. Your corpus will need to\nrequire a good amount of e\u001Bort to\nretreive/process, and represent some speci\u001Cc domain that is of interest\nto you.\nNOT queries: Amend your query language to support the boolean NOT\noperator as a minus sign (\u0010 -\u0011). To\nsupport this feature, edit the de\u001Cnition of query literal above to:\n1. a single token\n2. a sequence of tokens that are within double quotes, representing a\nphrase query\n3. a query literal preceeded by the negation symbol -\nWe say that a literal with a - is a negative literal, and require that\neach Qi in the query have at least\none positive literal. Knowing this, you should carefully select the\norder of terms when processing a query\nliteral: process and merge all positive literals, then merge with any\nnegative literals. Note: your NOT\noperator must also work with phrase queries. Your language now supports\nqueries like -\u0010Jamba Juice\u0011\nshakes smoothies and shakes + smoothies -mango.\nWildcard queries: Amend the query parser to support wildcard queries\nwith arbitrary numbers of * charac-\nters representing wildcards. Implement 1-, 2-, and 3-gram indexes for\neach vocabulary type in the vocabu-\nlary. Represent the k-gram index with a class KGramIndex, with a method\nto add a string type to the index\n(thereby generating 1-, 2-, and 3-grams for the type and inserting them\ninto an inverted index structure),\nand a method to retrieve a list of types that contain a given k-gram.\nWhen reading a wildcard token in a\nuser query, generate all k-grams for the wildcard token, then merge the\npostings list of each k-gram. The\nmerged list contains all candidate type strings; implement a\npost-\u001Cltering step to ensure that each candidate\nmatches the wildcard format. OR together the postings for the\nprocessed/stemmed term from each \u001Cnal\nwildcard candidate and then merge those postings as needed in the rest\nof the query.\nBiword index: When indexing the corpus, additionally build a biword\nindex. When the user enters a phrase\nquery literal, use the biword index to satisfy the query if and only if\nthe phrase query contains only two\n3\nterms; use the positional index otherwise. The biword index can be a\nnonpositional index, that is, you will\nrecord document IDs for each biword entry, but not the position of the\nbiword in the document.\nSoundex algorithm: Read the textbook chapter 3.4 regarding phonetic\ncorrection using the \u0010soundex al-\ngorithm,\u0011 then implement the algorithm so your search engine's users can\nsearch boolean queries on the\nauthors of documents in your corpus, using tolerant retrieval for\nmisspelled names via the soundex algo-\nrithm.\nThe National Park Service corpus does not have author information in its\ndocuments. To complete this\noption, you will need to download a a di\u001Berent corpus:\nmlb-articles-4000.zip from BeachBoard, contain-\ning articles about Major League Baseball. The JSON format for these\narticles contains an author \u001Celd.\nCreate a class to represent a soundex index. A soundex index maps from\nsoundex hash keys (four-letter\nstrings) to document IDs that contained a string which produced the\nhash. When indexing a document,\nafter you have processed all the tokens in the body of the document,\nprocess the author of the document as\nwell, by hashing each term in the author \u001Celd (the author's \u001Crst and\nlast names, presumably) using soundex,\nand inserting a posting into the soundex index.\nWhen querying a corpus, allow the user to search the author soundex\nindex by specifying a query of :author\n_______. A single term may follow :author, and that is the term you\nshould hash and retrieve postings for.\nList all documents that matched the author query.\nForeign language indexing: Once again, I am an ignorant American, so\n\u0010foreign\u0011 here means non-English.\nExpand your search engine to handle non-English language documents and\nqueries. The language you choose\nmust have di\u001Berent indexing/parsing rules than the simple rules we use\nfor English language, and you must\nprogram your engine to handle those rules. Example: you may choose\nGerman if you design a software\nmodule to split compound nouns, so that Computerprogrammierer is indexed\nseparately as computer and\nprogrammierer. (You will probably have to do your own research into how\nthis is done.) Your engine must\nstill operate on English documents so I can test it, and you may use two\ndi\u001Berent \u0010modes\u0011 for operating on\nEnglish or non-English collections if desired.\nYou must submit a summary of your language of choice, the issues that\nmake it harder than indexing\nEnglish, and a summary of how you will solve those issues when you turn\nin your project proposal.\nNote that you will need to also complete Category A option \u0010Your own\ncorpus\u0011 for this option to really\nmake any sense.\nYour own interests: Are you interested in something else that we've\ntalked about in lecture? Maybe you\nwant to do some research and implementation on your own? Come chat with\nme and let me know.\nCategory B:\nNEAR operator : Implement the NEAR/K operator in Boolean retrieval mode.\nGiven a value k, do a\npositional merge between the terms to the left and right of the NEAR\noperator, selecting documents where\nthe second term appears at most k positions away from the \u001Crst term. (We\nwill say that the order of the\nterms matters: \u0010angels love baseball\u0011 will match the query \u0010angels\nNEAR/2 baseball\u0011 but not \u0010baseball\nNEAR/2 angels\u0011.)\nGraphical user interface: Instead of a text interface, program a\ngraphical user interface. When the program\nstarts, show a dialog that lets the user select a directory to index.\nWhen the index is complete, show a text\n\u001Celd for the user to type their queries. Upon submitting the query, show\na list of document titles that match\nthe query. When the user double-clicks a result in the list, open a new\nwindow showing the contents of the\ndocument.\nYou must provide GUI-appropriate alternatives to the \u0010special queries\u0011\nmentioned in the required features.\n4\nIndex statistics: Add an option to the main menu that allows the user to\nview statistics about the index.\nYou must provide the following measures:\n1. Number of terms and types in the index.\n2. The average number of documents in the postings list of a term in the\nindex. (If 5 documents, with\npostings lists of size 2, 4, 6, 8, and 10, the average number of\ndocuments in a posting list is 6.)\n3. For the 10 most frequent terms in the index, the proportion of\ndocuments that contain each of those\nterms. (Return this as an array of doubles; if the most frequent term is\nin 50% of documents, the \u001Crst\ndouble in the array will be 0.5)\n4. The approximate total memory requirement of the index. Use the\nfollowing facts:\n(a) A HashMap/Dictionary object requires approximately 24+36n bytes per\nitem stored in the map,\nwhere n is the number of keys in the map, regardless of what kind of\nobjects are in the map. In\nthis case, n is the number of terms in the dictionary.\n(b) Each string term in the index requires approximately 40 + 2n bytes,\nwhere n is the length of the\nstring.\n(c) Each postings list itself (the actual ArrayList/List object)\nrequires 24 + 8n bytes, where n is\nthe number of entries in the list (the number of documents that contain\nthe term).\n(d) Each posting itself (the integer document ID in the postings list,\nplus the positions in the docu-\nment) requires 48 + 4n bytes, where n is the number of positions\nassociated with the document\nID in the posting.\n(e) Apply similar logic to separately sum the size of the biword index\nand/or soundex index, if\nand only if you implemented those features.\n5. Example: if there is one term in the index, and that term is\n\u0010search\u0011, and search is indexed to 2\ndocuments, with document 1 have 5 positions and document 2 having 6\npositions:\n(a) the HashMap takes 24 + 36 (1) = 60 bytes\n(b) the string \u0010search\u0011 requires 40 + 2 (6) = 52 bytes\n(c) the postings list for \u0010search\u0011 requires 24 + 8 (2) = 40 bytes\n(d) the postings list for document 1 requires 48 + 4 (5) 68 bytes, and\nthe postings list for document\n2 requires 48 + 4 (6) = 72 bytes\n(e) so the total memory requirement for the index is 60 + 52 + 40 + 68 +\n72 = 292 bytes.\nYou should not calculate these values when requested; you should instead\nadd a method void finishIndexing()\nto your inverted index class. Call that method when you are done\nprocessing documents, and in the method\nyou should calculate and store each the statistics above. Write\naccessor/\u0011get\u0011 methods for each statistic so\nyour main can use them when outputting.\nUnit testing framework: Implement a unit testing framework for portions\nof your search engine. Using a\nstyle and method appropriate to your language of choice, design,\nimplement, and run unit tests to verify the\ncorrectness of the following portions of your search engine:\n1. Porter stemmer: select a list of words (you will probably need 30-50)\ndesigned to test every single\ncase (100% code coverage) of your Porter stemmer code. Stem the words by\nhand to produce the set\nof expected outputs, then write unit tests for each word to verify that\nthe stemmer is correct.\n2. Positional inverted index: write a set of 5 simple text documents\nwith a combined vocabulary of\n10-15 words. Build a positional inverted index by hand. Write unit tests\nto constuct an index over\nyour documents, then verify that the positional postings match the\nexpected output based on your\nhand-built index. You do not need to verify each word in the vocabulary,\nbut should be sure to test\nwords that occur more than once in a particular document.\n3. Query processing: using your example corpus from above, write unit\ntests to verify the correctness\nof your search engine results. Write tests for each kind of query you\nhave to implement: phrase queries,\nAND queries, OR queries, and NOT queries (if you chose this option).\nVerify the results match your\n5\nexpected outputs by solving the queries by hand. Make sure you write\nqueries for which there is no\nresult set, and queries for which all documents are relevant.\nSummary\nI realize this is a long document and it may be hard to keep track of\nwhat's required. Here is a brief list of\nimportant things to keep in mind. (This is NOT exhaustive, you are\nultimately responsible for everything\nin this document even if it isn't listed in this summary.)\nYou must:\n1. Build a positional inverted index over a user-speci\u001Ced directory of\ntext \u001Cles\n2. Process tokens from \u001Cles with Porter stemming and special rules for\nother characters; and use the same\nrules for user queries\n3. Read Boolean queries from the user and merge postings lists for the\nquery (both AND and OR merges)\n4. Support phrase queries with quotation marks via the positional index\nYou must choose one of these options for each person in your group. If\nany group member is enrolled in 529,\nselect one additional option. At least one option must come from\nCategory A.\n1. Category A:\n(a) Your own corpus (must submit proposal to instructor)\n(b) NOT queries\n(c) k-gram index for wildcard queries\n(d) Biword index\n(e) Soundex index\n(f) Non-English indexing (requires proposal)\n(g) Your own research interest\n2. Category B:\n(a) NEAR/K operator\n(b) GUI\n(c) Index statistics\n(d) Unit tests\n6","distinct":true,"url":"https://api.github.com/repos/manav-bhanot/SearchEngineTech/commits/cb261f7cd5e62405e82a22de61263c8f07239aa1"}]}
{"actor":{"display_login":"manav-bhanot"}}