Strumenti Utente

Strumenti Sito


magistraleinformaticanetworking:ae:ae2021:start

Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

Link a questa pagina di confronto

Entrambe le parti precedenti la revisione Revisione precedente
magistraleinformaticanetworking:ae:ae2021:start [24/11/2021 alle 09:06 (4 giorni fa)]
Paolo Ferragina [Lectures]
magistraleinformaticanetworking:ae:ae2021:start [24/11/2021 alle 10:38 (4 giorni fa)] (versione attuale)
Paolo Ferragina
Linea 91: Linea 91:
 | 23/11/2021 | Substring search: definition, properties, reduction to prefix search. The Suffix Array. Binary searching the Suffix Array: p log n. Suffix Array construction via qsort and its asymptotic analysis. Text mining use of suffix arrays. Compressor bzip: MTF, RLE, Burrows-Wheeler Transform. | Chap. 10 of the notes: 10.1, 10.2.1 (but no page 10-4 and 10-5 and thus no Lemma 10.2), 10.2.3 (but no "The skew algorithm", no "The Scan-based algorithm"), 10.4.3 and 14.1-14.3.\\ [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_11_23-20211123_110530-Meeting%20Recording.mp4?web=1|Video]] and [[https://www.dropbox.com/s/m4yogpojydotw97/Lect%20SA-ST%20and%20Bwt.pptx?dl=0|slides]] | | 23/11/2021 | Substring search: definition, properties, reduction to prefix search. The Suffix Array. Binary searching the Suffix Array: p log n. Suffix Array construction via qsort and its asymptotic analysis. Text mining use of suffix arrays. Compressor bzip: MTF, RLE, Burrows-Wheeler Transform. | Chap. 10 of the notes: 10.1, 10.2.1 (but no page 10-4 and 10-5 and thus no Lemma 10.2), 10.2.3 (but no "The skew algorithm", no "The Scan-based algorithm"), 10.4.3 and 14.1-14.3.\\ [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_11_23-20211123_110530-Meeting%20Recording.mp4?web=1|Video]] and [[https://www.dropbox.com/s/m4yogpojydotw97/Lect%20SA-ST%20and%20Bwt.pptx?dl=0|slides]] |
 | 23/11/2021 | Exercises | Video and notes | | 23/11/2021 | Exercises | Video and notes |
-| 24/11/2021 | How to construct the BWT via qsort. How to invert the BWT. Exercises. | Video [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_11_24-20211124_090354-Meeting%20Recording.mp4?web=1|part 1]] and part 2.|+| 24/11/2021 | How to construct the BWT via qsort. How to invert the BWT. Exercises. | Video [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_11_24-20211124_090354-Meeting%20Recording.mp4?web=1|part 1]] and [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_11_24-20211124_094243-Registrazione%20della%20riunione.mp4|part 2]]. [[https://www.dropbox.com/s/tiqp6pr9v6aaehg/LZ77%2C%20LZss%2C%20LZ78%2C%20Bzip2.pdf?dl=0|Notes]] on exercises.|
  
 | 00/00/2021 | Prefix search: definition of the problem, solution based on arrays, Front-coding, two-level indexing based on compacted tries or Patricia Trees. Analysis of space, I/Os and time of all described solutions.  | Chap. 9 of the notes: 9.1, 9.4, 9.5. No Locality Preserving front coding (9.3). | | 00/00/2021 | Prefix search: definition of the problem, solution based on arrays, Front-coding, two-level indexing based on compacted tries or Patricia Trees. Analysis of space, I/Os and time of all described solutions.  | Chap. 9 of the notes: 9.1, 9.4, 9.5. No Locality Preserving front coding (9.3). |
magistraleinformaticanetworking/ae/ae2021/start.txt · Ultima modifica: 24/11/2021 alle 10:38 (4 giorni fa) da Paolo Ferragina