OBOWIĄZKOWE DO PRZESŁANIA: jedno zadanie
Podstawowe definicje [Banachowski, Diks, Rytter].
Dwie typowe reprezentacje tekstów to reprezentacja listowa i reprezentacja tablicowa. Reprezentacja listowa jest użyteczna przy dużej liczbie operacji wstawiania lub usuwania części tekstu. Reprezentacja tablicowa przydaje się przy statycznych operacjach.
Dane wejściowe algorytmów tekstowych to jeden lub więcej tekstów. Rozmiar danych wejściowych to zwykle długość tekstu (suma długości tekstów).
Niech x będzie wzorcem, a y tekstem, w którym szukamy wzorca. Przyjmujemy, że |x|=m, |y|=n, oraz m <= n. Mówimy, że x występuje w y na pozycji i, jeżeli y[i..i+m-1]=x. Problem wyszukiwania wzorca polega na znalezieniu wszystkich wystąpień wzorca x w tekście y. Wybrane algorytmy wyszukiwania (dopasowywania) wzorca:
// Funkcja na bazie [Wróblewski].
// Liczba porównań w najgorszym przypadku to m(n-m+1).
int pattern_matching(std::string text, std::string pattern) {
int i, j;
int n = text.size();
int m = pattern.size();
if (n == 0 || m == 0)
return -1;
for (i=0, j=0; j < m && i < n; i++, j++) {
if (text[i] != pattern[j]) {
i = i-j; // jakby o jeden za daleko
j = -1; // jakby o jeden za daleko
}
}
return ((j == m) ? (i-m) : (-1));
}https://pl.wikipedia.org/wiki/Algorytm_Knutha-Morrisa-Pratta
i: 01234567890123456789012 t: ABC ABCDAB ABCDABCDABDE p: ABCDABD j: 0123456 Niezgodność t[3]!=p[3]. Przesuwamy się do następnego A, i=4, j=0.
i: 01234567890123456789012 t: ABC ABCDAB ABCDABCDABDE p: ABCDABD j: 0123456 Niezgodność t[10]!=p[6]. Przesuwamy się do następnego A, ale AB pod koniec może być początkiem nowego dopasowania. Ustawiamy i=10, j=2 (nie od zera!).
i: 01234567890123456789012 t: ABC ABCDAB ABCDABCDABDE p: ABCDABD j: 0123456 Niezgodność od razu t[10]!=p[2]. Przesuwamy się do następnego A, i=11, j=0.
i: 01234567890123456789012 t: ABC ABCDAB ABCDABCDABDE p: ABCDABD j: 0123456 Niezgodność t[17]!=p[6]. Przesuwamy się do następnego A, ale AB pod koniec może być początkiem nowego dopasowania. Ustawiamy i=17, j=2 (nie od zera!).
i: 01234567890123456789012 t: ABC ABCDAB ABCDABCDABDE p: ABCDABD j: 0123456 Dochodzimy do i=22, j=7=m, pełne dopasowanie od pozycji i-j=i-m=15.
|j |0 |1 |2 |3 |4 |5 |6 | |pattern[j]|A |B |C |D |A |B |D | |shift[j] |-1|0 |0 |0 |0 |1 |2 |
// Funkcja na bazie [Wróblewski]. Złożoność O(n+m).
void init_shifts(std::string pattern, int shift[]) {
int i = 0, j = 0;
int m = pattern.size();
shift[0] = -1;
for (i=0, j=-1; i < m-1; i++, j++, shift[i] = j) {
while (j >= 0 && pattern[i] != pattern[j]) {
j = shift[j];
}
}
}
int kmp(std::string text, std::string pattern) {
int i, j;
int n = text.size();
int m = pattern.size();
if (n == 0 || m == 0)
return -1;
int *shift = new int[m];
init_shifts(pattern, shift);
for (i=0, j=0; j < m && i < n; i++, j++) {
while (j >= 0 && text[i] != pattern[j]) {
j = shift[j];
}
}
delete [] shift;
return ((j == m) ? (i-m) : (-1));
}
W tekstach zapisujemy informację i ta informacja jest często przekazywana pomiędzy różnymi punktami przez pewne medium transmisyjne. Szybkość przekazywania danych można zwiększyć ulepszając medium transmisyjne lub przez zmianę samych informacji [Drozdek].
Kompresja danych zmniejsza rozmiar reprezentacji danych
bez zmiany samych danych. Załóżmy, że do zakodowania informacji jest
wykorzystywanych n różnych symboli m_i (i=1,...,n).
Niech P(m_i) będzie prawdopodobieństwem wystąpienia symbolu m_i. Wtedy
P(m_1)+...+P(m_n)=1.
Zawartość informacji zbioru M, nazywana entropią źródła M,
jest zdefiniowana jako
L(M)=P(m_1)L(m_1)+...+P(m_n)L(m_n),
gdzie L(m_i)=-lg(P(m_i)), co stanowi minimalną długość słowa
kodowego symbolu m_i.
Shannon (1948) stwierdził, że L(M) daje najlepszą możliwą średnią
długość słowa kodowego, kiedy znane są zarówno symbole źródlowe,
jak i prawdopodobieństwo ich użycia.
Przykład. Dla trzech symboli mamy P(m_1)=P(m_2)=1/4, P(m_3)=1/2, L(M)=(1/4)*2+(1/4)*2+(1/2)*1=3/2.
Stopień kompresji to (len(input)-len(output))/len(input). Ograniczenia wymagane dla kodów:
+------+--------------+-----------------+-----------------+ |Symbol|Kod prawidłowy|Kod nieprawidłowy|Kod nieprawidłowy| +------+--------------+-----------------+-----------------+ | A | 00 | 0 | 0 | +------+--------------+-----------------+-----------------+ | B | 01 | 1 | 11 | +------+--------------+-----------------+-----------------+ | C | 10 | 01 | 01 | +------+--------------+-----------------+-----------------+
Wybrane algorytmy kompresji danych.
|Symbol | A | B | C | D | E | |Prawdopodobieństwo|0.39|0.21|0.19|0.12|0.09| |Kod I |11 |10 |00 |011 |010 | |Kod II |11 |01 |00 |101 |100 | Średnia długość słowa: L_H(M)=0.39*2+0.21*2+0.19*2+0.12*3+0.09*3=2.21 Entropia źródła: L(M)=2.09 (różnica 5%) Drzewa nie są wyznaczone jednoznacznie, ale średnia długość słowa tak.
| ( 0.09 0.12 ) 0.19 0.21 0.39
| ( 0.19 0.21 ) 0.21 0.39 | ( 0.19 0.21 ) 0.21 0.39 | | / \ | / \ | | 0.09 0.12 | 0.09 0.12 |
| ( 0.21 0.39 ) 0.40 | ( 0.21 0.39 ) 0.40 | | / \ | / \ / \ | | 0.19 0.21 | 0.09 0.12 0.19 0.21 | | / \ | | | 0.09 0.12 | |
| ( 0.40 0.60 ) | ( 0.40 0.60 ) | | / \ / \ | / \ / \ | | 0.19 0.21 0.21 0.39 | 0.19 0.21 0.21 0.39 | | / \ | / \ | | 0.09 0.12 | 0.09 0.12 |
| 1.0 | 1.0 | | 0/ \1 | 0/ \1 | | 0.40 0.60 | 0.40 0.60 | | 0/ \1 0/ \1 | 0/ \1 0/ \1 | | 0.19 0.21 0.21 0.39 | 0.19 0.21 0.21 0.39 | | (C) 0/ \1 (B) (A) | (C) (B) 0/ \1 (A) | | 0.09 0.12 | 0.09 0.12 | | (E) (D) | (E) (D) |
Implementacja algorytmu Huffmana może być wykonana na wiele sposobów. Wykorzystywana jest kolejka priorytetowa do przechowywania poddrzew. Inna implementacja może wykorzystywać posortowaną listę podwójnie powiązaną.
// https://en.cppreference.com/w/cpp/string
// https://en.cppreference.com/w/cpp/string/basic_string
#include <string>
#include <iostream>
std::string s = "0123456789abcdefghij";
// std::string s { "0123456789abcdefghij" };
// std::string s("0123456789abcdefghij");
// s.empty()
// s.size()
// s.capacity()
// s.clear() // nie zmienia capacity, erase(begin(), end())
// Return value: (1) *this or (2+3) iterator
// (1) s.erase(index=0, count=npos) usuwa min(count, size()-index) znaków
// (2) s.erase(first) usuwa jeden znak
// (3) s.erase(first, last) usuwa znaki z zakresu
// Return value: string // s.substr(pos=0, count=npos) substring [pos, pos+count) // std::string::npos znacznik końca napisu // jeżeli pos > s.size() to rzuca wyjątek // count is npos, returns [pos, size()) std::string sub1 = s.substr(10); // abcdefghij // both pos and pos+count are within bounds, returns [pos, pos+count) std::string sub2 = s.substr(5, 3); // 567 // pos is within bounds, pos+count is not, returns [pos, size()) std::string sub3 = s.substr(s.size()-3, 50); // hij
// Return value: *this
// (1) s.replace(pos, count, str)
// (1) s.replace(first, last, str)
// (2) s.replace(pos, count, str, pos2, count2)
// (3) s.replace(first, last, first2, last2)
// (4) s.replace(pos, count, cstr, count2)
// (4) s.replace(first, last, cstr, count2)
// (5) s.replace(pos, count, cstr)
// (5) s.replace(first, last, cstr)
// (6) s.replace(pos, count, count2, ch)
// (6) s.replace(first, last, count2, ch) count2 to liczba kopii ch
std::string s("The quick brown fox jumps over the lazy dog.");
s.replace(10, 5, "red"); // brown -> red
s.replace(s.begin(), s.begin() + 3, 1, 'A'); // The -> A
// Return value: position or npos
// (1) s.find(str, pos=0) finds the first substring equal to str
// (2) s.find(cstr, pos, count)
// finds the first substring equal to the range [cstr, cstr+count)
// (3) s.find(cstr, pos=0)
// finds the first substring equal to the character string pointed to by cstr
// (4) s.find(ch, pos=0) finds the first character ch
// Wypisuje znaki od pozycji n do końca stringu.
void print(std::string::size_type n, std::string &s) {
if (n == std::string::npos) {
std::cout << "not found\n";
} else {
std::cout << "found: " << s.substr(n) << '\n';
}
}
std::string::size_type n;
std::string s("This is a string");
// search from beginning of string
n = s.find("is");
print(n, s); // found: is is a string
// search from position 5
n = s.find("is", 5);
print(n, s); // found: is a string
// find a single character from beginning
n = s.find('a');
print(n, s); // found: a string
// find a single character
n = s.find('q');
print(n, s); // not found
// https://en.cppreference.com/w/cpp/algorithm/find #include <algorithm> template<class Iterator, class T> Iterator find(Iterator first, Iterator last, const T& value) // Return value: Iterator to the first element satisfying the condition // or last if no such element is found.
Zaimplementować wybrany algorytm wyszukiwania wzorca w tekście.
Zaimplementować algorytm Huffmana.