Question

1 Approved Answer

Posted on Sep 22, 2024

The Problem There are lots of ways to try to compare the similarity of documents. One way is to focus on the character n-grams that

The Problem

There are lots of ways to try to compare the similarity of documents. One way is to focus on the character n-grams that occur in two tracts of text.

n-grams and text comparison

The n-grams found in a text consists of every sequence of n characters. We are going to record the bigrams found in every word (space separated element) and use the counts from two documents to find their similarity.

Consider the sample sentence fragment:"the rat race"

In order, the bigrams (n=2) would be: th, he, ra, at, ra, ac, ce.

Overall the counts would be th:1, he:1, ra:2, at:1, ce:1.

If we take all the spaces out of the sentence to get theratrace, the tri-grams (n=3) would be:

the her era rat atr tra rac ace

Using this information, we could measure the similarity of two documents based on the bigram profile: the list of bigrams and their counts. One (not great) measure is https://en.wikipedia.org/wiki/Cosine_similarity#Ochiai_coefficient . Essentially this would be:

image text in transcribed

Where n is the number of elements in the two quantities A and B. The measure ranges from 0.0 1.0 . We are going to measure this coefficient for various n-grams of provided documents.

Basic Premise

You are going to build a map where the string represents a particular n-gram and the long represents the frequency of finding that n-gram in the document being processed.

Your Tasks

Complete the Project 7 by writing code for the following functions. Details of type for the functions can be found in functions.h (provided for you, see details below). The

map_to_string : returns a single string of the map, where each element is printed as string:long, comma separated elements. No comma at the end, see test cases

vector_to_string : returns a single string of the argument vector>, where each element is printed as string:long, comma separated elements. No comma at the end! This

