Współczesny świat atakuje nas nieustannie informacjami - książki, radio, telewizja, komórki czy też Internet zalewają nas setkami tysięcy informacji każdego dnia. Poruszanie się w gąszczu tych wszystkich informacji efektywnie nie było możliwe dla żadnego człowieka zanim nie nastała era komputerów, Internetu i wyszukiwarek, które zrewolucjonizowały dostęp do informacji. Wyszukiwanie informacji jest również kluczowym elementem większości biznesowych aplikacji - a skoro tak, to warto poświęcić czas na naukę związaną z przeszukiwaniem informacji. W niniejszym rozdziale zajmiemy się przeszukiwaniem informacji, a dokładniej przeszukiwaniem tekstu.
Przeszukiwanie tekstu - podstawy
Wyszukiwanie frazy w tekście za pomocą gotowych narzędzi jest proste - nie musimy się bowiem zastanawiać
'jak napisać wyszukiwanie' tylko
'co chcemy znaleźć'. W bibliotece C++ zaimplementowano podstawowy mechanizm wyszukiwania frazy w tekście i z niego właśnie tutaj skorzystamy.
Klasa std::string - metoda find
Do wyszukiwania frazy występującej w tekście służy metoda
find, która należy do klasy
std::string. Metoda
find posiada kilka deklaracji, które różnią się przyjmowanymi argumentami - wybiera się zazwyczaj tą, która na daną chwilę jest dla nas najbardziej odpowiednia :) Deklaracje tej metody są następujące:
size_type find( value_type ch, size_type off = 0 ) const;
size_type find( const value_type * ptr, size_type off = 0 ) const;
size_type find( const value_type * ptr, size_type off, size_type count ) const;
size_type find( const basic_string & str, size_type off = 0 ) const;
Powyższe zapisy w maksymalnym uproszczeniu możesz spokojnie interpretować tak:
unsigned int find( char znak, unsigned int offset = 0 );
unsigned int find( const char * sNapis, unsigned int offset = 0 );
unsigned int find( const char * sNapis, unsigned int offset, unsigned int liczbaZnakow );
unsigned int find( const std::string & napis, unsigned int offset = 0 );
Metoda find - zwracana wartość
Wszystkie wymienione wyżej metody zwracają to samo - uściślając jest to pozycja na której znaleziono poszukiwany znak bądź poszukiwaną frazę. Jeżeli fraza bądź znak nie został odnaleziony w przeszukiwanym tekście to wówczas metoda
find zwraca wartość
std::string::npos. Na chwilę obecną może wydawać Ci się to odrobinę zagmatwane, jednak wszystko stanie się jasne po przeanalizowaniu przykładów, które będą w dalszej części niniejszego rozdziału. Warto jeszcze w tym miejscu wspomnieć, że pozycja wskazuje zawsze na pierwszy znak frazy, a numerowanie pozycji znaków w tekście zaczyna się od zera.
Wyszukiwanie znaku w tekście
Pierwsza z wymienionych metod służy do wyszukiwania znaku w tekście. Argument pierwszy to znak poszukiwany, natomiast drugi określa miejsce od którego należy szukać znaku w tekście. Kod, który będzie wyszukiwał określony znak w tekście może więc wyglądać tak:
#include <string>
#include <iostream>
void szukajZnaku( std::string & tekst, char szukanyZnak )
{
size_t znalezionaPozycja = tekst.find( szukanyZnak );
if( znalezionaPozycja == std::string::npos )
std::cout << "Nie znaleziono znaku w tekscie" << std::endl;
else
std::cout << "Znak zostal odnaleziony na pozycji " << znalezionaPozycja << std::endl;
}
int main()
{
std::string naszTekst = "Przyklad z kursu C++ (http://cpp0x.pl)";
szukajZnaku( naszTekst, 'k' );
return 0;
}
Jeżeli zechcemy wypisać wszystkie pozycje występowania określonego znaku w tekście to wystarczy wykorzystać dodatkowo do tego celu drugi argument metody
find. Przykład:
#include <string>
#include <iostream>
void szukajWszystkichZnakow( std::string & tekst, char szukanyZnak )
{
size_t znalezionaPozycja = tekst.find( szukanyZnak );
if( znalezionaPozycja == std::string::npos )
{
std::cout << "Nie znaleziono znaku w tekscie" << std::endl;
return;
}
do
{
std::cout << "Znak zostal odnaleziony na pozycji " << znalezionaPozycja << std::endl;
znalezionaPozycja = tekst.find( szukanyZnak, znalezionaPozycja + 1 );
} while( znalezionaPozycja != std::string::npos );
}
int main()
{
std::string naszTekst = "Przyklad z kursu C++ (http://cpp0x.pl)";
szukajWszystkichZnakow( naszTekst, 'z' );
return 0;
}
Wyszukiwanie frazy w tekście
Do wyszukiwania frazy w tekście służą pozostałe trzy metody
find. Argument pierwszy to łańcuch znaków, który ma zostać wyszukany. Drugim argumentem jest miejsce od którego należy rozpocząć wyszukiwanie frazy w tekście. Trzecim argumentem, który występuje tylko w jednej z czterech metod jest długość szukanej frazy - czasami się przydaje, jednak ten przypadek nie zostanie omówiony ponieważ praktycznego zastosowania w swoich programach nie znajdziesz z wiedzą, którą posiadasz na chwilę obecną. Przejdźmy teraz do przykładu:
#include <string>
#include <iostream>
void szukajWszystkichFraz( std::string & tekst, std::string szukanaFraza )
{
size_t znalezionaPozycja = tekst.find( szukanaFraza );
if( znalezionaPozycja == std::string::npos )
{
std::cout << "Nie znaleziono frazy w tekscie" << std::endl;
return;
}
do
{
std::cout << "Fraza zostala odnaleziona na pozycji " << znalezionaPozycja << std::endl;
znalezionaPozycja = tekst.find( szukanaFraza, znalezionaPozycja + szukanaFraza.size() );
} while( znalezionaPozycja != std::string::npos );
}
int main()
{
std::string naszTekst = "Przyklad z kursu C++ (http://cpp0x.pl) - najlepszy kurs C++ w Internecie!";
szukajWszystkichFraz( naszTekst, "C++" );
return 0;
}
W powyższym przykładzie wykorzystano metodę size klasy std::string. Metoda ta zwraca długość tekstu w znakach. Więcej o tej metodzie dowiesz się w następnym rozdziale.
|
Wyszukiwanie frazy od końca
Gdy przyjdzie Ci pracować z algorytmami tekstowymi, a w szczególności z przeszukiwaniem tekstu to z pewnością przyjdzie moment w którym będziesz miał potrzebę szukania frazy od tyłu tekstu. Klasa
std::string oczywiście dostarcza takie narzędzie i jest nim metoda
rfind. Znaczenie argumentów jakie przyjmuje metoda
rfind jest dokładnie takie samo jak w przypadku metody
find. Opis zwracanej wartości jest również analogiczny do metody
find z tą różnicą, że zwracana pozycja będzie pierwszą pasującą frazą od końca w przypadku pomyślnego wyszukiwania. Oto przykład wykorzystujący przeszukiwanie tekstu od końca:
#include <string>
#include <iostream>
void szukajWszystkichFrazOdKonca( std::string & tekst, std::string szukanaFraza )
{
size_t znalezionaPozycja = tekst.rfind( szukanaFraza );
if( znalezionaPozycja == std::string::npos )
{
std::cout << "Nie znaleziono frazy w tekscie" << std::endl;
return;
}
do
{
std::cout << "Fraza zostala odnaleziona na pozycji " << znalezionaPozycja << std::endl;
if( znalezionaPozycja >= szukanaFraza.size() )
znalezionaPozycja = tekst.rfind( szukanaFraza, znalezionaPozycja - szukanaFraza.size() );
else
znalezionaPozycja = std::string::npos;
} while( znalezionaPozycja != std::string::npos );
}
int main()
{
std::string naszTekst = "Przyklad z kursu C++ (http://cpp0x.pl) - najlepszy kurs C++ w Internecie!";
szukajWszystkichFrazOdKonca( naszTekst, "C++" );
return 0;
}
Zadanie domowe
Uzupełnij funkcję poniższego programu tak, aby zwróciła wartość
true tylko wtedy gdy oba wyrazy występują w zadanym łańcuchu tekstowym:
#include <iostream>
#include <string>
bool szukaj( std::string & tekst, std::string wyraz1, std::string wyraz2 )
{
return false;
}
void wypiszWynik( bool czyZnaleziono )
{
if( czyZnaleziono )
std::cout << "Znaleziono" << std::endl;
else
std::cout << "Nie znaleziono" << std::endl;
}
int main()
{
std::string napis = "Zadanie domowe z kursu C++ (http://cpp0x.pl) - najlepszy kurs C++ w Internecie!";
wypiszWynik( szukaj( napis, "ada", "kurs" ) );
wypiszWynik( szukaj( napis, "ada", "taki" ) );
wypiszWynik( szukaj( napis, "C++", "cpp0x" ) );
wypiszWynik( szukaj( napis, "C#", "cpp0x" ) );
return 0;
}
Oczekiwane standardowe wyjście programu dla podanego zadania:
Znaleziono
Nie znaleziono
Znaleziono
Nie znaleziono