Platformăde e-learning și curriculăe-content pentru...
21
Platformă de e-learning și curriculă e-content pentru înv ățământul superior tehnic Transmisia datelor multimedia in retele de calculatoare 17. LZ78
Transcript of Platformăde e-learning și curriculăe-content pentru...
Platformă de e-learning și curriculă e-contentpentru învățământul superior tehnic
Transmisia datelor multimedia in retele de calculatoare
17. LZ78
2
LZ78
• LZ77 presupune localitatea grupurilor de simboluri
• LZ78:
▫ Nu exista un buffer de cautare – dictionarul este
explicit
▫ Codificatorul/decodificatorul construiesc dictionarul
intr-un mod sincronizat
▫ Codificare: <i, c>
i = indexul din dictionar
c = codul urmatorului simbol
• Example:
▫ wabbawabbawabbawabbawoowoowoo
3
Exemplu LZ78
Index Intr.
Dictionar:
Input: wabbawabbawabbawabbawoowoowoo
Output:
4
Exemplu LZ78
Index Intr.
1 w
Dictionar:
Input: wabbawabbawabbawabbawoowoowoo
Output:
<0, C(w)>
5
Exemplu LZ78
Index Intr.
1 w
2 a
Dictionar:
Input: -abbawabbawabbawabbawoowoowoo
Output:
<0, C(w)>
<0, C(a)>
6
Exemplu LZ78
Index Intr.
1 w
2 a
3 b
Dictionar:
Input: --bbawabbawabbawabbawoowoowoo
Output:
<0, C(w)>
<0, C(a)>
<0, C(b)>
7
Exemplu LZ78
Index Intr.
1 w
2 a
3 b
4 ba
Dictionar:
Input: ---bawabbawabbawabbawoowoowoo
Output:
<0, C(w)>
<0, C(a)>
<0, C(b)>
<3, C(a)>
8
Exemplu LZ78
Index Intr.
1 w
2 a
3 b
4 ba
5
Dictionar:
Input: -----wabbawabbawabbawoowoowoo
Output:
<0, C(w)>
<0, C(a)>
<0, C(b)>
<3, C(a)>
<0, C( )>
9
Exemplu LZ78
Index Intr.
1 w
2 a
3 b
4 ba
5
6 wa
Dictionar:
Input: ------wabbawabbawabbawoowoowoo
Output:
<0, C(w)>
<0, C(a)>
<0, C(b)>
<3, C(a)>
<0, C( )>
<1, C(a)>
10
Exemplu LZ78
Index Intr.
1 w
2 a
3 b
4 ba
5
6 wa
7 bb
Dictionar:
Input: --------bbawabbawabbawoowoowoo
Output:
<0, C(w)>
<0, C(a)>
<0, C(b)>
<3, C(a)>
<0, C( )>
<1, C(a)>
<3, C(b)>
11
Exemplu LZ78
Index Intr.
1 w
2 a
3 b
4 ba
5
6 wa
7 bb
8 a
Dictionar:
Input: ----------awabbawabbawoowoowoo
Output:
<0, C(w)>
<0, C(a)>
<0, C(b)>
<3, C(a)>
<0, C( )>
<1, C(a)>
<3, C(b)>
<2, C( )>
12
Exemplu LZ78
Index Intr.
1 w
2 a
3 b
4 ba
5
6 wa
7 bb
8 a
9 wab
Dictionar:
Input: ------------wabbawabbawoowoowoo
Output:
<0, C(w)>
<0, C(a)>
<0, C(b)>
<3, C(a)>
<0, C( )>
<1, C(a)>
<3, C(b)>
<2, C( )>
<6, C(b)>
13
Exemplu LZ78
Index Intr.
1 w
2 a
3 b
4 ba
5
6 wa
7 bb
8 a
9 wab
10 ba
Dictionar:
Input: ---------------bawabbawoowoowoo
Output:
<0, C(w)>
<0, C(a)>
<0, C(b)>
<3, C(a)>
<0, C( )>
<1, C(a)>
<3, C(b)>
<2, C( )>
<6, C(b)>
<4, C( )>
14
Exemplu LZ78
Index Intr.
1 w
2 a
3 b
4 ba
5
6 wa
7 bb
8 a
9 wab
10 ba
Dictionar:
Input: ------------------wabbawoowoowoo
Output:
<0, C(w)>
<0, C(a)>
<0, C(b)>
<3, C(a)>
<0, C( )>
<1, C(a)>
<3, C(b)>
<2, C( )>
<6, C(b)>
<4, C( )>
<9, C(b)>
11 wabb
15
Exemplu LZ78
Dictionar:
Input: ----------------------awoowoowoo
Output:
<0, C(w)>
<0, C(a)>
<0, C(b)>
<3, C(a)>
<0, C( )>
<1, C(a)>
<3, C(b)>
<2, C( )>
<6, C(b)>
<4, C( )>
<9, C(b)>
<8, C(w)>
11 wabb
12 a w
Index Intr.
1 w
2 a
3 b
4 ba
5
6 wa
7 bb
8 a
9 wab
10 ba
16
Exemplu LZ78
Dictionar:
Input: -------------------------oowoowoo
Output:
<0, C(w)>
<0, C(a)>
<0, C(b)>
<3, C(a)>
<0, C( )>
<1, C(a)>
<3, C(b)>
<2, C( )>
<6, C(b)>
<4, C( )>
<9, C(b)>
<8, C(w)>
<0, C(o)>
11 wabb
12 a w
13 o
Index Intr.
1 w
2 a
3 b
4 ba
5
6 wa
7 bb
8 a
9 wab
10 ba
17
Exemplu LZ78
Dictionar:
Input: --------------------------owoowoo
Output:
<0, C(w)>
<0, C(a)>
<0, C(b)>
<3, C(a)>
<0, C( )>
<1, C(a)>
<3, C(b)>
<2, C( )>
<6, C(b)>
<4, C( )>
<9, C(b)>
<8, C(w)>
<0, C(o)>
<13, C( )>
11 wabb
12 a w
13 o
14 o
Index Intr.
1 w
2 a
3 b
4 ba
5
6 wa
7 bb
8 a
9 wab
10 ba
18
Exemplu LZ78
Dictionar:
Input: ----------------------------woowoo
Output:
<0, C(w)>
<0, C(a)>
<0, C(b)>
<3, C(a)>
<0, C( )>
<1, C(a)>
<3, C(b)>
<2, C( )>
<6, C(b)>
<4, C( )>
<9, C(b)>
<8, C(w)>
<0, C(o)>
<13, C( )>
<1, C(o)>
11 wabb
12 a w
13 o
14 o
15 wo
Index Intr.
1 w
2 a
3 b
4 ba
5
6 wa
7 bb
8 a
9 wab
10 ba
19
Exemplu LZ78
Dictionar:
Input: ------------------------------owoo
Output:
<0, C(w)>
<0, C(a)>
<0, C(b)>
<3, C(a)>
<0, C( )>
<1, C(a)>
<3, C(b)>
<2, C( )>
<6, C(b)>
<4, C( )>
<9, C(b)>
<8, C(w)>
<0, C(o)>
<13, C( )>
<1, C(o)>
<14, C(w)>
11 wabb
12 a w
13 o
14 o
15 wo
16 o w
Index Intr.
1 w
2 a
3 b
4 ba
5
6 wa
7 bb
8 a
9 wab
10 ba
20
Exemplu LZ78
Dictionar:
Input: ---------------------------------oo
Output:
<0, C(w)>
<0, C(a)>
<0, C(b)>
<3, C(a)>
<0, C( )>
<1, C(a)>
<3, C(b)>
<2, C( )>
<6, C(b)>
<4, C( )>
<9, C(b)>
<8, C(w)>
<0, C(o)>
<13, C( )>
<1, C(o)>
<14, C(w)>
<13, C(o)>
11 wabb
12 a w
13 o
14 o
15 wo
16 o w
17 oo
Index Intr.
1 w
2 a
3 b
4 ba
5
6 wa
7 bb
8 a
9 wab
10 ba
21
LZ78
• Observatie▫ Daca continuam sa codificam, dictionarul continua sa
creasca
• Solutii practice▫ Oprirea cresterii dictionarului
efectiv, considerarea dictionarului ca unul static
▫ Micsorarea dictionarului
Ex. Pe baza statisticilor de utilizare
▫ Resetarea dictionarului
▫ Fara a cunoaste informatii specifice referitoare la sursa, tehnicile de mai sus nu garanteaza succesul