vector is convenient for sorting, (can't sort a map) as you'll see below, see test cases

clean_string : for the provided string argument returns a new string where the only contents are alphabetic characters in lower case of the argument string

generate_ngrams : for the provided argument string, generates all the ngrams of a given n for that string. Returns a vector of all the ngrams found (no counting at this point, just a

vector of ngrams, could have repeats).

process_line : does the following

o calls clean_string to clean up the provided string argument o calls generate_ngrams on the string (n is provided as an argument) o records the frequency of the ngrams in the argument map reference.

pair_frequency_greaterthan : takes in two pairs and returns whether the first pair is greaterthan the second pair based on the .second of both pairs.

top_n : return a vector> of the argument map that is sorted in frequency order, highest to lowest. Provide only the top n values, n provided as an argument.

If you sort the vector to find this ordering, than pair_frequency_greaterthan is useful. It is a two-layered ordering: first by frequency, second alphabetically. Thus you always print

the element with the highest frequency. However, if two or more elements are tied in frequency, then print those tied frequency elements in alphabetical order.

pair_string_lessthan : takes in two pair and returns whether the first pair is lessthan the second pair based on the .first of both pairs.

ochiai : calculates the ochiai value for the two argument maps. If you use set_intersection to find the intersection set, then pair_string_lessthan is useful.

Test Cases

Test cases are provided in the subdirectory test of the project directory (because it is getting confusing), at least one for each function . However! It is time you start writing your own tests. The tests I provide are not complete, and we are free to write extra tests for grading purposes. Do a good job and test your code. Just because you pass the one (probably simple) test does not necessarily mean your code is fine. Think about your own testing!!!!

Assignment Notes

You are given the following files:

main.cpp This file includes the main function where the test cases will be run:

---------- main.cpp start----------

#include using std::cout; using std::cin; using std::endl; using std::boolalpha; #include using std::setprecision; #include using std::map; #include using std::vector; #include using std::pair; #include using std::string; using std::getline; #include using std::ifstream; #include using std::ostream_iterator; #include "functions.h" int main (){ int case_no; ostream_iterator oss(cout, ", "); cout > case_no; switch(case_no){ case 1 : { cin.ignore(100, ' '); string s; getline(cin, s); cout > n; cin.ignore(100, ' '); getline(cin, s); auto v = generate_ngrams(s, n); copy (v.begin(), v.end(), oss); cout  m{ {"a",3}, {"b",2}, {"c",1} }; cout  m; cin >> n; cin.ignore(100, ' '); getline(cin, s); process_line(m, s, n); cout > s >> l; pair p1(s,l); cin >> s >> l; pair p2(s,l); cout > v{ {"a",1}, {"b",2}, {"c",3} }; cout  m; cin >> ngram >> topn; cin.ignore(100, ' '); getline(cin, s); process_line(m, s, ngram); auto v = top_n(m, topn); cout  m1, m2; cin >> ngram >> fname1 >> fname2; ifstream if1(fname1); ifstream if2(fname2); while (getline(if1, line) ) process_line(m1, line, ngram); while (getline(if2, line) ) process_line(m2, line, ngram); cout  ---------- main.cpp end----------
 Do not modify this file.
 functions.h  This file is the header file for your functions.cpp file.
 ----------functions.h start----------
 #ifndef DOCUMENT_SIM #define DOCUMENT_SIM #include using std::string; #include using std::map; #include using std::pair; #include using std::vector; string map_to_string(map &m); string vector_to_string(vector> &v); string clean_string(string w); vector generate_ngrams(string w, size_t n); void process_line(map& m, string line, size_t n); bool pair_string_lessthan(const pair &p1, const pair &p2); bool pair_frequency_greaterthan(const pair &p1, const pair &p2); vector> top_n(map &m, int num); double ochiai(map &m1, map &m2); // optional, see @461 in piazza double ochiai2(map &m1, map &m2, int num); #endif 
 ----------functions.h end----------
 Do notmodify this file.
 input#.txt  These four text files will be used to run the test cases.
 
  
 correct_output_#.txt  These text files will be used to grade your output based on thecorresponding input files. Be sure that your output matches these text files exactly to
 get credit for the test cases.
 
 --------------------gburg.txt
  Fourscore and seven years ago our fathers brought forth on this continent a new nation, conceived in liberty and dedicated to the proposition that all men are created equal. Now we are engaged in a great civil war, testing whether that nation or any nation so conceived and so dedicated can long endure. We are met on a great battle field of that war. We have come to dedicate a portion of that field, as a final resting place for those who here gave their lives that that nation might live. It is altogether fitting and proper that we should do this. But, in a larger sense, we can not dedicate -- we can not consecrate -- we can not hallow -- this ground. The brave men living and dead, who struggled here, have consecrated it, far above our poor power to add or detract. The world will little note, nor long remember, what we say here, but it will never forget what they did here. It is for this the living, rather, to be dedicated here to the unfinished work which they who fought here have thus far so nobly advanced. It is rather for us to be here dedicated to the great task remaining before us -- that from thse honored dead we take increased devotion to that cause for which they gave the last full measure of devotion -- that we here highly resolve that these dead shall not have died in vain -- that this nation, under God, shall have a new birth of freedom -- and that government of the people, by the people, for the people, shall not perish from the earth. 
 ---------------------
 ---------------------howl1.txt
 I saw the best minds of my generation destroyed by madness, starving hysterical naked, dragging themselves through the negro streets at dawn looking for an angry fix, angelheaded hipsters burning for the ancient heavenly connection to the starry dynamo in the machinery of night, who poverty and tatters and hollow-eyed and high sat up smoking in the supernatural darkness of cold-water flats floating across the tops of cities contemplating jazz, who bared their brains to Heaven under the El and saw Mohammedan angels staggering on tenement roofs illuminated, who passed through universities with radiant cool eyes hallucinating Arkansas and Blake-light tragedy among the scholars of war, who were expelled from the academies for crazy & publishing obscene odes on the windows of the skull, who cowered in unshaven rooms in underwear, burning their money in wastebaskets and listening to the Terror through the wall, who got busted in their pubic beards returning through Laredo with a belt of marijuana for New York, who ate fire in paint hotels or drank turpentine in Paradise Alley, death, or purgatoried their torsos night after night with dreams, with drugs, with waking nightmares, alcohol and cock and endless balls, incomparable blind streets of shuddering cloud and lightning in the mind leaping toward poles of Canada & Paterson, illuminating all the motionless world of Time between, Peyote solidities of halls, backyard green tree cemetery dawns, wine drunkenness over the rooftops, storefront boroughs of teahead joyride neon blinking traffic light, sun and moon and tree vibrations in the roaring winter dusks of Brooklyn, ashcan rantings and kind king light of mind, who chained themselves to subways for the endless ride from Battery to holy Bronx on benzedrine until the noise of wheels and children brought them down shuddering mouth-wracked and battered bleak of brain all drained of brilliance in the drear light of Zoo, who sank all night in submarine light of Bickfords floated out and sat through the stale beer afternoon in desolate Fugazzis, listening to the crack of doom on the hydrogen jukebox, who talked continuously seventy hours from park to pad to bar to Bellevue to museum to the Brooklyn Bridge, a lost battalion of platonic conversationalists jumping down the stoops off fire escapes off windowsills off Empire State out of the moon, yacketayakking screaming vomiting whispering facts and memories and anecdotes and eyeball kicks and shocks of hospitals and jails and wars, whole intellects disgorged in total recall for seven days and nights with brilliant eyes, meat for the Synagogue cast on the pavement, who vanished into nowhere Zen New Jersey leaving a trail of ambiguous picture postcards of Atlantic City Hall, suffering Eastern sweats and Tangerian bone-grindings and migraines of China under junk-withdrawal in Newarks bleak furnished room, who wandered around and around at midnight in the railroad yard wondering where to go, and went, leaving no broken hearts, who lit cigarettes in boxcars boxcars boxcars racketing through snow toward lonesome farms in grandfather night, who studied Plotinus Poe St. John of the Cross telepathy and bop kabbalah because the cosmos instinctively vibrated at their feet in Kansas, who loned it through the streets of Idaho seeking visionary indian angels who were visionary indian angels, who thought they were only mad when Baltimore gleamed in supernatural ecstasy, who jumped in limousines with the Chinaman of Oklahoma on the impulse of winter midnight streetlight smalltown rain, who lounged hungry and lonesome through Houston seeking jazz or sex or soup, and followed the brilliant Spaniard to converse about America and Eternity, a hopeless task, and so took ship to Africa, who disappeared into the volcanoes of Mexico leaving behind nothing but the shadow of dungarees and the lava and ash of poetry scattered in fireplace Chicago, who reappeared on the West Coast investigating the FBI in beards and shorts with big pacifist eyes sexy in their dark skin passing out incomprehensible leaflets, who burned cigarette holes in their arms protesting the narcotic tobacco haze of Capitalism, who distributed Supercommunist pamphlets in Union Square weeping and undressing while the sirens of Los Alamos wailed them down, and wailed down Wall, and the Staten Island ferry also wailed, who broke down crying in white gymnasiums naked and trembling before the machinery of other skeletons, who bit detectives in the neck and shrieked with delight in policecars for committing no crime but their own wild cooking pederasty and intoxication, who howled on their knees in the subway and were dragged off the roof waving genitals and manuscripts, who let themselves be fucked in the ass by saintly motorcyclists, and screamed with joy, who blew and were blown by those human seraphim, the sailors, caresses of Atlantic and Caribbean love, who balled in the morning in the evenings in rosegardens and the grass of public parks and cemeteries scattering their semen freely to whomever come who may, who hiccuped endlessly trying to giggle but wound up with a sob behind a partition in a Turkish Bath when the blond & naked angel came to pierce them with a sword, who lost their loveboys to the three old shrews of fate the one eyed shrew of the heterosexual dollar the one eyed shrew that winks out of the womb and the one eyed shrew that does nothing but sit on her ass and snip the intellectual golden threads of the craftsmans loom, who copulated ecstatic and insatiate with a bottle of beer a sweetheart a package of cigarettes a candle and fell off the bed, and continued along the floor and down the hall and ended fainting on the wall with a vision of ultimate cunt and come eluding the last gyzym of consciousness, who sweetened the snatches of a million girls trembling in the sunset, and were red eyed in the morning but prepared to sweeten the snatch of the sunrise, flashing buttocks under barns and naked in the lake, who went out whoring through Colorado in myriad stolen night-cars, N.C., secret hero of these poems, cocksman and Adonis of Denverjoy to the memory of his innumerable lays of girls in empty lots & diner backyards, moviehouses rickety rows, on mountaintops in caves or with gaunt waitresses in familiar roadside lonely petticoat upliftings & especially secret gas-station solipsisms of johns, & hometown alleys too, who faded out in vast sordid movies, were shifted in dreams, woke on a sudden Manhattan, and picked themselves up out of basements hung-over with heartless Tokay and horrors of Third Avenue iron dreams & stumbled to unemployment offices, who walked all night with their shoes full of blood on the snowbank docks waiting for a door in the East River to open to a room full of steam-heat and opium, who created great suicidal dramas on the apartment cliff-banks of the Hudson under the wartime blue floodlight of the moon & their heads shall be crowned with laurel in oblivion, who ate the lamb stew of the imagination or digested the crab at the muddy bottom of the rivers of Bowery, who wept at the romance of the streets with their pushcarts full of onions and bad music, who sat in boxes breathing in the darkness under the bridge, and rose up to build harpsichords in their lofts, who coughed on the sixth floor of Harlem crowned with flame under the tubercular sky surrounded by orange crates of theology, who scribbled all night rocking and rolling over lofty incantations which in the yellow morning were stanzas of gibberish, who cooked rotten animals lung heart feet tail borsht & tortillas dreaming of the pure vegetable kingdom, who plunged themselves under meat trucks looking for an egg, who threw their watches off the roof to cast their ballot for Eternity outside of Time, & alarm clocks fell on their heads every day for the next decade, who cut their wrists three times successively unsuccessfully, gave up and were forced to open antique stores where they thought they were growing old and cried, who were burned alive in their innocent flannel suits on Madison Avenue amid blasts of leaden verse & the tanked-up clatter of the iron regiments of fashion & the nitroglycerine shrieks of the fairies of advertising & the mustard gas of sinister intelligent editors, or were run down by the drunken taxicabs of Absolute Reality, who jumped off the Brooklyn Bridge this actually happened and walked away unknown and forgotten into the ghostly daze of Chinatown soup alleyways & firetrucks, not even one free beer, who sang out of their windows in despair, fell out of the subway window, jumped in the filthy Passaic, leaped on negroes, cried all over the street, danced on broken wineglasses barefoot smashed phonograph records of nostalgic European 1930s German jazz finished the whiskey and threw up groaning into the bloody toilet, moans in their ears and the blast of colossal steamwhistles, who barreled down the highways of the past journeying to each others hotrod-Golgotha jail-solitude watch or Birmingham jazz incarnation, who drove crosscountry seventytwo hours to find out if I had a vision or you had a vision or he had a vision to find out Eternity, who journeyed to Denver, who died in Denver, who came back to Denver & waited in vain, who watched over Denver & brooded & loned in Denver and finally went away to find out the Time, & now Denver is lonesome for her heroes, who fell on their knees in hopeless cathedrals praying for each others salvation and light and breasts, until the soul illuminated its hair for a second, who crashed through their minds in jail waiting for impossible criminals with golden heads and the charm of reality in their hearts who sang sweet blues to Alcatraz, who retired to Mexico to cultivate a habit, or Rocky Mount to tender Buddha or Tangiers to boys or Southern Pacific to the black locomotive or Harvard to Narcissus to Woodlawn to the daisychain or grave, who demanded sanity trials accusing the radio of hypnotism & were left with their insanity & their hands & a hung jury, who threw potato salad at CCNY lecturers on Dadaism and subsequently presented themselves on the granite steps of the madhouse with shaven heads and harlequin speech of suicide, demanding instantaneous lobotomy, and who were given instead the concrete void of insulin Metrazol electricity hydrotherapy psychotherapy occupational therapy pingpong & amnesia, who in humorless protest overturned only one symbolic pingpong table, resting briefly in catatonia, returning years later truly bald except for a wig of blood, and tears and fingers, to the visible madman doom of the wards of the madtowns of the East, Pilgrim States Rocklands and Greystones foetid halls, bickering with the echoes of the soul, rocking and rolling in the midnight solitude-bench dolmen-realms of love, dream of life a nightmare, bodies turned to stone as heavy as the moon, with mother finally ******, and the last fantastic book flung out of the tenement window, and the last door closed at 4 A.M. and the last telephone slammed at the wall in reply and the last furnished room emptied down to the last piece of mental furniture, a yellow paper rose twisted on a wire hanger in the closet, and even that imaginary, nothing but a hopeful little bit of hallucination ah, Carl, while you are not safe I am not safe, and now youre really in the total animal soup of time and who therefore ran through the icy streets obsessed with a sudden flash of the alchemy of the use of the ellipsis catalogue a variable measure and the vibrating plane, who dreamt and made incarnate gaps in Time & Space through images juxtaposed, and trapped the archangel of the soul between 2 visual images and joined the elemental verbs and set the noun and dash of consciousness together jumping with sensation of Pater Omnipotens Aeterna Deus to recreate the syntax and measure of poor human prose and stand before you speechless and intelligent and shaking with shame, rejected yet confessing out the soul to conform to the rhythm of thought in his naked and endless head, the madman bum and angel beat in Time, unknown, yet putting down here what might be left to say in time come after death, and rose reincarnate in the ghostly clothes of jazz in the goldhorn shadow of the band and blew the suffering of Americas naked mind for love into an eli eli lamma lamma sabacthani saxophone cry that shivered the cities down to the last radio with the absolute heart of the poem of life butchered out of their own bodies good to eat a thousand years. 
 --------------------
 --------------------neruda.txt
 Enfermo en Vercruz, recuerdo un da del Sur, mi tierra, un da de plata como un rpido pez en el agua del cielo. Loncoche, Lonquimay, Carahue, desde arriba esparcidos, rodeados por silencio y races, sentados en sus tronos de cueros y maderas. El Sur es un caballo echado a pique coronado con lentos rboles y roco, cuando levanta el verde hocico caen las gotas, la sombra de su cola moja el gran archipilago y en su intestino crece el carbn venerado. Nunca ms, dime, sombra, nunca ms, dime, mano, nunca ms, dime, pie, puerta, pierna, combate, trastornars la selva, el camino, la espiga, la niebla, el fro, lo que, azul, determinaba cada uno de tus pasos sin cesar consumidos? Cielo, djame un da de estrella a estrella irme pisando luz y plvora, destrozando mi sangre hasta llegar al nido de la lluvia! Quiero ir detrs de la madera por el ro Toltn fragante, quiero salir de los aserraderos, entrar en las cantinas con los pies empapados, guiarme por la luz del avellano elctrico, tenderme junto al excremento de las vacas, morir y revivir mordiendo trigo. Ocano, treme un da del Sur, un da agarrado a tus olas, un da de rbol mojado, trae un viento azul polar a mi bandera fra!
 --------------------
 You will write only functions.cpp and compile that file using functions.h and main.cpp in the same directory. You are only turning in functions.cpp for the project.
 Comparing outputs: You can use redirected output to compare the output of your program to
 the correct output. Use redirected output and the diff command in the Unix terminal to accomplish this: 
 Run your executable on the desired input file. Lets assume youre testing input1.txt, the first test case. Redirect the output using the following line when in your proj06 directory: ./a.out  output1.txt
 Now your output is in the file output1.txt. Compare output1.txt to correct_output1.txt using the following line: diff output1.txt correct_output1.txt
 If the two files match, nothing will be output to the terminal. Otherwise, diff will print the two outputs. 
  
  
  n (A n B n A) n(B)