plik

Spis treści

1.WSTĘP..................................................................................................................................................................4

1.1.W

YSZUKIWANIE

PEŁNOTEKSTOWE

INFORMACJI

......................................................................................................... 4

1.2.C

PRACY

........................................................................................................................................................4

1.3.R

OZWIĄZANIE

PRZYJĘTE

PRACY

..........................................................................................................................5

1.4.T

ECHNOLOGIA

NARZĘDZIA

ZASTOSOWANE

PRACY

................................................................................................5

1.5.R

EZULTATY

PRACY

..............................................................................................................................................7

1.6.O

RGANIZACJA

PRACY

...........................................................................................................................................7

2.WYSZUKIWANIE PEŁNOTEKSTOWE – RÓŻNE PODEJŚCIA...............................................................9

2.1.K

ONTEKST

PRACY

...............................................................................................................................................9

2.2.S

TAN

SZTUKI

....................................................................................................................................................10

2.3.N

ASZE

ROZWIĄZANIE

.........................................................................................................................................12

3.OPIS NARZĘDZI ZASTOSOWANYCH W PRACY....................................................................................15

3.1.O

BIEKTOWA

BAZA

DANYCH

BJECTIVITY

/DB.......................................................................................................15

3.2.J

AVA

...............................................................................................................................................................22

3.3.G

RAM

.............................................................................................................................................................23

3.4.P

YTHON

..........................................................................................................................................................23

3.5.P

OSTGRE

SQL..................................................................................................................................................24

3.6.L

EAFNODE

.......................................................................................................................................................25

3.7.B

IBLIOTEKI

.....................................................................................................................................................25

4.OBIEKTOWOŚĆ A WYSZUKIWANIE PEŁNOTEKSTOWE...................................................................27

4.1.O

BIEKTOWOŚĆ

WYSZUKIWANIE

INFORMACJI

.......................................................................................................27

4.2.O

MÓWIENIE

PRZYJĘTEGO

ROZWIĄZANIA

.................................................................................................................30

4.3.A

LGORYTM

INDEKSOWANIA

.................................................................................................................................33

4.4.A

LGORYTM

WYSZUKIWANIA

................................................................................................................................37

4.5.A

LTERNATYWNE

KONCEPCJE

...............................................................................................................................44

5.ROZWIĄZANIA IMPLEMENTACYJNE: SYSTEM ŚCIĄGANIA, INDEKSOWANIA I

WYSZUKIWANIA NEWSÓW............................................................................................................................50

5.1.O

PIS

NAJWAŻNIEJSZYCH

KLAS

..............................................................................................................................51

5.2.I

MPLEMENTACJA

FETCHERA

NARZĘDZIA

BACKUPUJĄCEGO

.......................................................................................56

5.3.I

MPLEMENTACJA

INDEKSOWANIA

..........................................................................................................................57

5.4.I

MPLEMENTACJA

WYSZUKIWANIA

............................................................. ............................................................ 62

5.5.F

RONTEND

.......................................................................................................................................................68

6.PROBLEMY ZWIĄZANE Z ZASTOSOWANYM ROZWIĄZANIEM......................................................70

6.1.P

ROBLEMY

NAPOTKANE

PODCZAS

IMPLEMENTACJI

...................................................................................................70

6.2.W

ADY

ZALETY

PRZYJĘTEGO

ROZWIĄZANIA

..........................................................................................................73

6.3.Z

ASTOSOWANIE

PRACY

......................................................................................................................................74

6.4.P

LANY

PRZYSZŁOŚĆ

......................................................................................................................................74

7.PODSUMOWANIE...........................................................................................................................................79

PRACE CYTOWANE..........................................................................................................................................80

1. Wstęp

1.1.

Wyszukiwanie pełnotekstowe informacji

Internet to w tej chwili największe światowe repozytorium wiedzy ze wszystkich prawie

dziedzin naszego życia. Dziesiątki tysięcy artykułów na każdy możliwy temat dostępne są w, niestety
poważnie zaniedbanej, publicznej bibliotece. Większość całkowicie za darmo. Internet bywa nieraz
określany jako największy śmietnik świata. Wyszukanie pożądanej informacji wśród tysięcy ton „e-
makulatury” wydaje się więc być zadaniem godnym szaleńca. Zwłaszcza, jeśli informacja ma być
dokładna,   a   czas   potrzebny   na   jej   znalezienie   akceptowalny.   Informacja   której   poszukujemy
najprawdopodobniej  jest  jednak na wyciągnięcie  ręki. Problem, z którym zmagają się nieustannie
tysiące internautów na całym świecie to: jak mądrze po nią sięgnąć. Podobnie, choć na nieco mniejszą
skalę, rzecz się ma z internetowymi grupami dyskusyjnymi. Tu również, a  czasem tylko tu, możemy
znaleźć rozwiązanie dręczącego nas problemu. Tutaj także, niestety nazbyt często, mamy do czynienia
z   niekompetencją,   niewiedzą   i   całą   masą   informacji   często   zbędnych   lub   nieprawdziwych,
dostarczanych   przez   nadgorliwych   użytkowników   Usenetu.   Odfiltrowanie   śmieci   od   praktycznej
wiedzy wydaje się być w takiej sytuacji nieuniknionym zadaniem.
W   obu   tych   przypadkach,   z   pomocą   przychodzą   nam   aplikacje   zwane   wyszukiwarkami
pełnotekstowymi. To dzięki nim możemy bez obawy usiąść przed ekranem komputera i nie tracąc
czasu na żmudne poszukiwania, w kilka sekund otrzymać listę artykułów dotyczących interesującego
nas zagadnienia i spełniających podane przez nas kryteria. Tylko czy aby na pewno? Czy zawsze
jesteśmy w stanie znaleźć dzięki nim informację, której oczekujemy? A może często zdarza nam się
ślęczeć   całymi   godzinami   przed   komputerem,   przeglądając   kolejne,   całkowicie   nierelewantne
rezultaty wyszukiwania, z nadzieją że ten kolejny będzie w końcu właściwy?  Zapewne zdarzają się
również i takie sytuacje. Powód jest prosty – uniwersalne produkty (a do takiego statusu dążą obecni
liderzy   w   branży   wyszukiwarek   internetowych)   nigdy   nie   będą   w   stanie   spełnić   bardziej
specyficznych wymagań zaawansowanych użytkowników.

Zbudowanie idealnej wyszukiwarki, zawsze znajdującej adekwatne i interesujące nas dane jest

oczywiście (wbrew temu co próbują niekiedy wcisnąć nam specjaliści od reklamy) niemożliwą do
zrealizowania   utopią.   Dlatego   też   celem,   który   powinniśmy   sobie   stawiać   nie   może   być   jeden
uniwersalny   i   niezastąpiony   program,   lecz   raczej   stworzenie   jak   największej   ilości   bardzo
specyficznych   rozwiązań,   ułatwiających   nam   życie   (czyli   uzyskanie   właściwej   informacji)   w
poszczególnych dziedzinach. Jedną z takich dziedzin, w których brakuje obecnie niestety dobrego,
dedykowanego   mechanizmu   wyszukiwania,   jest   światowe   (a   w   szczególności   polskie)   archiwum
internetowych grup dyskusyjnych. Mimo, że dostępna jest w sieci całkiem spora ilość wyszukiwarek
indeksujących grupy, nie istnieje aplikacja, która koncentruje się wyłącznie na tym zagadnieniu i robi
to dobrze. A właśnie koncentracja i specyficzne podejście do konkretnego problemu jest warunkiem
(lecz oczywiście nie jedynym kryterium) sukcesu takiego projektu. Niniejsza praca jest jedną z prób
podjęcia się takiego właśnie wyzwania – stworzenie dedykowanej wyszukiwarki pełnotekstowej, dla
polskich grup dyskusyjnych.

1.2.

Cel pracy

Celem naszej pracy jest przedstawienie jednego z możliwych rozwiązań problemu

pełnotekstowego wyszukiwania  informacji  w dużych zbiorach danych. Nie  jest  naszym zadaniem
zaproponowanie   uniwersalnego   modelu,   lecz   raczej   przedstawienie   pewnej   koncepcji   budowy   i
działania   wyszukiwarki   ukierunkowanej   na   wydobywanie   specyficznego   rodzaju   informacji   z
wcześniej zdefiniowanych zasobów. Jak wiadomo, trafność wyniku nie jest miarą obiektywną, lecz
zdefiniowaną   li   tylko   przez   wymagania   konkretnego   użytkownika.   Przy   tworzeniu   wyszukiwarki

konieczne jest więc dokładne określenie  sposobu pomiaru trafności wyników wyszukiwania. Na tej
podstawie  możliwe  będzie  bowiem sprawdzenie   czy i w jakim  stopniu  zakładana  funkcjonalność
(rezultaty wyszukiwania) została osiągnięta.
W   związku   z   tym,   w   naszej   pracy   postanowiliśmy   skoncentrować   się   na   kilku   cechach,   które
uważamy za ważne, a które często nie są uznawane za priorytetowe w istniejących produktach. Przede
wszystkich chcemy więc, aby zwracane wyniki zapytań były:

–

dokładne – chodzi o to, żeby użytkownik dostawał w wynikach wyszukiwania przede wszystkim
artykuły zawierające szukane przez niego całkowite ciągi słów, a dopiero z dalszym priorytetem
artykuły, które spełniają podane warunki tylko częściowo

–

niezależne od momentu w czasie – nieważne czy dany artykuł został napisany całkiem
niedawno, czy dziesięć lat temu, powinien się on pojawić w wynikach wyszukiwania z takim
samym priorytetem (o ile oczywiście nie została zaznaczona opcja wyboru przedziału
czasowego)

–

trwałe – jest to powiązane bezpośrednio z niezależnością w czasie i chodzi o to, żeby uniknąć
zjawiska “gubienia” artykułów – często występującego w popularnych wyszukiwarkach newsów
(również Google) – polegającego na marginalizacji a w końcu ignorowaniu wyników starszych w
czasie

Ponadto, ze względu na specyfikę języka polskiego, uznaliśmy, że istotne jest również, żeby

wyszukiwarka uwzględniała w swoim działaniu składnię języka polskiego, tj aby wyniki
prezentowane były niezależnie od formy fleksyjnej poszczególnych słów zapytania.

1.3.

Rozwiązanie przyjęte w pracy

Nasze rozwiązanie charakteryzuje się:

–

zastosowaniem podejścia obiektowego do projektowania i implementacji

–

odejściem od ograniczeń relacyjnych baz danych poprzez zastosowanie w projekcie bazy
obiektowej, bardziej adekwatnej dla omawianego problemu

–

wysokim stopniem modularyzacji systemu – zamiast tworzenia jednej aplikacji odpowiadającej
za całość mechanizmów niezbędnych do osiągnięcia zakładanych rezultatów, postawiono na
stworzenie wielu niezależnych aplikacji, ściśle ze sobą współpracujących

–

łatwością rozbudowy tworzonego systemu, optymalizacji czy dodania nowej funkcjonalności,
poprzez zastosowanie standardowych metod dokumentacji zarówno koncepcji projektowych
(UML) jak i samego kodu aplikacji (JavaDoc)

1.4.

Technologia i narzędzia zastosowane w pracy

Technologia, którą wybraliśmy do implementacji nie jest przypadkowa i ma bezpośredni

związek z założeniami przyjętego wcześniej rozwiązania.
Projekt został zrealizowany z użyciem następującego oprogramowania:

–

Obiektowa baza danych Objectivity/DB 8.0, obecnie jeden z liderów światowych w dziedzinie
zaawansowanych rozwiązań bazodanowych, oferujący między innymi: zarządzanie transakcjami,
wiązanie do Javy oraz wiele rodzajów zależności (relacji) między obiektami.

–

Obiektowy język programowania Java (połączenie wersji standardowej, J2SE, z wersją
enterprise, czyli J2EE – ta druga głównie do implementacji frontendu)

–

Obiektowy język skryptowy Python – wybrany do kilku specyficznych zastosowań, głównie w
celu optymalizacji (użycie Javy było niekiedy zbyt kosztowne ze względu na prędkość działania
lub niemożliwe ze względu na brak odpowiednich, niezawodnych bibliotek),

–

Program Gram 2.4.3 firmy Neurosoft – oparta na standardzie CORBA aplikacja, przeznaczona
do analizy językowej tekstu,

–

OmniORB – serwer CORBA, poprzez który aplikacja łączy się z programem Gram,

–

Serwer grup dyskusyjnych Leafnode odpowiedzialny za ściąganie wiadomości z archiwum
Usenetu na dysk

–

Serwer aplikacji Tomcat, oparty na Javie, który odpowiada za działanie frontendu aplikacji

–

CVS – program do kontroli wersji oprogramowania, przydatny przy równoległej pracy nad
kodem i dokumentacją

–

Dia – darmowa aplikacja (na licencji GPL) do rysowania diagramów (w tym UML),

–

OpenOffice.org – darmowy pakiet biurowy (licencja GPL) w którym powstała praca, składający
się m.in. z edytora tekstu Writer oraz narzędzia do tworzenia prezentacji Impress

–

Zintegrowana platforma programistyczna Eclipse IDE, szczególnie przystosowana do tworzenia
zaawansowanych projektów z użyciem technologii opartych o język Java

–

System operacyjny: Debian GNU/Linux.

Wybór Objectivity jako podstawowej bazy danych był ryzykowny. Po pierwsze ze względu na

małą popularność stosowania obiektowych baz danych do tego typu rozwiązań, po drugie ze względu
na nasze doświadczenia zawodowe, które opierają się głównie na znajomości baz relacyjnych. Już po
krótkim   czasie   pracy   okazało   się   jednak   że   był   to   wybór   prawidłowy.   Baza   danych   nastawiona
bardziej   na   referencje,   niż   przeszukiwanie   zawartości   nadaje   się   idealnie   do   zastosowania   w
projektach,  w  których   ściśle  określona   jest  struktura  danych  i   dokładnie   wiemy jakie   informacje
chcemy z tych danych uzyskać (mówiąc ściślej – jakie zapytania będziemy chcieli zoptymalizować,
już na poziomie kodu programu). Idea relacyjnej  bazy danych – czyli uniwersalny, deklaratywny
język zapytań, byłby w przypadku naszej aplikacji niepotrzebnym i – co zostanie udowodnione w
części dalszej pracy – bardzo kosztownym narzutem.

Java została wybrana natomiast z co najmniej dwóch względów. Po pierwsze, jest to

nowoczesny,   spójny   i   prawdziwie   obiektowy   język   programowania,   doskonale   nadający   się   do
zastosowania w aplikacji,  w której  większość  funkcjonalności   można rozpisać poprzez diagramy
UML, operujące na obiektach (de facto, wszystkie operacje, zarówno na poziomie aplikacji jak i bazy
danych reprezentowane są w naszej aplikacji z użyciem abstrakcji obiektowej). Po drugie – Java jest
(obok C++) najlepiej wspieranym przez Objectivity językiem programowania. W pakiecie dostępna
jest   dokładna   dokumentacja   użytkowa,   jak   również   biblioteki,   zapewniające   pełne   wykorzystanie
standardowych,   jak   również   bardziej   zaawansowanych   funkcji,   oferowanych   przez   Objectivity.
Przykładem   może   być   rozszerzenie   języka   Java   o   specyficzne   dla   Objectivity   relacje   (ang.
relationships)   –   czyli   związki   asocjacyjne   pomiędzy   klasami   (również   typu   wiele-do-wiele),
reprezentacja   wszystkich  rodzajów  kolekcji   stosowanych   w  bazie   jako obiekty Javy, jak również
operacje  na federacji, znajdujących się w niej bazach danych, kontenerach oraz wszelkich innych
obiektach systemowych udostępnionych przez Objectivity/DB.

Przy wyborze pozostałych narzędzi, staraliśmy się zwracać uwagę na takie aspekty jak:

–

skalowalność, przystosowanie narzędzia do przetwarzania dużych ilości danych

–

uniwersalność (chodzi o to, żeby przy niewielkim nakładzie pracy możliwe byłoby przystosowanie
aplikacji i/lub środowiska programistycznego do pracy w innym środowisku, np. do działania w
systemie operacyjnym Microsoft Windows)

–

niezawodność, dojrzałość narzędzia – szczególnie korzystając z aplikacji typu open-source, na
licencji GPL lub podobnych, bardzo ważne jest zbadanie dojrzałości rozwiązania i przystosowania
do intensywnej eksploatacji

–

łatwość instalacji i obsługi – aby kwestie techniczne nie przesłoniły głównego, merytorycznego
aspektu pracy (m.in. dlatego postawiliśmy na system operacyjny Debian GNU/Linux, który
charakteryzuje się ogromną łatwością instalacji oprogramowania i ogólną dostępnością większości
potrzebnych nam aplikacji)

1.5.

Rezultaty pracy

Rezultatem naszej pracy jest działający i w pełni funkcjonalny system wyszukiwania

pełnotekstowego wiadomości z archiwum polskich grup dyskusyjnych. Składa się on z modułów, z
których każdy odpowiedzialny jest za oddzielne zadania związane z działaniem wyszukiwarki.

Krótka specyfikacja poszczególnych modułów:

•

fetcher – serwer ściągający nowe wiadomości z polskich grup dyskusyjnych i zapisujący je na
twardym dysku w postaci plików

•

backuper – narzędzie backupujące ściągane przez fetcher artykuły poprzez zapisywanie ich w nie
przetworzonej formie jednocześnie do dwóch baz danych: relacyjnej bazy PostgreSQL oraz
docelowej, obiektowej bazy Objectivity/DB

•

indekser  –   aplikacja   przetwarzająca   zapisane   w   prostej   formie   artykuły   do   postaci
usystematyzowanej,   w   celu   takiej   organizacji   informacji   w   bazie,   aby   samo   wyszukiwanie
sprowadziło   się   do   prostych   operacji   na   danych,   a   najlepiej   ograniczyło   się   tylko   do
przechodzenia po referencjach pomiędzy obiektami

•

wyszukiwarka – główna i jedyna widoczna dla końcowego użytkownika aplikacja, której
zadaniem jest zwrócenie odpowiednich wyników (artykułów) w zależności od podanego przez
użytkownika zapytania (zazwyczaj szukanego ciągu słów)

•

optymalizator – program działający w tle, którego zadaniem jest wykonywanie najczęściej
pojawiających się zapytań i zbieranie zaktualizowanych wyników takiego wyszukiwania; dzięki
niemu prezentacja wyników takich zapytań jest możliwa „od ręki” - bez potrzeby wyszukiwania,
gdyż są ode przetrzymywane bezpośrednio w bazie danych; przy czym optymalizator został
zaimplementowany tylko częściowo: w bazie przechowywane są zapytania wraz z ich wynikami,
nie ma jednak mechanizmu aktualizującego te zapytania

1.6.

Organizacja pracy

Pracę możemy podzielić na trzy zasadnicze najważniejsze części:

1. Omówienie problemu i możliwych rozwiązań

Pierwsza   część   pracy   zawiera   dokładne   omówienie   kontekstu   pracy.   Odwołuje   się   do
istniejących w chwili obecnej rozwiązań podobnego problemu wskazując ich najważniejsze
zalety i wady. Prezentuje  też w sposób ogólny nasze podejście do problemu. W dalszej
części   omówione   zostają   szczegółowo   narzędzia,   które   wykorzystujemy   w   pracy,   ze
szczególnym   uwzględnieniem   obiektowej   bazy   Objectivity/DB,   odpowiedzialnej   za
utrwalanie danych w prezentowanym systemie.

2. Omówienie naszego rozwiązania

2. Wyszukiwanie pełnotekstowe – różne podejścia

W tym rozdziale opisany został kontekst pracy oraz obecny stan sztuki odnośnie problemu

pełnotekstowego wyszukiwania informacji. Na końcu rozdziału naszkicowane zostało proponowane
przez nas rozwiązanie problemu.

2.1.

Kontekst pracy

Dzięki Internetowi zyskujemy dostęp do niemal nieograniczonego zbioru danych. Sporo jest

zasobów bardzo wartościowych, jednak toną one w oceanie śmieci i bezużytecznego szumu
informacyjnego. Wyłuskanie wartościowych treści, nawet spośród zasobów danych powstających w
ciągu tylko jednego dnia, jest zadaniem bardzo czasochłonnym. A co, jeśli chcielibyśmy zebrać
informacje z zasobów zgromadzonych w ciągu kilku lat? Jedynym rozwiązaniem problemu dotarcia
do interesujących nas danych jest stworzenie mechanizmu pozwalającego na szybkie ograniczenie
zbioru dokumentów do odpowiadającego nam zakresu oraz ułożenia ich w odpowiedniej kolejności.
Narzędzia takie nazywamy pełnotekstowymi wyszukiwarkami internetowymi.

Wyszukiwarki internetowe są to aplikacje udostępniane najczęściej przez strony WWW. Ich

zadaniem jest wyszukiwanie i prezentowanie odnośników do dokumentów spełniających określone
przez użytkownika kryteria. Głównym kryterium wyszukiwania informacji są zapytania o
występowanie konkretnych słów lub zdań w treści artykułów. Osoba korzystająca z takiego narzędzia
podaje jedno lub więcej słów, które powinien zawierać wyszukany dokument. Aplikacja znajduje
wszystkie dokumenty dla podanego zapytania oraz ustawia je według szacowanej trafności.

Zasoby WWW można podzielić na dwie grupy: strony publikowane przez organizacje oraz

strony   prywatne.   W   przypadku   witryn   firm   i   organizacji   można   się   spodziewać,   iż   treści   tam
prezentowane   będą   odpowiednio  ustrukturalizowane  oraz   że   będą   one   raczej   dobrej   jakości.   W
przypadku stron prywatnych, a takich jest dużo więcej, struktury informacji są raczej luźne, a treści
często bezwartościowe. Większość dzisiejszych wyszukiwarek zoptymalizowana jest w ten sposób, iż
strony prywatne umieszczane są niżej w ocenach trafności od stron organizacji i firm.
Zupełnie inaczej wygląda sprawa w archiwum grup dyskusyjnych. Jak sama nazwa wskazuje, grupy
służą do wymiany informacji  i poglądów przez użytkowników Usenetu. Nie można tutaj dokonać
podobnego podziału, jak w przypadku stron WWW. Wszystkie osoby i podmioty udzielające się w
dyskusjach   traktowaną   są   jednakowo.   Nie   istnieje   bowiem   możliwość   stworzenia   uniwersalnego
mechanizmu oceniającego wiarygodność danego autora, a wszelkie próby takiej klasyfikacji skończyć
się   mogą   kompromitacją   wyszukiwarki   –   nietrudno   bowiem   oszukać   automat,   choćby   poprzez
podawanie  fałszywego adresu  zwrotnego e-mail,  czy  też  wysyłanie  wiadomości  poprzez  roboty z
różnych lokalizacji.

Budowa Usenetu, czyli grup dyskusyjnych, różni się diametralnie od struktury stron WWW.

World-Wide-Web   stanowi   rodzaj   grafu   skierowanego.   Każda   strona   stanowi   jego   wierzchołek   a
każdy   link   jest   krawędzią.   Istnieje   prawie   nieskończenie   wiele   możliwości   połączeń   pomiędzy
stronami. W przypadku grup dyskusyjnych mamy do czynienia bardziej z sekwencją drzew, niż z
grafem.   Każda   grupa   dyskusyjna   posiada   swoją   własną   sekwencję   postów   głównych,   nie
posiadających ojców, od których zaczynają się wszystkie wątki. Każdy wątek zorganizowany jest na
zasadzie drzewa. Dowolny post  w wątku może posiadać  tylko jednego ojca  i jednocześnie może
posiadać dowolną liczbę odpowiedzi, które także mogą posiadać swoje odpowiedzi, itd. Posty nie są
w żaden sposób połączone między sobą poza relacją ojciec-dziecko (post-odpowiedź).

i   jak   się   wydaje   to,   że   jest   bardzo   oczywisty.   PageRank   nadaje   dokumentom   WWW   ocenę   na
podstawie  liczby odnośników wychodzących i wchodzących. Im jest  ich więcej,  tym wyższa jest
ocena. Założeniem tego algorytmu jest to, iż im więcej strona posiada linków do innych stron, tym
wydaje   „ważniejsza”   jest   dla   użytkownika,   ponieważ   trafiwszy   na   nią   ma   on   większe  szanse   na
dotarcie do interesujących go danych. Na tej samej zasadzie, jeśli wiele miejsc w sieci posiada link do
danej strony, świadczy to o tym, iż jest ona interesująca dla większej grupy ludzi.

Algorytm ten jest kompletnie nieprzydatny w przypadku grup dyskusyjnych. Nie ma tutaj

bowiem rozbudowanej sieci linków. Każdy post posiada co najwyżej jednego posta-ojca i może
posiadać dowolną liczbę odpowiedzi, podczepionych pod niego, jednak nie świadczy to w żaden
sposób o jego ważności. W związku ze specyficzną budową Usenetu trudno tu o jakikolwiek algorytm
oceny trafności postów. Trudno jest też oceniać posty na podstawie ich autorów. Jedyną daną jaką
jesteśmy w stanie wydobyć na temat autorów to to, ile postów na danej grupie zamieścili do tej pory.
Nie jest to wskaźnik, który pokazuje nam stopień profesjonalizmu wypowiedzi. Element ten może być
tylko ciekawą informacją w statystyce natomiast nie nadaje się zbytnio do oceny trafności wyników.

Mechanizm działania wyszukiwarki można przedstawić jako trzy główne etapy. Są to:

1. Ściąganie – mechanizm oferowany przez fetcher, pobierający dane z różnych zasobów i zapisujący

je na dysk lub w bazie danych.

2. Indeksowanie – mechanizm budujący indeks na podstawie pobranych dokumentów.

3. Wyszukiwanie – mechanizm wyszukujący odpowiednie dokumenty według zapytania

użytkownika.

Budowa fetchera jest bardzo uzależniona od typu danych, jakie ma pobierać. Inaczej wygląda

dla stron WWW, inaczej dla grup dyskusyjnych, a jeszcze inaczej dla zasobów intranetowych. W
przypadku stron WWW fetchery buduje się na zasadzie pająków internetowych (ang. web spider lub
pełzaczy – ang. web crawler). Są to programy, które przechodzą od strony do strony, nawigując po
linkach, ściągając przy okazji całą zawartość stron na dysk lub do bazy danych. Proces pobierania
stron internetowych jest bardzo uzależniony od wydajności serwerów, na których znajdują się strony
oraz od przepustowości łącz na świecie. Przejście przez wszystkie strony na świecie jest procesem
pracochłonnym i w zależności od ilości uruchomionych pająków może trwać nawet kilkanaście dni.

Fetchery Usenetu mają ułatwione zadanie. W związku z rozproszeniem serwerów grup

dyskusyjnych po świecie i z faktem, iż każdy serwer posiada swoje archiwum prawie wszystkich grup
wystarczy połączyć się tylko z jednym z nich aby mieć dostęp do potrzebnych dokumentów. Posty
zamieszczane są na serwerach jako czysty tekst

, bez zbędnych dodatków. Dzięki temu operacja ich

pobierania jest bardzo szybka i mało obciążeniowa dla systemu. W ciągu kilku sekund klient Usenetu
jest w stanie pobrać kilka tysięcy postów.

Indekser jest to najbardziej obciążeniowa część wyszukiwarki. Jego zadaniem jest zbudowanie

struktury indeksu na podstawie pobranych wcześniej przez fetcher dokumentów, w formie surowej.
Operacja  ta  nie  bardzo  jest   skomplikowana  algorytmicznie,  jednak  w związku z ogromną  ilością
danych do przetworzenia może być bardzo pracochłonna i długotrwała. Na ogół indekser pobiera
wcześniej   zapisany,   surowy   dokument,  parsuje  go   a   następnie   przechodzi   przez   niego   słowo   po
słowie.  Parsowanie  polega   na   wyodrębnieniu   z   dokumentu   tekstu,   z   pominięciem   wszystkich
zbędnych  metainformacji, np.: formatowanie czcionki, tagi  HTML-owe, itp. Przechodząc po treści
indekser analizuje każde słowo. Nowe słowa, wcześniej niezindeksowane, zapisywane są w bazie. Dla

Problemem mogą być jedynie grupy binarne, na których użytkownicy zamieszczają duże pliki graficzne,

wideo i audio. W postach binarnych bardzo rzadko spotyka się jakikolwiek tekst, więc z punktu
widzenie wyszukiwarki pełnotekstowej można je całkowicie pominąć, co też czynimy w naszej pracy.

słów już istniejących w strukturze tworzona jest tylko relacja z aktualnie przetwarzanym
dokumentem.

Przy okazji indeksowania zapisywane są wstępne informacje na temat ważności wystąpienia

danego słowa w tekście. Analizując dokument w formacie HTML można stwierdzić, czy dane słowo
występuje w tytule, nagłówku lub w treści. W zależności od położenia słowa w dokumencie oraz od
czcionki, jaką został napisany, można pokusić się o nadanie mu wagi. Im większą czcionka słowa –
tym większa waga wyniku. Największą ocenę otrzymują słowa zawarte w tytule strony. Taka wstępna
analiza artykułów ułatwia pracę kolejnemu mechanizmowi, czyli wyszukiwarce.

Wyszukiwanie jest to jedyny element całego mechanizmu dostępny dla użytkownika.

Najczęściej wyszukiwarki dostępne są jako aplikacje WWW. Jednak mogą to być równie dobrze
wszelkiego rodzaju aplikacje lub nawet dodatki do aplikacji lub systemów.

Proces wyszukiwania polega na odczytaniu indeksu słów i pobraniu odpowiedniego zbioru

dokumentów. Następnie zbiór ten jest sortowany według kryterium trafności każdego dokumentu.
Pobierając każdy dokument do wyników zapytania wyliczana jest jego waga w stosunku do podanego
zapytania. W prostszych rozwiązaniach jest to suma wag szukanych słów z danego dokumentu.
Szukając kilku słów, najwyżej w rezultatach pojawią się te dokumenty, w których słowa te występują
w tytule lub nagłówku, a najniżej te, w których szukane słowa pojawiają się w dalszej części treści.

2.3.

Nasze rozwiązanie

Prezentowane przez nas rozwiązanie, zgodnie z powszechnie przyjętą konstrukcją budowy

wyszukiwarek składa  się z trzech  głównych części: fetchera,  indeksera  i właściwej  wyszukiwarki
informacji.   Tym   co   wyróżnia   je   spośród   innych   tego   typu   projektów   jest   m.in.   zastosowanie
obiektowego   języka   programowania   z   trwałością   zapewnioną   przez   obiektową   bazę   danych
Objectivity/DB,   a   także   specjalne   podejście   do   indeksowanych   danych,   którymi   są   wiadomości
zamieszczane na polskich grupach dyskusyjnych.
Dzięki   pełnemu   zastosowaniu   obiektowości,   struktura   danych   i   działanie   aplikacji   nie   są
podporządkowane ciągłej potrzebie konwersji obiektów do relacyjnych krotek. Można się więc skupić
jedynie na wymaganej funkcjonalności systemu, co w znaczny sposób ułatwia zarówno modelowanie
jak   i   implementację.   Dzięki   specjalnemu   podejściu   do   grup   dyskusyjnych,   mamy   możliwość
uzyskania   większej   ilości   informacji,   niż   przy   zastosowaniu   uogólnionego   podejścia,   traktując
jednakowo wszystkie elementy indeksowanego tekstu.
Inną ważną cechą naszego pomysłu jest modularyzacja rozwiązania. Każdy z modułów spełnia ściśle
określoną funkcję i przekazuje zdefiniowaną wcześniej informację innym modułom. Taka koncepcja
w tym konkretnym przypadku sprawdza się doskonale, gdyż każdy z elementów naszej aplikacji jest
w  pewien  sposób   niezależny  od   pozostałych.   Wykorzystanie   innego  fetchera   nie   zmieni   sposobu
działania   indeksera   i   wyszukiwarki.   Zmiana   koncepcji   indeksowania   nie   powinna   wpłynąć   na
działanie analizy fleksyjnej czy mechanizmu wyszukiwania. Narzędzie do cache'owania wyników nie
polega w żaden sposób na mechanizmie indeksowania, etc.

Omówimy teraz pokrótce najważniejsze moduły naszej aplikacji. Bardziej szczegółowe

informacje, dotyczące poszczególnych rozwiązań znaleźć można w rozdziałach czwartym i piątym,
opisujących zarówno koncepcję rozwiązania jak i samą implementację. Tutaj skupimy się zatem
jedynie na przedstawieniu najważniejszych funkcji poszczególnych modułów.

Zadaniem naszego fetchera jest połączenie się z (lokalnym) serwerem grup dyskusyjnych i

pobranie wszystkich aktualnych postów z wybranych grup. Każdy post zapisywany jest następnie w
systemie baz danych Objectivity/DB, w bazie

NntpPostDB, jako obiekt klasy

pl.edu.pjwstk.NewsSearch.NntpArticle. Każda grupa zapisywana jest w oddzielnym
kontenerze (nazwą kontenera jest nazwa grupy).

3. Opis narzędzi zastosowanych w pracy

Proponowane przez nas rozwiązanie opiera się na obiektowej bazie danych Objectivity/DB oraz

obiektowym języku programowania Java. W części indeksującej wykorzystany został produkt firmy
Neurosoft – Gram:  oprogramowanie służące do analizy językowej tekstu. Indekser komunikuję się z
Gramem   poprzez   protokół   zdefiniowany   przez   CORBA.   Przy   okazji   tworzenia   wyszukiwarki
powstało kilka niezbędnych dodatków, takich jak: oprogramowanie służące do archiwizacji zasobów
grup dyskusyjnych ściągające wszystkie posty z serwera i umieszczające je w relacyjnej bazie danych
PostgreSQL   oraz   mała   biblioteka   stworzona   w   Javie   realizująca   komunikację   z   serwerem   grup
dyskusyjnych poprzez protokół NNTP zgodnie z RFC 977 (Network News Transfer Protocol) z 1986
roku..

3.1.

Obiektowa baza danych Objectivity/DB

Obiektowa baza danych Objectivity/DB zapewnia mechanizmy do trwałego przechowywania

oraz wyszukiwania obiektów stworzonych w trzech językach programowania: C++, Java, Smalltalk.
System zarządzania bazą danych ukrywa przed użytkownikiem wszystkie operacje niskopoziomowe
związane z trwałością danych.

Architektura

Wszystkie operacje bazodanowe odbywają się w tym samym procesie, w którym działa

aplikacja. Dzieję się tak dzięki dynamicznemu doładowywaniu potrzebnych bibliotek.

Objectivity/DB definiuje cztery rodzaje obiektów w bazie danych. Są to:

•

trwały obiekt

•

kontener

•

baza danych

•

federacja

Obiekt
Trwały obiekt, będący wystąpieniem „klasy zdolnej do trwałości” (ang. „persistence capable

class”) jest to najmniejszy byt programistyczny, który podlega zapisaniu lub odczytaniu z bazy. Jest to
typowy, zwyczajny obiekt z języków programowania, który dziedziczy z klasy dostarczanej przez
producenta bazy lub implementuje specjalny interfejs. Jedyną różnicą między obiektami trwałymi a
nietrwałymi jest to, że obiekty nietrwałe znikają wraz z zakończeniem działania aplikacji. Obiekty
trwałe potrafią przetrwać zamknięcie aplikacji i zostać przywrócone podczas kolejnego uruchomienia
tak jakby w ogóle nie zostały zniszczone. Baza Objectivity/DB przechowuje cały stan obiektu (za
wyjątkiem atrybutów zadeklarowanych jako ulotne („transient”)). Oznacza to, że dane z wszystkich
pól zostaną zachowane. Nie ważne czy są to pola prywatne, publiczne czy chronione. Wszystkie pola
nie będące wystąpieniami typów prostych powinny być także opisane klasami zdolnymi do trwałości.

System zarządzania bazą danych przechowuje także informacje o obiektach powiązanych

niezależnie czy jest to relacja jeden-do-jeden lub agregacja.

Dostęp do kontenerów odbywa się poprzez obiekt bazy danych. Metoda lookupContainer()
obiektu ooDBObj zwraca kontener o podanej nazwie lub null jeżeli taki nie istnieje. Istnieje też
możliwość przejścia iteratorem po wszystkich kontenerach bazy wywołując metodę contains().

Baza Danych  jest to obiekt przechowujący kontenery. Każda baza danych posiada swój domyślny
kontener (ang.  default  container) oraz kontener nazwanych korzeni (ang.  named  roots). Dodatkowo
może posiadać kontenery utworzone przez aplikację.
Baza danych może być utworzona przez administratora poprzez odpowiednie narzędzia lub z poziomu
aplikacji. Każda baza danych należy tylko do jednej federacji i posiada unikalną nazwę w jej obrębie.
Fizycznie   baza   danych   stanowi   plik   na   dysku.   Istnieje   możliwość   przenoszenia   baz   pomiędzy
federacjami za pomocą narzędzia ooattachdb. Taka operacja może powodować spore komplikacje
jeżeli okaże się, iż obiekty z pozoru tej samej klasy nagle okażą się niekompatybilne (błędy związane
z zarządzaniem schematem).

Federacja
Potocznie   zwana   „baza   danych”   w   przypadku   Objectivity/DB   oznacza   federację   baz   danych
(mogących   znajdować   się   na   różnych   maszynach).   Federacja   jest   to   byt   tworzony   przez
administratora.   Grupuje   ona   w   sobie   bazy   danych   korzystające   ze   wspólnego   modelu   obiektów
(schematu). Federacja może być stworzona tylko z poziomu narzędzi administratorskich.
Aplikacja łączy się z federacją baz danych poprzez BootFile, plik opisujący położenie pliku federacji.
Aplikacja może korzystać tylko z jednej federacji podczas swojego działania.

Wielowątkowość
Objectivity/DBDB zapewnia możliwość dostępu do bazy danych dla wielu klientów jednocześnie.
Obsługą wielowątkowości zajmuje się serwer zamków (ang. lock server) – oolockserver. Dba on
o zapewnienie zasad ACID w stosunku do transakcji operujących na bazie. Jest to mały proces, który
może być uruchomiony na dowolnej maszynie. W pliku bootFile każdej federacji zapisany jest adres
hosta, na którym uruchomiony jest serwer zamków. Aplikacja nie łączy się explicite z lock serverem.
Dzieje się to głębiej w bibliotekach obsługujących dostęp do bazy.

Aplikacja   dokonuje   wszystkich   operacji   bazodanowych   w   ramach   sesji,   która   działa   w   ramach
konkretnego połączenia. Sesja jest instancją klasy  Session  dostarczanej przez producenta. Służy
ona   do   interakcji   aplikacji   z   bazą   danych   oraz   udostępnia   dane   i   zasoby.   Wszystkie   transakcje
odbywają  się  w ramach   sesji.  Transakcja  rozpoczyna się  metodą  begin()  obiektu  Session  a
kończy  commit().   Istnieje   też   możliwość   zerwania   transakcji   –   metoda  abort().   Podczas
transakcji   aplikacja   zakłada   dwa   rodzaje   zamków:   do   czytania   (read   lock)   lub   do   modyfikacji
obiektów (write lock). W momencie, kiedy aplikacja pobiera obiekt do czytania baza danych, zakłada
na   nim   zamek   „do   czytania”.   Jeżeli   aplikacja   będzie   próbowała   zapisać   pobrany   obiekt   (np.   po
zmianie zawartych w nim danych) zamek zostanie zaktualizowany do „do pisania” (write lock).

Baza Objectivity/DB zapewnia dwa rodzaje dostępu wielowątkowego:

•

Standardowa wielowątkowość

•

Tryb “Multiple Readers, One Writer (MROW)”

•

Nazwa pola relacji w danej klasie

•

Pełna nazwa klasy na drugim końcu relacji (wraz z nazwą pakietu)

•

Nazwa pola relacji odwrotnej

•

Zachowanie podczas kopiowania obiektu. Może być jedno z:

➢

COPY_DELETE – po operacji skopiowania obiektu źródłowego, obiekt kopia nie będzie
posiadał relacji do obiektu docelowego

➢

COPY_MOVE – po operacji skopiowania obiektu źródłowego, relacja zostanie przeniesiona z
obiektu źródłowego do kopii. Po operacji obiekt źródło nie będzie posiadał relacji do obiektu
docelowego.

➢

COPY_COPY – wraz ze skopiowaniem obiektu źródłowego zostanie także skopiowana relacja.
Po operacji istnieć będą dwa obiekty z dwoma relacjami do tego samego obiektu docelowego.

•

Zachowanie podczas wersjonowania. Objectivity/DB w wersji dla języka Java nie obsługuje
wersjonowania. Mimo to należy zdefiniować sposób zachowania się relacji podczas
wersjonowania, aby można było korzystać z tej klasy łącząc się z bazą za pomocą innych
języków programowania.

•

Flaga (true/false) określająca, czy propagowane będzie usunięcie obiektu. Inaczej mówiąc, czy
jeżeli obiekt zostanie usunięty należy usunąć także obiekty z nim powiązane.

•

Flaga (true/false) określająca, czy propagować zamki na obiekty powiązane. Flaga ta ma
znaczenie tylko jeżeli zdecydujemy się wiązać relacjami obiekty ponad kontenerami. Jeżeli
wszystkie obiekty powiązane znajdują się w tym samym kontenerze to nie zauważymy różnicy
gdyż baza danych blokuje cały kontener a nie pojedyncze obiekty.

•

Tryb przechowywania relacji.

public

class

Article

extends

ooObj {

...

private

ToManyRelationship stats;

public

static

OneToMany stats_Relationship() {

return

new

OneToMany(

"stats"

// This relationship

"pl.edu.pjwstk.NewsSearch.WordStats"

// Destination class

"article"

// Inverse relationship

Relationship.COPY_MOVE,

// Move links to copy of object

Relationship.VERSION_MOVE,

// Move links to new version

false

// Don't propagate delete

false

// Don't propagate locks

Relationship.INLINE_NONE);

// Non-inline storage mode

}

// End stats_Relationship static method

...

}
Kod 2. Przykład definiowania relacji. Obiekt Article relacje „stats” do obiektów klasy
WordStats. Jest to relacje typu jeden-do-wielu.

Dodatki

Wraz z klasami niezbędnymi do budowania aplikacji opartych na bazie Objectivity/DB

producent   rozpowszechnia   zestaw   dodatków.   Chodzi   tutaj   głównie   o   trwałe   kolekcje,   które
przygotowane są do przechowywania w bazie. Spowodowane  jest  to główne tym, iż standardowe
kolekcje języka Java (listy, mapy i inne z pakietu  java.util.*) nie są obiektami trwałymi i w
związku z tym nie mogą być przechowywane przez Objectivity/DB. W naszej pracy stosowaliśmy
ooTreeList i ooTreeMap. Obie te klasy dziedziczą z ooBTree, która zajmuje się zarządzaniem
kolekcją   w   środowisku   Objectivity/DB.   Struktura   tej   kolekcji   oparta   jest   na   zasadzie   b-drzewa.
Przechowuje ona węzły i liście. Klasa ooBTree zajmuje się rozrzucaniem obiektów na węzły i liście.
Przy okazji sama tworzy strukturę kontenerów wiążąc je ze sobą.

Tworząc kolekcję użytkownik ma możliwość zdefiniowania maksymalnej liczby obiektów

przechowywanej w węźle b-drzewa. Przy małej liczbie spada liczba konfliktów przy zakładaniu
zamków w przypadku kiedy wiele aplikacji klienckich korzysta jednocześnie z tej samej kolekcji.
Podając dużą maksymalną liczbę obiektów minimalizujemy liczbę kontenerów obsługujących
kolekcję.

3.2.

Java

Obiektowy język programowanie stworzony przez firmę SUN (

http://

java.sun.com

). Główną

jego zaletą jest pełna obiektowość bez możliwości obejścia jej sztuczkami programistycznymi.
Dużym udogodnieniem Javy jest pełny zestaw kolekcji oraz gotowych klas pomocniczych, dzięki
którym tworząc aplikacje programuje się w zasadzie tylko jej logikę. Nie trzeba natomiast tworzyć od
zera swoich klas pomocniczych implementujących rożnego rodzaju struktury danych.

Wszystkie programy Javy uruchamiane są w maszynie wirtualnej (ang. Java Virtual Machine –

JVM). Kod źródłowy programu kompilowany jest do postaci bajtkodu (ang. byte code). Dzięki takiej
architekturze dowolna aplikacja stworzona przy pomocy standardowych klas Javy jest w pełni
przenośna pomiędzy dowolnymi systemami operacyjnymi, które posiadają implementacje maszyny
wirtualnej. Wszystkie operacje dostępu do zasobów (pliki, pamięć, zasoby sieciowe) odbywają się
poprzez JVM. Do zadań maszyny wirtualnej należy sprawne zarządzanie pamięcią aplikacji Javy oraz
umożliwianie dostępu do zasobów w danym systemie operacyjnym.

Java oferuje tzw. odśmiecacz (ang. Garbage Collector w skrócie GC). Jest to mechanizm

wbudowany   w   maszynę   wirtualną   Javy   służący   do   usuwania   z  pamięci   nieużywanych   obiektów.
Programując w tym języku twórca aplikacji nie zajmuję się w ogóle kwestiami zarządzania pamięcią.
Obiekty   są   powoływane   a   ich   niszczeniem   zajmuje   się   GC..   W   maszynie   wirtualnej  SUNa
znajdywanie   kandydatów   do   usunięcia   odbywa   się   wykorzystując   algorytm   „Mark  and  Sweep”.
Polega on na przejściu przez wszystkie obiekty zaczynając od najniższego na stosie. Przechodząc
przez każdy z nich odznaczana jest flaga „marked”. Po zakończeniu procesu wszystkie obiekty, które
nie mają ustawionej tej flagi zostają usunięte. Specyfikacja maszyny wirtualnej nie definiuje sposobu
znajdowania   martwych   obiektów.   Kwestia   ta   pozostawiona   jest   do   decyzji   producenta   danej
wirtualnej maszyny.

Obiekt jest aktywny jeśli istnieje jakaś ścieżka z aktualnie wykonywanego programu poprzez

obiekty powiązane, kolekcje itp. do danego obiektu. Jeżeli taka ścieżka nie istnieje, obiekt jest
kandydatem do skasowania. Usuwanie nieużywanych obiektów nie odbywa się natychmiastowo po
utracie dostępu do obiektu. Obiekty-śmieci istnieją przez jakiś czas w pamięci a proces odśmiecania
odbywa się raz na jakiś czas lub w razie konieczności uwolnienia pamięci (np. kończy się pamięć
programu a aplikacja próbuje powołać nowe obiekty).

3.3.

Gram

Dużym zagadnieniem w wyszukiwaniu pełnotekstowym jest analiza i przekształcanie tekstu. W

naszej pracy skupiliśmy się głównie na stworzeniu mechanizmu indeksującego i wyszukującego.
Analiza tekstu w języku polskim to temat na odrębną prace magisterską, dlatego też wykorzystaliśmy
gotowe oprogramowanie. Firma Neurosoft udostępniła nam swój główny produkt – GRAM
(

http://

gram.neurosoft.pl

). Jest to oprogramowanie służące do zaawansowanej analizy i

przekształcania   tekstów   w   języku   polskim.   Jest   ono   wykorzystywane   w   profesjonalnych
zastosowaniach.   Zostało   wbudowane   w   mechanizm   wyszukiwarki  NetSprint.pl,   który   jest
wykorzystywany  przez Wirtualną  Polską oraz  wiele  innych  wyszukiwarek  dostępnych   w  polskim
Internecie.

Funkcjonalność oprogramowania Gram udostępniana jest poprzez interfejsy CORBA. Dzięki

temu analizy językowe stają się dostępne dla każdego języka programowania z obsługą standardu
CORBA.

Z oprogramowania GRAM korzystamy głównie w celu normalizacji tekstów. Normalizacja

polega na zamianie wszystkich słów na ich formy podstawowe. Dzięki temu wyszukiwanie informacji
staje się łatwiejsze i celniejsze. Wpisując tekst do znalezienia użytkownik nie musi się martwić czy
podał go w odpowiedniej formie. Mechanizm szukające odnajdzie wszystkie teksty, w których
występują dane słowa bez względu na to, w jakiej formie zostały użyte.

3.4.

Python

Język skryptowy, który aspiruje do miana „obiektowego”. Niestety po pierwszym momencie

fascynacji   podsyconej   dużym  szumem  w   kręgach   programistycznych   wychwalającym   ten   język,
szybko doszliśmy do rozczarowania. Główną wadą tego języka jest to, że nie jest w stu procentach
obiektowy. Niestety, mimo dużych starań twórców przemknęły się do niego konstrukcje rodem z PHP
lub   C.  Najlepszym   tego   przykładem  jest   sposób   pobierania   długości   listy.   Mając   obiekt   lista,  w
którym przechowujemy elementy naturalnym sposobem, z punktu widzenia obiektowości, wydaje się
wywołanie   metody  length()  lub  size()  (lub podobnej)  na naszym obiekcie. W  Pythonie, z
niezrozumiałych   względów,   przyjęto   rozwiązanie,   w   którym  chcąc   otrzymać  rozmiar   listy  należy
wywołać funkcję globalną len(list) przekazując jako parametr referencję do obiektu lista.

Oczywiście, fakt iż jest to technologia skryptowa niesie ze sobą wszystkie wady (liczne) i

zalety (stosunkowo nieliczne) języków skryptowych. Są to:

•

Brak kompilacji: 90% błędów programisty jest do wychwycenia w procesie kompilacji. Błędy
popełnione w programie skryptowym ujawnią się dopiero w momencie wykonania wadliwego
kodu. W modułach bardzo rzadko uruchamianych taki błąd może ujawnić się bardzo późno
(nawet po miesiącach).

•

Brak mocnego typowania. Nie jest to cecha przywiązana do języków skryptowych, jednak
większość spotykanych języków skryptowych uznaje co najwyżej dwa typy: liczbowy i
tekstowy. Python nie odbiega od tego schematu

•

Brak deklaracji zmiennych. Zmienne powoływane są w momencie ich pierwszego użycia. Nie
jest to wielka wada, ale w dużych aplikacjach przy niskiej „higienie” kodu może wprowadzać
dodatkowe zamieszanie do i tak skomplikowanego kodu.

•

Metody i zmienne prywatne (zob. sekcja 9.6

dokumentacji

Pythona). Python nie oferuje

możliwości definiowania zmiennych i metod prywatnych. Pseudo-prywatność zmiennych i
metod można osiągnąć poprzez specjalne nazewnictwo: __metodaA(). Nazwy takie zamieniane
są podczas wykonania na [nazwaklasy]__metodaA(), co powoduje ukrycie takich pól przed

dostępem z zewnątrz. Mimo takich zabiegów istnieją sposoby obejścia zakresu widoczności
zmiennych tak, że pola i metody prywatne stają się dostępne z zewnątrz.

•

Bloki programu. Do definicji bloków programu nie stosuje się klamr (np. „{” i „}”). Zamiast
tego kod jest formatowany odpowiednio wcięciami. Wcięcie głębsze od aktualnego oznacza
wewnętrzny blok. W momencie przenoszenia plików na inne systemu operacyjne obsługujące
inne kodowania mogą powstawać błędy spowodowane przesunięciem się niektórych wcięć.

Oczywiście Python posiada również zalety:

•

Olbrzymi zasób bibliotek implementujących prawie wszystkie spotykane w Internecie
technologie (nntp, imap, pop3, http, ftp, wyrażenia regularne, kolekcje, CORBA, i inne).

•

Wyjątki. Podobnie do Javy wbudowany został mechanizm obsługi wyjątków. Wszelkie
nietypowe zachowanie sygnalizowane jest odpowiednimi wyjątkami zamiast zwracania kodów
błędów przez funkcje.

•

Szybkie tworzenie małych programów. Dzięki rozbudowanym zasobom biblioteki i możliwości
ściągnięcia dodatków z Internetu programowanie niewielkich aplikacji może okazać się bardzo
szybkie.

Ogólnie Python jest krokiem w dobrym kierunku jeżeli chodzi o języki skryptowe. Na pewno

jest on przyjemniejszy w programowaniu niż PHP. Jednak dla programisty Javy przejście na Pythona
może być źródłem sporej frustracji.

3.5.

PostgreSQL

Relacyjna baza danych rozpowszechniana na zasadzie Open Source. Zapewnia ona pełny

zestaw operacji bazodanowych – SQL, transakcje (pełna zgodność z ACID), procedury składowane
(ang.  stored procedures), wyzwalacze (ang.  triggers), indeksy, prawa dostępu, widoki (ang.  views).
Postgres  pozwala   na   prawie   bezbolesne   przenoszenie   baz   z/na  Oracle,   SQL  Servera  lub   inne
obsługujące  SQLa.  Jest   to   w   pełni   profesjonalny   system   zarządzania   bazą   danych,   który   został
wykorzystany w wielu projektach komercyjnych.

Jedną z ciekawszych zalet tego SZBD stanowi konstrukcja „SELECT pole1, pole2

FROM tabela LIMIT x OFFSET y” ograniczająca zwracane rekordy tylko do określonego
wycinka. Jest to szczególnie istotne w aplikacjach internetowych gdzie zachodzi potrzeba
stronicowania danych, np. pokazywanie po 20 wątków na stronie. W innych SZBB (np. SQL Server)

„

początek petli

”

for

range(1,2):

" + str(i)

„

kolejny krok pętli

”

„

koniec petli

”

Kod 3. Przykład deklaracji pętli w języku Python

trzeba niestety stosować obejścia poprzez implementowanie odpowiednich procedur składowanych
dla osiągnięcia podobnego efektu.

Niestety Postgres mimo swojego profesjonalnego podejścia i obsługi standardów SQL92 i

SQL99

(jak

chwalą

się

jego

twórcy

Internecie:

http://

www.postgresql.org

/ docs

/7.4/

interactive

/ preface.html

#INTRO-WHATIS

) nie oferuje żadnych

dodatkowych udogodnień:

•

Brak jest możliwości zaawansowanego tuningu bazy pod względem wydajności.

•

Brak zapamiętywania często wykonywanych niezmiennych zapytań.

Główną zaletą Postgresa jest fakt, iż jest dostępny za darmo i jednocześnie jest prawie w pełni

kompatybilny z SQL. W porównaniu z MySQL-em – innym darmowym system zarządzania bazą
danych Postgres wypada bardzo dobrze.

3.6.

Leafnode

Głównym i jedynym źródłem danych dla naszego mechanizmu wyszukiwarki jest domowy

serwer   grup   dyskusyjnych  LeafNode  (wersja  leafnode-1.9.42.rel).   Jest   to   proste
oprogramowanie   obsługujące   protokół   NNTP,   ściągające   artykuły   i   grupy   dyskusyjne   z   serwera
głównego   (ang.  feed).   W   naszym   przypadku   skorzystaliśmy   z   publicznego   serwera
news://news.task.gda.pl oferującego większość grup światowych i prawie wszystkie grupy
polskie.   Początkowo   próbowaliśmy   korzystać   z   serwera  news://news.tpi.pl  lecz   jego
wydajność   pozostawia   sporo   do   życzenia.   Server   Leafnode   udostępnia   ściągnięte   posty   dalej
użytkownikom   poprzez   protokół   NNTP.   Można   łączyć   się   z   nim   za   pomocą   każdego   programu
czytnika grup dyskusyjnych.

Leafnode przechowuje ściągnięte artykuły na dysku jako pliki. Każdy artykuł to oddzielny plik,

a każda grupa to oddzielny katalog. Stwarza to pewne problemy gdyż tylko nieliczne systemy plików
potrafią  sobie   poradzić   z ogromną   ilością   małych   plików   przechowywanych  w  jednym  katalogu.
Początkowo   dane   zapisywane   były   w   systemie   Ext3   jednak   szybko   doszliśmy   do   fizycznego
ograniczenia liczby plików. Obecnie system działa na systemie plików  ReiserFS, który nie posiada
limitu liczby plików.

Serwer LeafNode skonfigurowany jest tak, że nie kasuje starych postów. Dzięki temu jesteśmy

w posiadaniu pełnej historii polskich grup dyskusyjnych od połowy sierpnia roku 2003.

Co noc uruchamiany jest proces ściągania nowych artykułów z polskich grup dyskusyjnych

(pl.*,  alt.pl.*,  free.pl.*,  ms-news.pl.*).   Niestety,   oprogramowanie   to   jest   mało   wydajne.   Proces
ściągania przy rozmiarze archiwum ok. 10gb trwa ok. 22 godziny. Możliwe że jest to spowodowane
słabą wydajnością maszyny, na której działa (procesor 333MHz, 64mb RAMu). Przy przekroczeniu
24   godzin  może   dojść   do   dodatkowych   komplikacji.  Jeżeli  zaś   proces   ściągania  nowych   postów
będzie   uruchamiany  co   dwa  dni  może to  doprowadzić   do  efektu   „kuli   śniegowej”   – im rzadziej
ściągane posty tym ich więcej, więc dłużej to trwa itd.

3.7.

Biblioteki

Biblioteka NNTP

Implementacja fetchera (roz 5.2) korzysta z biblioteki, łączącej się z serwerem poprzez

protokół NNTP. Początkowo wykorzystywaliśmy bibliotekę gnu.inet.nntp projektu Savannah
(

http://

savannah.nongnu.org

/ projects

/nntp-

java

). Jest to rozbudowana biblioteka implementująca

większość komend protokołu NNTP. W czasie prac okazało się, że potrafi zawiesić się bez podania

4. Obiektowość a wyszukiwanie pełnotekstowe

Rozdział czwarty pracy składa się głównie z dokładnego omówienia i uzasadnienie rozwiązania

zastosowanego w ramach pracy. Szczególny nacisk został położony na algorytmy stanowiące
zasadniczy rezultat pracy, czyli algorytm indeksowania i wyszukiwania informacji.

4.1.

Obiektowość a wyszukiwanie informacji

Od kilku dobrych dekad (to informatyczny odpowiednik tradycyjnego „od wieków”) trwa

nieustanna walka (niestety nie zawsze na rzeczowe argumenty) pomiędzy zwolennikami relacyjnych
(RDBMS)   i obiektowych   (ODBMS)   systemów  baz danych.  Orędownicy  obu  koncepcji   często  nie
stronią   od   kategorycznych   opinii   na   temat   opiewanej   przez   siebie   technologii,   dyskwalifikując
jednocześnie   wszystkie   konkurencyjne   rozwiązania   („każde   zadanie   da   się   wykonać   szybciej   i
efektywniej   stosując   bazę   relacyjną/obiektową”,   „obiektowe/relacyjne   bazy   danych   to   relikt
przeszłości”, etc). Oczywiście, jak zwykle w takich przypadkach bywa, prawda leży pośrodku. Obie
koncepcje   mają   swoje   dobre   i   słabe   punkty,   nie   ma  uniwersalnego   rozwiązania,   a   zastosowanie
konkretnej technologii zależy przede wszystkim od specyfiki projektu. W tym miejscu należałoby
przybliżyć  nieco  konkretne   „za   i   przeciw”   obu  rozwiązań,   aby   wyjaśnić   powody,  dla   których   w
omawianej aplikacji wybrane zostało konkretne rozwiązania, oparte o system obiektowy.

Ogromną zaletą baz relacyjnych jest powszechne użycie deklaratywnego języka zapytań SQL,

który mimo licznych wad i błędów koncepcyjnych, przyjął się i jest obecnie uznawany za standard.
Stosowanie  SQL  uwalnia   programistę   od   ciągłego   myślenia   o   niskopoziomowych   szczegółach
implementacyjnych  i pozwala spojrzeć na aplikację  z wyższego poziomu abstrakcji, jedynie przez
pryzmat   formalnych   powiązań   między   danymi.   Zaletą   systemów   relacyjnych   jest   więc   przede
wszystkim znana i popularna  technologia,  a co za tym idzie, również bardzo dobre wsparcie dla
narzędzi wspomagających rozwijanie aplikacji opartych na relacyjnym silniku. Istotnym plusem jest
także   istnienie   standardów,   takich   jak  ODBC  i  JDBC,   dzięki   którym,  przynajmniej   teoretycznie,
przejście do nowej wersji, czy zmiana stosowanego systemu baz danych nie powinna nieść za sobą
kłopotliwych zmian  w kodzie  aplikacji.  Jednak  trzeba  tu poczynić pewne  założenia.  Po pierwsze
takie, że kod rozwijanej  aplikacji  zawiera jedynie standardowe komendy  SQL  i nie stosowane są
jakiekolwiek   rozszerzenia   standardu   oferowane   przez   system.   Po   drugie,   musimy   przyjąć,   że
stosowany system zarządzania bazą danych zapewnia całkowite wsparcie dla tego standardu. Niestety,
pierwsze założenie w znaczny sposób uszczupla możliwości programisty, szczególnie gdy powiązania
między   danymi   są   skomplikowane   i   trudno   je  zamodelować  jedynie   przy   użyciu   standardowych
dostępnych  w  RDBMS  metod. Wybiera  się więc najczęściej  rozwiązanie  połowiczne – częściowe
odejście   od   standardu,   wiążące   się   z   utratą   całkowitej  przenaszalności  kodu,   na   rzecz   ułatwień
programistycznych i lepszej wydajności pracy. Wielu ważnych dostawców baz danych (w tym firma
Oracle) oferuje od pewnego czasu rozwiązania hybrydowe. Są to bazy oparte na filozofii relacyjnej,
jednak oferujące pewne elementy obiektowości, jak np. referencje między krotkami, dziedziczenie
encji, wołanie metod, itp. Rozwiązania te charakteryzują się całkowitą nieprzenaszalnością (brak jest
jakiegokolwiek   standardu   odnoszącego   się   do   tego   typu   systemów),   mogą   być   jednak   dobrym
rozwiązaniem w przypadku gdy posiadamy już aplikację bazującą na systemie relacyjnym i występuje
potrzeba jej optymalizacji, czy reorganizacji struktury danych.
Rozwiązania  hybrydowe  nie   eliminują   jednak   największej   niedogodności,  jaką   stwarzają   systemy
oparte na filozofii relacyjnej. Jak zauważa  Steve  McClure

z International Data Corporation, 25%

czasu jaki spędza programista przy tworzeniu aplikacji poświęcane jest na mapowanie struktury
danych w bazie na strukturę obiektową używaną w kodzie programu. Mapowanie takie może mieć
sens, jeśli ważnym wymaganiem aplikacji ma być jej przenaszalność na inne systemy baz danych. W

S.McClure, Object Database vs. Object-Relational Databases. IDC Bulletin #14821E - August 1997.
(

http://www.ca.com/products/jasmine/analyst/idc/14821E.htm#BKMTOC2

)

przypadku   przywiązania   firmy   do   konkretnego   narzędzia   bazodanowego   jest   to   jednak   zupełnie
niepotrzebny   narzut,   którego   niestety   nie   sposób   zniwelować,   przy   zastosowaniu   standardowego
systemu  RDBMS.   Jedyną   godną   uwagi   próbę   pójścia   w   kierunku   większej   integracji   języka
programowania z systemem RDBMS podjął Oracle, ze swoim PL/SQL. Język ten sprawdza się przy
systemach typowo bazodanowych, np. opartych na  Oracle  Forms, gdzie oprogramowanie aplikacji
sprowadza   się   do   utworzenia   pewnej   ilości   procedur   i   bloków   programistycznych   w  PL/SQL,
zintegrowanych w sterowane  zdarzeniowo  środowisko formularzy. Rozwiązanie  to nie  ma jednak
zastosowania w bardziej  zaawansowanych projektach,  opartych na strukturze  MVC  (Model-View-
Controller), wymagających wielu aplikacji klienckich, pracujących na różnych platformach, a także
dostęp do danych przez aplikację internetową, czy Web Services.
Mimo wielu problemów, jakie narzuca sztywny model danych stosowany w  RDBMS, rozwiązania
relacyjne   (i   obiektowo-relacyjne)   nieustannie   przewodzą  na   światowym rynku  bazodanowym.  Na
sukces  RDBMS  oraz  SQL  pracuje   wszakże   ogromne   lobby   producentów,   przez   co   wiele   osób
niesłusznie może odnieść wrażenie, że model relacyjny jest jedynym możliwym podejściem do  baz
danych i nie istnieją żadne sensowne, alternatywne rozwiązania.
A rozwiązania takie istnieją.  Wprawdzie lansowany przez grupę  ODMG  obiektowy język zapytań
OQL,  ze   względu   na   liczne   niejasności   i   pomyłki   koncepcyjne   nie   uzyskał   aprobaty   rynku   i   (z
nielicznymi wyjątkami) nie jest wykorzystywany komercyjnie, to jednak istnieją inne, równie dobre
jak   SQL   sposoby   dostępu   do   danych,   opierające   się   zazwyczaj   na   nieco   innej   koncepcji   niż
deklaratywny język zapytań. Co więcej, w specyficznych przypadkach, sposoby te mogą okazać się o
wiele bardziej skuteczne. Zastosowaniu obiektowego modelu danych, zarówno na poziomie bazy jak i
kodu aplikacji ma wiele zalet. Takie rozwiązanie, już na starcie eliminuje wspomniane wyżej 25%
pracy programistycznej, polegającej na mapowaniu obiektów języka programowania na krotki w bazie
danych. Poza tym zyskujemy bardziej  naturalną,  intuicyjną strukturę  danych opartą  na obiektach.
Język SQL, wprawdzie wspierany przez niektórych dostawców ODBMS, nie jest najlepszą metodą
uzyskiwania   dostępu   do   danych   w   systemach   obiektowych.   Obiektowe   systemy   baz   danych
zapewniają   bowiem   wiele   alternatywnych,   najczęściej   dużo   bardziej   wydajnych   sposobów   na
wykonanie identycznych czynności. Mogą to być na przykład:

●

dostęp do obiektów poprzez referencje i struktury (tablice, listy, drzewa) referencji

●

skanowanie obiektów w bazie danych (proste wyszukiwanie ze względu na jedno lub kilka
kryteriów)

●

bezpośrednie pobranie obiektu poprzez użycie struktury obiektów-korzeni

Pierwszym omawianym sposobem jest wykorzystanie w systemach obiektowych referencji i

kolekcji referencji jako naturalne zastąpienie relacji. Przy takim podejściu, aby uzyskać interesujące
nas dane, nie musimy zazwyczaj przeszukiwać całej bazy, zadając odpowiednie kryteria. Wystarczy
przeszukać   dane   bezpośrednio   związane  z aktualnie   używanym obiektem,  czyli   przejść   poprzez
referencję do powiązanego obiektu i wywołać odpowiednią metodę. Taka nawigacja po referencjach
między obiektami może w wielu sytuacjach zastąpić nam zupełnie operację przeszukiwania bazy.
Większość systemów opiera się bowiem na bardzo powiązanych ze sobą strukturach danych, więc
operując na konkretnym obiekcie prawdopodobne jest, że operacje jakie będziemy chcieli wykonać
dotyczą bezpośrednio tego właśnie obiektu, bądź obiektów z nim powiązanych.
Większość obiektowych systemów baz danych, w tym Objectivity/DB, oferuje również narzędzie do
skanowania  – wyszukiwania obiektów w bazie w oparciu określone kryteria.  Skanowania  takiego
nie możemy równać z zapytaniem, gdyż dotyczy ono zazwyczaj jednej konkretnej klasy obiektów i
wyszukiwanie polega na przeszukaniu wszystkich obiektów w bazie pod kątem zadanego kryterium
Brak tutaj możliwości grupowania obiektów, agregacji w celu generowania raportów, czy zwykłego
złączenia (join) dwóch klas po określonym atrybucie. Skanowanie możemy traktować więc jedynie
jako wstępną segregację obiektów w bazie danych w celu pobrania ich do dalszego przetwarzania.
W specyficznych przypadkach stosowany może być również mechanizm bezpośredniego pobierania
z   bazy   (lookup)   obiektu-korzenia.  Taki   obiekt   oznaczony   jest   unikalnym   w   ramach   bazy

identyfikatorem i może być stosowany jako tzw. korzeń, od którego możemy dalej nawigować
wgłąb bazy. Obiekty-korzenie okazują się być szczególnie przydatne, gdy w bazie istnieje pewien
rodzaj danych, do których odwołania występują bardzo często. Ułatwia to i w znacznym stopniu
przyspiesza dostęp tych danych, jak również do obiektów powiązanych z nimi poprzez asocjacje.
Ostatecznie, oba te rozwiązania, czyli skanowanie i bezpośrednie pobieranie obiektu-korzenia mają
za zadanie jedynie znalezienie obiektu lub grupy obiektów, od których możemy dalej nawigować
już z użyciem tradycyjnych metod, w zależności od stosowanego języka programowania.

Kryterium

RDBMS

ODBMS

Możliwe

sposoby

pobierania i modyfikacji
danych

Deklaratywny język

SQL

interfejsy do konkretnych języków
programowania

Bezpośrednie pobranie obiektu
(lookup),

nawigacja

referencjach, skanowanie (scan),
deklaratywne języki zapytań a’la
SQL

Przenaszalność aplikacji

Bardzo wysoka, w przypadku
użycia standardowego SQL

Minimalna (brak standardów)

Wsparcie dla obiektowych
języków programowania

Brak,

bardzo

kosztowne

mapowanie obiektów w aplikacji
na strukturę bazy (ok 25% czasu
spędzanego na kodowaniu)

Bezpośrednie, brak konieczności
mapowania danych

Możliwość automatycznej
optymalizacji

Duża, ze względu na wysoki
poziom abstrakcji języka zapytań
SQL, jak również struktury danych
(trzecia postać normalna)

Znikoma,   przy   obecnym   braku
standardów   dotyczących   dostępu
do   danych   i   ich   abstrakcyjnej
struktury (pewne kroki ku zmianie
tego   stanu  rzeczy  są   czynione
przez   organizacje,   np.   grupę
ODMG)

Wpływ na strukturę
danych

bazie,

rozszerzalność struktury

Niewielki, stosowana jest
tradycyjna struktura encji i
związków,

uniemożliwiająca

bardziej zaawansowane powiązania
między danymi (jak

np.

dziedziczenie)

Bardzo   duży,   zazwyczaj   możliwe
jest   bezpośrednie   przeniesienie
struktury   klas   w   aplikacji   na
strukturę bazy

Integracja   z   istniejącymi
narzędziami,   językami
programowania,
systemami   zarządzania
bazą

Standardy   dostępu   do   bazy   przez
ODBC/JDBC   i   inne,   zazwyczaj
oparte   na   mechanizmie   refleksji
(bardzo   kosztowne),   wiele
uniwersalnych   narzędzi   do
zarządzania bazą

Brak standardowych narzędzi, brak
standardowych   mechanizmów
dostępu   do   danych.   Aplikacje
zazwyczaj   dostarczone   przez
producenta.   Dostęp   do   bazy
bezpośrednio, z poziomu kodu

Tabela 1. Porównanie praktycznych możliwości aktualnych systemów RDBMS i

ODBMS

Trzeba   jednak   pamiętać,   że   wyszukiwanie   informacji   w   dobrze  ustrukturyzowanych  danych   w
Objectivity/DB,   czy  innych   bazach   obiektowych,   nie   wymaga   zazwyczaj   skanowania   obiektów   z
użyciem predykatów (odpowiednik deklaratywnych zapytań z baz relacyjnych). Większość informacji
możemy uzyskać poprzez pobranie odpowiedniego  obiektu-korzenia, a następnie przechodzenie od
niego do kolejnych obiektów, poprzez zdefiniowane struktury: kolekcje i referencje. W ten sposób

eliminowany   jest   ogromny   dodatkowy  narzut,   jaki   wymusza   relacyjne   podejście   do   znajdowania
informacji   –   konieczność   każdorazowego   przeszukiwania   dużych   zbiorów   danych   pod   kątem
podanych   parametrów,   które   zawężają   wyniki.  Oczywiście   istnieją   automatyczne   optymalizatory,
specjalne  techniki indeksowania  i  inne  czynniki zmniejszające  ten  narzut.  Nie  zmienia  to jednak
faktu, że w bazie obiektowej, techniki te nie są, jak w przypadku podejścia relacyjnego, niezbędne.
Dzieje się tak, ponieważ obiekty które potrzebujemy uzyskać, zakładając prawidłowo zdefiniowane
asocjacje między klasami, zawsze powinniśmy mieć łatwo dostępne poprzez referencje. Taki właśnie
model – wiele mocno powiązanych, zależnych od siebie obiektów, po których głównie nawigujemy,
w celu pobrania danych – stosowany jest zazwyczaj przy implementacji wyszukiwania zindeksowanej
informacji   z  dużych  archiwów   danych.  Obiektowa   baza   danych   nadaje  się   więc   do  takiego  celu
idealnie, ze względu na ogromną swobodę w tworzeniu unikalnych struktur danych i optymalizację tej
struktury (często   wiążącą  się  z redundancją  danych) pod kątem wydajności  wyszukiwania  (czasu
odpowiedzi).   Można   powiedzieć   nawet   więcej   –   w   tradycyjnej   bazie   relacyjnej,   nawet   najlepiej
przygotowana struktura danych, w przypadku takiego projektu jak wyszukiwarka zawiedzie – właśnie
z powodu braku  możliwości  dostosowania  struktury danych do potrzeb  aplikacji.  Potwierdziły to
początkowe eksperymenty, zakładające stworzenie relacyjnej kopii struktury danych zastosowanej w
prezentowanej   aplikacji,   w   bazie   PostgreSQL.   Już   po   zindeksowaniu   paru   tysięcy   artykułów,
szybkość wyszukiwania różniła się kilkukrotnie na korzyść Objectivity. Można tylko zgadywać, że po
zastosowaniu bardziej skomplikowanej struktury danych, różnica ta rosłaby jeszcze bardziej

Podsumowując, oba podejścia – obiektowe i relacyjne – posiadają wiele ważnych zalet i tyleż

samo często dyskwalifikujących wad. Skalowalność, rozszerzalność i potężne możliwości
optymalizacji schematu sprawiły, że wybór rozwiązania padł w tym konkretnym przypadku na bazę
Objectivity/DB.

4.2.

Omówienie przyjętego rozwiązania

Rozwiązanie przyjęte w omawianym systemie opiera się przede wszystkim na maksymalnym

skorzystaniu z elastyczności, jaką oferuje obiektowa baza danych, w tym przypadku Objectivity/DB.
Struktura danych, czyli definicje klas i asocjacje pomiędzy klasami, została dobrana w taki sposób,
aby   przede   wszystkim   zoptymalizować   efektywność   operacji   wyszukiwania.   Rozsądna   szybkość
wyszukiwania informacji to zdecydowanie najważniejsze kryterium w ocenie każdej wyszukiwarki
pełnotekstowej.   I   o   ile   kryterium   trafności   wyników   jest,   wydawałoby   się,   równie   istotne,   to   w
praktyce wyszukiwarka znajdująca  nawet najbardziej  adekwatne rezultaty w czasie większym niż,
powiedzmy dziesięć sekund, z góry skazana jest na porażkę. Oczywistym efektem takiego działania,
czyli koncentracji na szybkości już na etapie tworzenia struktury aplikacji, jest znaczne wydłużenie
się czasu potrzebnego na zindeksowanie artykułów (czyli stworzenie struktury danych systemu) oraz
zdecydowane   zwiększenie   fizycznego   rozmiaru   danych   na   dysku.   Szybkość   bowiem   osiągamy
głównie  dzięki świadomej  redundancji  danych,  czyli  przechowywaniu tej  samej  treści  w różnych
miejscach w systemie i w różnych stadiach przetworzenia. Przy takim konkretnym zbiorze informacji
jak archiwum (polskich) grup dyskusyjnych, rozmiar samych, nieprzetworzonych jeszcze danych już
liczy się setkach gigabajtów. Uporanie się z tak ogromną strukturą wymaga specjalnego podejścia.
Standardowe mechanizmy, oferowane na przykład przez relacyjne bazy danych, nie zdają egzaminu
ze względu na zbyt uniwersalne podejście do tematu. Potrzebna jest tu bowiem struktura, która ułatwi
(przyspieszy)   bezpośredni   dostęp   do   danych,   po   które   sięgamy   najczęściej.   Zbudowanie   takiej
struktury umożliwia baza danych Objectivity/DB.

Główną funkcjonalnością wyszukiwarki pełnotekstowej jest oczywiście wyszukiwanie

artykułów na podstawie podanego przez użytkownika ciągu słów, dalej zwanego zapytaniem. Należy
więc zaprojektować strukturę danych w taki sposób, aby zoptymalizować operację pobierania z bazy
danych kolejnych słów zapytania użytkownika. Może to zostać zrealizowane na przykład poprzez
stworzenie odpowiedniej struktury danych, zawierającej wszystkie występujące w bazie słowa i

umożliwiającej  odczytanie  z niej   w szybki  sposób  jednego konkretnego. Pobrane  słowo  powinno
posiadać   łatwo   dostępną   informację   o   wszystkich   swoich   wystąpieniach   w   całym   archiwum
artykułów.   Niesie   to   za   sobą   wprawdzie   niebezpieczeństwo,   że   często   występujące   słowa   będą
niepotrzebnie przetrzymywały listy referencji to prawie wszystkich artykułów w bazie, a tym samym
opóźniały wyszukiwanie  mając  jednocześnie  bardzo znikomy  wpływ na  trafność  wyników. Takie
powiązanie  zawęża jednak w istotny sposób  przeszukiwanie  bazy do konkretnych artykułów, bez
potrzeby wertowania całego archiwum. A kłopoty wynikające z występowania bardzo popularnych
słów można wyeliminować poprzez pomijanie ich w indeksowaniu, lub czyszczenie bazy tuż po tej
operacji,  czy  też  mniej  radykalnie  – poprzez  odpowiednie   oznaczenie  i  tym samym eliminację  z
mechanizmu wyszukiwania.
Następnie, aby znajdowanie konkretnych, dokładnych podciągów zapytania nie wymagało operacji na
całej bazie, również kolejne słowa w poszczególnych artykułach powinny być dostępne przez prostą
referencję. Możliwość nawigacji w obie strony pomiędzy kolejnymi słowami w artykule w znaczny
sposób   ułatwia,   a   co   najważniejsze   przyspiesza   operację   poszukiwania   w   artykułach   dokładnych
ciągów,   identycznych   z   zapytaniem.   Dodatkowy   narzut   w   postaci   przetrzymywania   podwójnie
informacji o kolejności słów w artykule jest więc w tym przypadku uzasadniony.
Jeśli wyszukiwarka ma uwzględniać fleksję języka polskiego, potrzebna jest w bazie danych również
informacja   o   podstawowej   formie   każdego   z   zapisanych   słów.   Aby   informacja   ta   mogła   być
efektywnie   wykorzystana   podczas   operacji   wyszukiwania,   musi   być   ona   dostępna   z   poziomu
poszczególnych   słów   (np.   metoda   w   obiekcie   reprezentującym   słowo).   Tylko   takie   powiązanie
spokrewnionych  fleksyjnie  wyrazów   jest   w   stanie   zapewnić   w   miarę   szybkie   przeszukiwanie
wszystkich możliwych form podanego przez użytkownika zapytania.
Mimo całej tej optymalizacji, kwestią na jaką należy zwrócić szczególną uwagę jest jak największe
odciążenie bazy danych, szczególnie przy procesie wyszukiwania. Ewentualna słaba wydajność jest tu
bowiem   bezpośrednio   odczuwalna   przez   użytkownika   końcowego.   Dlatego   też,   należy   zadbać
również   o   odpowiednie  cache'owania  zapytań   i   zapobieganie   tym   samym   niepotrzebnemu
przeładowaniu   bazy   przez   wykonywanie   identycznych,   powtarzalnych   operacji.   Na   przykład,
kilkukrotne wykonanie dokładnie takiego samego zapytania powinno być automatycznie wykrywane i
zamiast operacji wyszukiwania, powinny zostać pobrane gotowe rezultaty z wcześniej przygotowanej
pomocniczej   struktury   danych.   Mechanizm  cache'owania  zapytań   stwarza   niebezpieczeństwo
serwowania   użytkownikowi   nieaktualnych   informacji.   Dlatego   też,   wyniki   historycznych   zapytań
powinny być nieustannie aktualizowane, tak aby zawsze uwzględniać również nowo dodane artykuły.

Korzystając z powyższych wytycznych, powstaje pewna ogólna wizja działania systemu oraz

schematu struktury danych. Szczegółowo strukturę tę można ją opisać w następujących punktach:

•

Podstawowy mechanizm pobierania danych do przygotowania wyników zapytania realizowany
jest przez pomocniczą haszowaną tablicę wszystkich słów występujących w archiwum newsów
(co niekoniecznie oznacza skopiowanie jeden do jednego słownika poprawnej polszczyzny) –
taka implementacja pozwala na szybkie pobranie konkretnego słowa do dalszego przetwarzania,
co polepsza efektywność operacji wyszukiwania.

•

Do każdego ze słów podpięte jest drzewo artykułów w dwóch formach: bezpośrednio (poprzez
kolekcję referencji do artykułów), oraz poprzez pośrednie obiekty – pozycje danego słowa w
artykule (patrz rysunek: Przykład struktury danych). Pozycji takich jest dokładnie tyle ile w
sumie wszystkich słów we wszystkich artykułach. Pozycje służą przede wszystkim do szybkiego
znajdowania dokładnych ciągów wielu słów (np. cytaty) wśród zindeksowanych artykułów.

•

Najbardziej popularne słowa, czyli takie które pojawiają się w większości artykułów (dokładna
wartość procentowa progu jest konfigurowalna z poziomu kodu) są odpowiednio oznaczane, tak
aby nie były one brane pod uwagę przy wyszukiwaniu (oprócz wyszukiwania dokładnych
ciągów). Całkowita rezygnacja z przechowywania struktury pozycji dla słów popularnych jest
niepożądana, ponieważ mimo iż odchudza w znacznym stopniu bazę, to przekreśla jednocześnie

●

tworzenie powiązań artykuł – słowo

●

tworzenie struktury powiązań fleksyjnych słów

Pierwszy etap – parsowanie treści artykułu – polega na analizie artykułu w celu podziału

informacji w nim zawartej na informację opisującą artykuł oraz rzeczywistą treść artykułu (i
ewentualnie, dodatkowo stopkę z podpisem). Pojedynczy post ściągnięty z grupy dyskusyjnej ma w
miarę standardową strukturę. Najważniejsze informacje zawarte w opisie artykułu to, w kolejności w
jakiej występują:

•

ID artykułu (tzw. Message-ID), czyli unikalny, jednoznaczny identyfikator wiadomości wśród
wszystkich postów grup dyskusyjnych

•

temat artykułu (nie mylić z tematem grupy dyskusyjnej)

•

autor artykułu (imię i nazwisko, e-mail) – nie zawsze wprawdzie da się jednoznacznie określić
autora na tej podstawie, często jest to jednak możliwe

•

data wysłania artykułu

•

powiązanie artykułu z innymi artykułami (miejsce w wątku, artykuł rodzic, dzieci artykułu)

Parametry mają istotny wpływ na działanie wyszukiwania, ponieważ są one brane pod uwagę przy
obliczaniu wagi danego artykułu (np. gdy słowo pojawia się w temacie ma to większe znaczenie niż
pojawienie się go w treści artykułu, a gdy istnieje tylko w stopce, ma to znaczenie marginalne) oraz
przy zaawansowanym wyszukiwaniu (np. ze względu na daty lub autora postu). Oprócz tego, w
opisie   artykułu   zawarte   są   inne,   mniej   istotne   informacje,   takie   jak   np.   nazwa   klienta   grup
dyskusyjnych,   z   którego   wysłany   został   post,   nazwa   serwera,   priorytet,   czy   rodzaj   kodowania
wiadomości (Dokładną strukturę artykułu przedstawia rysunek: Struktura wiadomości NNTP). Dane
dodatkowe  mogą  zostać   użyte  np.   w do  stworzenia   statystyk  grup,  mogą  też  być  przydatne  do
lepszego   zidentyfikowania   autora   (np.   poprzez   określenie   klienta   grup   dyskusyjnych,   z  którego
korzysta   autor).   Ich  znaczenie   dla   samego  wyszukiwania   wiadomości   jespfft   jednak  niewielkie.
Wynikiem parsowania artykułu jest nowo powstały obiekt, reprezentujący jeden konkretny artykuł
grup   dyskusyjnych.   Obiekt   ten   posiada   standardową   strukturę,   która   umożliwia   jego   dalsze
przetwarzanie na kolejnych etapach indeksowania.

Drugi etap indeksowania to umieszczenie artykułu w ogólnej strukturze postów, czyli

określenie   miejsca   artykułu   w   konkretnym   wątku.   Dokonuje   się   tego   poprzez   dodanie
zindeksowanej  wiadomości  do listy artykułów w wątku na określonej  pozycji  (jeśli  artykuł jest
odpowiedzią na inny post), lub stworzenie nowego wątku jako obiektu w bazie i przypisanie do
niego indeksowanego artykułu (jeśli  artykuł rozpoczyna wątek). Struktura wątków i postów jest
bardzo istotna nie tyle przy wyszukiwaniu, lecz raczej przy prezentacji końcowych wyników – np. w
postaci   drzewa   wątków.   Dane   potrzebne   do   określenia   miejsca   danego   artykułu   w   strukturze
wątków   znajdują   się   w   jednym   z   tagów   standardowej   struktury   artykułu:  References.  Tag   ten
zapisywany jest jako pole nowo powstałego obiektu podczas parsowania.

Trzeci, najważniejszy etap procesu indeksowania polega na analizie samej treści artykułu,

wydzieleniu z niej pojedynczych słów i stworzeniu ich struktury. Każde kolejne słowo, znajdujące się
w treści artykułu, dodawane jest do bazy danych jako oddzielny obiekt (o ile oczywiście w bazie tego
słowa jeszcze nie uwzględniono). Następnie tworzone jest dwustronne powiązanie pomiędzy słowem
i artykułem. Każde słowo “wie” w ilu i w jakich konkretnie artykułach się znajduje, każdy artykuł
posiada szczegółową informację o słowach w nim zawartych. Dodatkowo, tworzona jest
dwukierunkowa lista słów występujących kolejno w artykule – nazywana od tej pory listą pozycji.
Każdy obiekt reprezentujący pozycję powiązany jest z jednym słowem i jednym tylko artykułem oraz
przechowuje informacje o tym, które miejsce zajmuje dane słowo w konkretnym artykule.

nawet oddzielnie dla każdego artykułu, optymalnie jednak może to być w granicach kilkunastu
lub kilkudziesięciu artykułów)

•

Formalne rozdzielenie indeksowania artykułów od analizy fleksyjnej również wpływa na wzrost
elastyczności procesu – obie operacje można przeprowadzać oddzielnie, starając się wybrać
momenty względnie małego obciążenia bazy (np. pory nocne)

Gdy już omówiliśmy główny mechanizm działania aplikacji, możemy przejść do etapu, na

którym skorzystamy ze struktury wygenerowanej podczas indeksowania artykułów – czyli do
algorytmu wyszukiwania informacji.

4.4.

Algorytm wyszukiwania

Mechanizm wyszukiwania jest drugim co do ważności modułem aplikacji. Jego efektywność

zależy   bezpośrednio   od   efektywności   mechanizmu   indeksowania,   czyli   adekwatności   struktury
danych  systemu do planowanego  sposobu  wyszukiwania  w nim informacji.  Mimo tej  zależności,
istnieje   jednak   pewne   pole   manewru   przy   budowaniu   algorytmu   wyszukiwania   i   od   niektórych
decyzji podjętych na tym etapie może w znacznym stopniu zależeć wydajność całej aplikacji.

Sposób wyszukiwania zależy przede wszystkim od rodzaju informacji, jakie chcemy uzyskać.

Nie   można   nigdy   powiedzieć,   że   dany   algorytm   wyszukiwania   jest   najlepszy.   Można   jedynie
stwierdzić, że najlepiej spełnia zdefiniowane wcześniej kryterium trafności. Jednak, co nie wydaje się
wcale   oczywiste,   nie   zawsze   trafność   musi   być   tym,   czego   oczekujemy   od   wyszukiwarki.   A
przynajmniej   nie   zawsze   musi   mieć   ona   najwyższy   priorytet.   Kryteriów   oceny   wyników
wyszukiwania może być znacznie więcej i każde z nich może okazać się odpowiednie w określonej
sytuacji. Oprócz trafności rezultatów mogą to być między innymi:

–

czas wyszukiwania – ilość sekund (milisekund) od wysłania zapytania do zwrócenia wyników
(zazwyczaj liczona jako czas od otrzymania przez aplikację zapytania do zwrócenia wyników, z
pominięciem czas na wysłanie wyników przez sieć internetową, czy intranet, gdyż czas ten
zależy najczęściej od czynników niezależnych od samego silnika wyszukiwania)

–

stosunek wyników relewantnych (spełniających zdefiniowane kryteria trafności) do wszystkich
wyników wyszukiwania

–

niski procent wyników nierelewantnych

–

i inne

Tak więc, jak zostało to już zresztą wspomniane we wstępie pracy, pierwsze pytania jakie

należy sobie zadać przy budowie nowej wyszukiwarki dotyczyć powinny kryteriów, jakie należałoby
zastosować. W szczególności:

–

Jak zdefiniować trafność wyników i jak ma się ona do innych kryteriów oceny wyników
wyszukiwania?

–

Jakie kryteria powinny być priorytetowe przy zwracaniu wyników wyszukiwania?
(przedstawione np. procentowo, od najbardziej do najmniej istotnych)

W przedstawianej aplikacji postawiono przede wszystkim na trafność rezultatów

wyszukiwania. Szybkość działania aplikacji znajduje się na drugim miejscu, co oczywiście wcale nie
oznacza, że była to przy budowanie aplikacji sprawa mało istotna – większość optymalizacji zostało
przeprowadzonych właśnie ze względu na słabą wydajność konkretnego rozwiązania. Chodzi jednak o
to, że przy projekcie i implementacji nie było brane pod uwagę jakiekolwiek działanie, mające na celu
przyspieszenie aplikacji, poprzez zmniejszenie czy zawężenie jej funkcjonalności. Takie działania
powinny być zastosowane przy ewentualnym komercyjnym wdrożeniu, w którym niekoniecznie

niezbędna będzie cała dostarczona funkcjonalność, byłyby jednak bezcelowe i szkodliwe omawianej
aplikacji, której celem jest bardziej prezentacja wszystkich możliwości rozwiązania, niż maksymalna
wydajność.   Z   tego   samego   względu,   przy   budowie   nie   były   stosowane   żadne   techniczno-
administracyjne   aspekty   przyspieszenia   działania,   jak   na   przykład   stworzenie   rozproszonej   sieci
danych   połączonej   w   klaster,   przeniesienie   części   operacji   na   inne   maszyny   w   celu   odciążenia
głównego silnika bazy, etc. To również działania istotne dla końcowego wdrożenia, lecz zupełnie
zbędne w aplikacji, będącej przedmiotem tej pracy..
Trafność natomiast została potraktowana priorytetowo. A konkretnie definicja trafności, obejmująca
dwa  najważniejsze   dla   nas   aspekty,  czyli   dokładność   i   trwałość   rozumiana   jako   niezależność   od
czasu.

–

dokładność – zazwyczaj standardowy użytkownik oczekuje jednego z dwóch rodzajów wyników
przy  korzystaniu   z  wyszukiwarki   pełnotekstowej   Pierwszy   to   artykuły  zawierające   dokładny
podany w zapytaniu ciąg słów (ew. w różnych formach fleksyjnych) – przykładem może być
tutaj   cytat,   tytuł   książki,   informacje   na   temat   konkretnej   dziedziny   o   specyficznej,   kilku
członowej   nazwie,   imię   i   nazwisko   popularnej   osoby,   i   inne.   W   przeciwnym   wypadku
standardowy użytkownik szuka najprawdopodobniej artykułów, zawierających informacje które
są   częścią   wspólną   wszystkich   podanych   w   zapytaniu   wyrażeń,   np.   gdy   nie   wie   jak
skonfigurować modem cyfrowy łączący z Internetem pisze: „Neostrada  Linux instalacja”, gdy
poszukuje   aktualności   ze   świata   terroryzmu:   „Bush  Bin  Laden  terroryzm”,   etc..   W   naszym
rozwiązaniu przyjęliśmy, że ważniejsze są te pierwsze artykuły, ponieważ zazwyczaj zwracają
dokładnie   to   czego   użytkownik   oczekuje.   Jeśli   jednak   takich   wyników   nie   ma   lub   jest   ich
niewiele, powinny zostać zwrócone również artykuły z drugiej grupy.

–

trwałość i niezależność od czasu – chodzi o to, żeby uniknąć zjawiska “gubienia” artykułów –
często   występującego   w   popularnych   wyszukiwarkach   newsów     –   polegającego   na
marginalizacji   a   w   końcu   ignorowaniu   wyników   starszych   w   czasie.   Specyfika   grup
dyskusyjnych   polega   między   innymi   na   tym,   że   często   odpowiedzi   na   konkretne   pytanie
pojawiają się tylko raz, a następni pytający otrzymują zamiast odpowiedzi sugestię, aby najpierw
przeszukać   archiwum   (czasami   nawet   z   podaniem  Message-ID  odpowiedniej   wiadomości).
Zdarza się też, że konkretny temat pojawia się na grupach intensywnie przez bardzo krótki okres
czasu   (np.   najnowszy   błąd   w   jądrze   Linuksa,   czy   najnowszy   model   samochodu   BMW)   a
następnie znika i nikt już o nim nie wspomina. W takich przypadkach, przeszukanie odległego w
czasie  archiwum bywa  jedynym możliwym sposobem  dotarcia  do szukanej  informacji.  Taka
możliwość powinna więc zostać udostępniona.

Mając już odpowiedzi na dwa podstawowe pytania, możemy się zabrać do właściwej analizy

omawianego systemu, pod kątem algorytmu wyszukiwania i sposobu oceny rezultatów. Ze względu
na dużą różnorodność zastosowanych rozwiązań dotyczących poszczególnych algorytmów
wyszukiwania, zostaną przedstawione oddzielnie trzy podstawowe algorytmy wyszukiwania, które
powstały na użytek przedstawianej aplikacji.

I. Wyszukiwanie dokładnych ciągów

Ta metoda wyszukiwania opiera się na stworzonej podczas indeksowania strukturze, w której

treść zindeksowanych artykułów reprezentowana jest jako dwukierunkowe listy pozycji – obiektów
wiążących ze sobą słowo i artykuł. Każde słowo posiada informację na temat wszystkich pozycji, na
których występuje we wszystkich artykułach. Jedna referencja umożliwia przejście z poziomu słowa
do poziomu połączonej z nim pozycji i stamtąd nawigacja po kolejnych pozycjach w celu znalezienia
artykułów spełniających kryteria poszukiwania.

Szczegółowo algorytm ten przedstawia się następująco:
1. Na początku pobierane jest pierwsze słowo zapytania wysłanego przez użytkownika.

informacją o jednym tylko słowie wspólnym z zapytaniem.
Wynikiem takiego wyszukiwania są zazwyczaj dwie listy:

–

artykułów zawierających dokładne ciągi słów z zapytania

–

artykułów zawierających od 2 do N-1 słów z zapytania (zakładając że zapytanie ma N słów)

Powyższy algorytm przedstawiony jest obrazowo na rysunku: Wyszukiwanie dokładnych

ciągów.

Warto zauważyć, że przedstawiony algorytm ma sens jedynie, gdy znalezione rezultaty

zawierają co najmniej podciąg dwóch słów wspólnych z szukanym zapytaniem. Artykuły posiadające
wspólne tylko jedno słowo można spokojnie pominąć (a tym samym pominąć całkowicie ostatnią
iterację powyższego algorytmu), gdyż zostaną one i tak znalezione w kolejnym wyszukiwaniu, już bez
uwzględniania wspólnych podciągów.

II. Wyszukiwanie części wspólnej
Wyszukiwanie części wspólnej oznacza, że nie szukamy już dokładnych (pod)ciągów

zawartych w zapytaniu, lecz raczej staramy się zidentyfikować artykuły, które zawierają wszystkie
podane słowa, lub przynajmniej jak największą ilość słów podanych w zapytaniu. Algorytm ten w
mniejszym stopniu wykorzystuje zdefiniowane dla artykułów dwukierunkowe listy pozycji. Korzysta
za to intensywnie z operacji na zbiorach, w szczególności z sumy zbiorów i ich intersekcji (części
wspólnej).

Punktem wyjścia jest w tym przypadku również pierwsze słowo zapytania. Pobierane jest ono

jako obiekt-korzeń z bazy danych, tak jak każde z kolejnych słów. Różnica polega na tym, że nie
istnieje tutaj specjalny algorytm dla pierwszego słowa. Wszystkie traktowane są jednakowo przy
wyszukiwaniu, gdyż nie o kolejność nam tutaj chodzi, a o samo wystąpienie w artykułach podanych w
zapytaniu słów.
Dla każdego ze słów pobranych z zapytania użytkownika wykonujemy najpierw prosty algorytm,
który wygląda następująco:

1. Pobieramy kolejne słowo z zapytania
2. Pobieramy listę pozycji dla pobranego słowa

3. Dodajemy artykuły z pobranej listy na kolejnej pozycji w tymczasowej tablicy wyników
Po wykonaniu tej operacji, w tymczasowej tablicy, o długości równej ilości słów zapytania

znajdują się listy artykułów dla każdego ze słów. Teoretycznie jest to już lista wyników naszego
zapytania.   Jedyne   co   należy   teraz   zrobić,   to   połączyć   listy   z   tymczasowej   tablicy,   eliminując
powtarzające   się   artykuły   (ilość   powtórzeń   oznacza   w   tym   wypadku   liczbę   słów   z   zapytania
występujących w pobranym artykule, wpływa więc bezpośrednio na   priorytet artykułu) i obliczyć
wagę każdego z nich.  Intersekcja  (część wspólna)  wszystkich  list  tworzy nam listę  artykułów, w
których występują wszystkie słowa z zadanego zapytania – te artykuły otrzymują najwyższą wagę (na
podstawie ustalonych wcześniej kryteriów). Reszta, zależnie od liczby powtórzeń, otrzymuje niższą
lub wyższą wagę i lokowana jest na odpowiedniej pozycji, w oddzielnej liście.
Wynikiem tego wyszukiwania są więc, podobnie jak w przypadku wyszukiwania ciągów słów, dwie
listy:

–

dokładnych wyników (zawierających wszystkie słowa z zadanego zapytania)

–

wyników częściowych, zawierających od 1 do N-1 słów z zadanego zapytania (w sumie
zapytanie ma N słów).

Obrazowo algorytm został przedstawiony na rysunku: Wyszukiwanie części wspólnej

Zakładając, że nie zostały wybrane niestandardowe kryteria wyszukiwania, wszystkie trzy (a

właściwe cztery, gdyż wyszukiwanie z Gramem wykonywane jest w praktyce dwukrotnie) algorytmy
zwracają   pewną,   nieuporządkowaną   w  żaden   sposób   listę   rezultatów.   Każdy  z  wyników   posiada
wprawdzie pewne informacje o znalezionym artykule, między innymi na temat trafności wyniku, takie
jak np. ilość znalezionych słów występujących w jednym ciągu, suma wszystkich znalezionych słów z
zapytania,   czy  liczba   słów   o  tej   samej   formie   podstawowej.   Nie   istnieje   jednak   jeszcze   metoda
porównania tych wyników, nadania odpowiednich wag poszczególnym atrybutom i stworzenia na tej
podstawie posortowanej  względem trafności listy rezultatów. A jedynie taka właśnie lista stanowi
wartość dla użytkownika końcowego.
W  tym  właśnie   momencie,   mając   konkretną   listę   zwróconych  rezultatów  wyszukiwania,  możemy
przejść  do drugiego etapu, czyli obliczenia wagi (ważności) każdego ze znalezionych artykułów. Aby
obliczona waga była jak najbliższa rzeczywistej trafności, którą w ogólny sposób zdefiniowaliśmy na
początku   rozdziału,   potrzebna   jest   pewna   lista   kryteriów,   które   powinniśmy   brać   pod   uwagę   w
naszych obliczeniach. Poniższa lista jest próbą wskazania najważniejszych z nich.
Kryteria brane pod uwagę do obliczenia całkowitej wagi artykułu, w kolejności od najważniejszych
do najmniej istotnych:

–

Ilość szukanych słów, występujących w znalezionych artykułach w tej samej kolejności jak w
zapytaniu.

To   kryterium   zostało   nieprzypadkowo   postawione   na   miejscu   pierwszym.   Wydaje   się,   że
większość użytkowników, wpisując  w formularzu określony ciąg słów, oczekuje w rezultacie
wyników zawierających dokładnie ten sam ciąg, bądź ewentualnie znaczną część wyrazów tego
ciągu  w  niezmienionej  kolejności.  Jest   bardzo   prawdopodobne,  że  są  to  właśnie  te  artykuły,
których użytkownik poszukuje. A nawet jeśli tak nie jest, i tak nie zaszkodzi zwrócenie tych
artykułów z nieco wyższym priorytetem. Zazwyczaj bowiem, jeśli oczekiwanym wynikiem jest
nie dokładny ciąg, a część wspólna artykułów zawierających podane wyrazy, to po prostu ciąg
taki nie występuje nigdzie w archiwum.

–

Wystąpienie dokładnego poszukiwanego ciągu

Jest to skrajny przypadek wcześniejszego punktu. Takie artykuły powinny dostawać
zdecydowanie wysoki priorytet. Realizacja może wyglądać na przykład w postaci specjalnej
premii przy obliczaniu wagi dla takiego artykułu.

–

Liczba szukanych słów zapytania, które występują w znalezionym artykule.

Mowa oczywiście o słowach, które nie występują w artykule ciągu, lecz rozrzucone są po nim,
być może występując wielokrotnie. Kryterium ilości wyszukanych słów zapytania jest drugim co
do ważności i każde znalezione słowo powinno zwiększać w znaczny sposób wagę artykułu w
którym się znajduje. Przy czym priorytet jest trochę niższy niż w przypadku tych samych słów
połączonych w ciąg. W praktyce, słowa zapytania rozrzucone po artykule występuję
zdecydowanie częściej niż ciągi.

–

Wystąpienie w artykule wszystkich szukanych słów.

Takie artykuły, podobnie jak artykuły zawierające dokładny poszukiwany ciąg, powinny być
premiowane dodatkowo przy wyliczaniu wagi (premia oczywiście odpowiednio mniejsza niż w
poprzednim przypadku).

–

Kluczowe słowa występujące w temacie artykułu

Jest to istotne kryterium, szczególnie jeśli musimy w jakiś sposób rozróżnić artykuły zawierające
te same ilości poszukiwanych słów. Założenie, że słowa występujące w temacie wiadomości,
bądź (to sprawa do dokładniejszego zbadania) w pierwszej części tekstu więcej mówią o treści
artykule niż słowa znajdujące się w jego dalszych częściach, wydaje się sensowne. W

przypadkach niejednoznacznych, warto więc wziąć pod uwagę nie tylko samą częstotliwość
występowania, ale również lokalizację słów artykule.

–

Wiadomość wysłana przez popularnego autora

To kryterium może być bardzo zwodnicze i nie powinno być stosowane jako decydujące, lecz
jeśli już, jedynie uzupełniająco – różnicując artykuły, które do tej pory uzyskały podobną lub taką
samą   zsumowaną   wagę.   Teoretycznie   bowiem,   często   wypowiadający   się   na   grupach
dyskusyjnych użytkownicy powiadają  większą wiedzę i prawdopodobieństwo udzielenia przez
nich trafnej odpowiedzi na zadany temat jest wyższe. Z drugiej jednak strony, bywa że niełatwo
jest zidentyfikować  taką osobą – na przykład jeśli  korzysta ona z Usenetu za pośrednictwem
strony   internetowej   umożliwiającej   wysyłanie   newsów   bez   podania   adresu   e-mail,   lub   też
świadome   ukrywanie   swojej   tożsamości   na   grupach   dyskusyjnych.   Często   zdarzać   się   mogą
również   pomyłki   związane   np.   z   powtarzającym   się  nickiem,   identycznym   imieniem   i
nazwiskiem,   korzystaniem   z   tego   samego   konta,   a   nawet   podszywaniem   się   pod   innych
uczestników dyskusji.

–

Data wysłania artykułu

Jest to najmniej istotne kryterium, może zostać nawet pominięte w implementacji. Chodzi o to, że
jeżeli wszelkie inne sposoby mierzenia zawiodą, priorytet dostać mogą artykuły napisane w
okresie późniejszym, czyli w domyśle, bardziej aktualne. Należy jednak (co zostało wspomniane
już na samym wstępie) wystrzegać się całkowitego pomijania treści starszych, jak również
nadawania zbyt wysokiego priorytetu dacie wysłania wiadomości.

W ten sposób omówiony został cały mechanizm wyszukiwania informacji w systemie. Od

algorytmów wyszukiwania, po nadanie wagi każdemu z rezultatów, aż do ostatecznej listy wyników
prezentowanej końcowemu użytkownikowi. Jest jednak jeszcze jedna ważna kwestia dotycząca
wyszukiwania, która została do tej pory odsunięta nieco na bok. Chodzi o cache'owania wyników
zapytań.

Jeśli przyjmujemy, że obciążenie systemu, a co za tym idzie również obciążenia bazy danych,

będzie   znaczne,   oczywiste   jest,   że   zapytania   przesyłane   do   systemu   będą   się   często   powtarzać.
Dlatego   też,   należy   pomyśleć   o   optymalizacji   zarządzania   takimi   zapytaniami,   tak   aby   bez
specjalnego opóźnienia w działaniu, można było sprawdzić, czy dane zapytanie wystąpiło już w bazie
i jeśli miało to miejsce, zaserwować użytkownikowi gotową listę wyników. Zakładamy, że w bazie
istnieje dodatkowa struktura, której zadaniem jest przechowywanie historii wykonanych zapytań wraz
z   ich   rezultatami.   Istotne   jest,   aby   struktura   ta   zbudowana   była   w   taki   sposób,   aby   zwiększyć
wydajność   mechanizmu   wyszukiwania   dla   często   występujących   zapytań,   nie   opóźniając
jednocześnie tej operacji dla zapytań oryginalnych, nie zarejestrowanych jeszcze w naszej strukturze.
Rozwiązaniem   jest   przechowywanie     zapytań   historycznych   jako  haszowanych  tablic   referencji,
znajdujących   się   w   obiektach   konkretnych     słów,   od  których   zaczyna   się   dane   zapytanie.   Takie
rozwiązanie   zawęża   liczbę   obiektów   przeszukiwanych   podczas   operacji   sprawdzania,   czy   dane
zapytanie (wraz z wynikami)  znajduje  się  już  w archiwum. Nie  potrzeba  też wykonywać prawie
żadnych dodatkowych operacji  na  bazie w celu sprawdzenie czy dane zapytanie  wystąpiło już w
systemie.   Struktura  jest   bowiem  bezpośrednio   dostępna   z  obiektu,   który  i   tak   pobieramy  w  celu
wykonania algorytmu wyszukiwania. Jest to spora oszczędność czasu i zasobów.

Dokładne omówienie rozwiązań implementacyjnych, dotyczących algorytmu wyszukiwania,

obliczania wagi wyników, jak również systemu cache'owania zapytań znajduje się w rozdziale piątym
– Rozwiązania implementacyjne: System ściągania, indeksowania i wyszukiwania newsów.

4.5.

Alternatywne koncepcje

Jednym z poważnych ograniczeń napotkanych podczas implementacji opisanego projektu

okazał się niedostatek zasobów dyskowych. Taqqq wydawałoby się mało istotna kwestia wpłynęła w
całkiem   znaczny   sposób   na   zastosowane   w   praktyce   rozwiązania,   szczególnie   te   związane   ze
sposobem przechowywania danych w bazie (strukturą danych). Zakładając, że nie mamy sztywnego
ograniczenia co do akceptowalnej maksymalnej wielkości przechowywanych danych, otwierają się
przed nami ogromne możliwości wykorzystania takiego potencjału – możliwości, które nie były brane
pod uwagę przy implementacji.  Mowa  tutaj  o odejściu  od  oszczędnego (pod  względem zasobów
dyskowych) projektowania i zastosowaniu bardzo dużej, ale przemyślanej redundancji danych, w celu
zwiększenia szybkości działania aplikacji. Wiąże się to oczywiście ze znacznym wzrostem rozmiaru
bazy danych – nawet o kilka rzędów wielkości. Tak gwałtowne zwiększenie rozmiaru aplikacji jest
bardzo ryzykowne i aby przyniosło spodziewane efekty – czyli zwiększenie wydajności – musi być
bardzo dokładnie zaplanowane.
Ideą,   jaka   przyświeca   koncepcji   zwiększania   wydajności   poprzez   redundancję   danych   jest
zapewnienie jak najlepszej koncentracji danych, potrzebnych do wykonania pojedynczej operacji na
bazie. Chodzi tu zarówno o koncentrację koncepcyjną – czyli odpowiednie asocjacje między typami
danych, realizowane jako referencje i kolekcje referencji w obiektach, jak i o koncentrację fizyczną,
czyli   taką   implementację   bazy,   aby   dane   często   uczestniczące   w   tych   samych   operacjach
przechowywane   były  fizycznie   blisko   siebie.   Drugi   sposób   –   koncentracja   fizyczna   –   jest   nieco
trudniejszy w realizacji i przy stosowanym poziomie abstrakcji narzędzi deweloperskich, zależy mniej
od programisty a bardziej  od zastosowanego oprogramowania.  Objectivity/DB  oferuje  wprawdzie
pewne mechanizmy, które mogą zostać wykorzystane w celu  optymalizacji  dostępu do danych na
poziomie  fizycznym.  Jest  to realizowane poprzez odpowiedni  podział  federacji  na bazy danych i
kontenery, odpowiednie rozmieszczenie danych w każdej ze struktur, zastosowanie specyficznych dla
Objectivity   kolekcji,  jak  haszowane   drzewa,   tablice   i   listy  obiektów,   etc.  Jednak  w  tym  miejscu
skoncentrujemy   się   na   ciekawszym   koncepcyjnie,   a   zarazem   bezpośrednio   powiązanym   z
optymalizacją   fizyczną   zagadnieniem,   jakim   jest   optymalizacja   struktury   danych   na   poziomie
schematu.
Chodzi tutaj o takie przeprojektowanie struktury klas i asocjacji między nimi, aby zapewnić jeszcze
szybszy   i   wygodniejszy   dostęp   do   danych,   wykorzystywanych   przy   mechanizmie   wyszukiwania.
Koncepcji   może   być   tu   wiele.   Zaprezentowane   zostaną   jednak   tylko   dwie   z   nich.   Te,   które
charakteryzują się według nas niezerowym prawdopodobieństwem przyszłej realizacji w praktyce.

1. Struktura słów oparta o haszowane tablice referencji
To bardziej zasobochłonna z omawianych tutaj propozycji. Polegałaby ona na

przeprojektowaniu   struktury   obiektów   słów   w   bazie   danych,   w   taki   sposób,   aby   każde   ze   słów
zawierało w sobie trójwymiarową, haszowaną tablicę, zbudowaną z powiązanych z nim kolejnych
słów   we   wszystkich   zindeksowanych   artykułach.   Pierwszym  wymiarem   (n)   byłyby  pozycje   słów
następujących   po   słowie   głównym   w

. Każdy rząd w tablicy to kolejna pozycja, czyli np. rząd

pierwszy to tablica wszystkich słów bezpośrednio następujących po w

, drugi to tablica słów

występujących na drugiej pozycji po w

, etc. Drugi wymiar (m) oznaczałyby artykuły, a dokładnie

kolejne słowa, będące częściami artykułów, następującymi po miejscu wystąpienia w nich słowa
głównego w

. Trzecim wymiarem, byłaby tablica obiektów pozycji, powiązanych ze słowem w

takich, że dla danego słowa w

n,m

, jest to lista wszystkich pozycji (słów w artykułach) następujących

bezpośrednio po liście słów w

1,m

... w

n,m

w danym artykule. Każdy z elementów tablicy w

n,m

jest więc

powiązany z co najmniej jedną pozycją listy p. Lista p zawiera wszystkie pozycje powiązane ze
słowem głównym w

Można na tą strukturą spojrzeć  również jako jeden wielki graf,  łączący ze sobą wszystkie słowa
występujące   we   wszystkich   zindeksowanych   artykułach   oraz   ich   pozycje   w   tychże   artykułach.
Dokładnie   powyższa   koncepcja   została   przedstawiona   na   rysunku:  Struktura   słów   oparta   o
haszowane tablice referencji.

danych) uniemożliwić wyszukiwanie. W pracy ten problem został częściowo rozwiązany (a
właściwie ominięty) poprzez pomijanie słów najbardziej popularnych. Wyszukiwanie zaczynamy od
przeszukiwania pozycji dla słów zapytania występujących rzadko, a następnie nawigujemy w obie
strony w poszukiwaniu odpowiednich podciągów. Sposób ten sprawdza się całkiem nieźle jeśli w
zapytaniu rzeczywiście znajduje się co najmniej jedno słowo bardzo mało popularne. Problem
pojawia się gdy wszystkie słowa zapytania są słowami często występującymi w artykułach, a dopiero
ich odpowiednia kombinacja tworzy unikalną frazę, nazwę instytucji, czy cytat. W takim wypadku
algorytm nie ma innego wyjścia niż wyszukać wszystkie pozycje dla jednego ze słów z zapytania. W
wyjątkowych przypadkach może to nawet uniemożliwić wyszukanie informacji.

Nowe rozwiązanie

Z drugiej strony, w proponowanym tutaj alternatywnym rozwiązaniu, problem ten praktycznie zostaje
całkowicie  zniwelowany. Każde  słowo  powiązane  jest  bowiem ze wszystkimi słowami  z którymi
łączy się w artykułach.  Nie ma więc potrzeby przeszukiwania wszystkich pozycji dla interesującego
nas słowa. Wystarczy pobrać pozycje powiązane z dwoma pierwszymi słowami zapytania (a przy
zastosowaniu pierwszej koncepcji z trójwymiarową tablicą, również z kolejnymi słowami zapytania,
w zależności od zdefiniowanego rozmiaru tablicy) a następnie nawigować już według tego samego
algorytmu, w celu znalezienia całego poszukiwanego ciągu. Zwiększenie efektywności wyszukiwania
zależy tutaj bezpośrednio od ilości słów, z którymi powiązane jest pierwsze słowo szukanego ciągu.
Jest to zależność liniowa – jeśli szukane słowo powiązane jest poprzez listę pozycji z ilością Z innych
słów, wzrost wydajności części wyszukiwania odpowiedzialnej za pobranie   listy pozycji powinien
być w przybliżeniu Z-krotny. Niestety, taka sama zależność dotyczy również miejsca na dysku, które
potrzebne   jest   do   zbudowania   struktury,   zapewniającej     dodatkowe   powiązania,   niezbędne   do
implementacji tej koncepcji.

Korzyści z zastosowania nowego rozwiązania

Oprócz celu głównego, czyli przyspieszenia działania, zastosowanie proponowanej koncepcji

może przynieść również inne, całkiem ciekawe możliwości, rozszerzające znacznie funkcjonalność
aplikacji. Omówimy najciekawsze z nich:

–

Zaawansowane wyszukiwanie z użyciem wyrażeń “pseudo-regularnych”

Chodzi o wyrażenia typu: znajdź wszystkie artykuły, które zawierają podciąg “Ala ma * kota”,
gdzie * może być dowolnym wyrazem, np. “ładnego”, “niegrzecznego”, “strasznego”, etc.
Teoretycznie można wykonać taką operację również w obecnym systemie. Koszt jednak tego
byłby   nieporównywalnie   większy   –   zamiast   zatrzymywać   nawigowanie   po   pozycjach   przy
natrafieniu na pierwsze słowo artykułu nie pasujące do zapytania, trzeba by za każdym razem
sprawdzać wszystkie słowa i znajdować te, które pasują do wyrażenia. W modelu słów opartym
na   haszowanych   tablicach   referencji,   tę   samą   informację   mamy   tak   naprawdę   dostępną   z
definicji, tzn. bez stosowania dodatkowych algorytmów. Każde słowo powiązane jest w listą
wszystkich słów, występujących w artykułach po nim, na odpowiednich pozycjach. Jedyne co
należałoby   zrobić,   to   sprawdzić   czy   na   odpowiednich,   wymaganych   pozycjach   znajdują   się
podane   w   zapytaniu   słowa   (omijając   pozycję   oznaczoną   gwiazdką).   Jeśli   znajdują   się   w
strukturze artykuły spełniające wszystkie z tych założeń, ich lista jest jednocześnie listą wyników
naszego   zapytania.   Tym   samym,   to   co   wydawałoby   się   niemożliwe   przy   zastosowaniu
standardowej struktury zindeksowanych danych (powiązania artykuł – pozycje – słowa) okazuje
się nie tylko możliwe, ale wręcz bardzo proste i efektywne w przedstawionej, zmodyfikowanej
strukturze.

–

Znajdowanie niedokładnych ciągów

Stosując mechanizm omówiony powyżej (wyrażenia “pseudo-regularne” na słowach), możemy
ulepszyć również sam mechanizm wyszukiwania, zarówno podciągów jak i algorytm

znajdowania   części   wspólnej   słów.   Użytkownik   szukając   jakiejś   frazy   lub   kilku   słów
kluczowych zazwyczaj oczekuje, że znalezione artykuły będą nie tylko zawierały podane przez
niego   słowa,   ale   również,   że   tematyka   artykułu   będzie   bezpośrednio   związana   ze   słowami
kluczowymi   które   wpisał.   Oczywiście   automatycznie   trudno   odgadnąć   dokładną   tematykę
artykułu po jego treści. Można jednak wnioskować, że jeśli poszukiwane słowa znajdują się w
tym samym zdaniu (lub w zdaniach sąsiadujących), to jest dużo bardziej  prawdopodobne, że
treść artykułu będzie bezpośrednio związana z tymi właśnie słowami kluczowymi. A na pewno
dużo bardziej, niż w przypadku, gdy słowa te rozrzucone są po całym artykule.
Wykorzystując   to   założenie,   możemy   tak   zmodyfikować   mechanizm   wyszukiwania   słów
kluczowych, aby w pierwszej kolejności brane były pod uwagę słowa występujące blisko siebie
(niekoniecznie   w   jednym   ciągu).   To   oczywiście   również   można   zrealizować   wykorzystując
strukturę danych z prezentowanego rozwiązania. W aktualnym rozwiązaniu jest to realizowane
już po wyszukaniu wszystkich rezultatów, na podstawie pozycji poszczególnych wyszukanych
słów w artykułach  (wcześniej  nie  mamy nawet  możliwości, żeby zgadnąć ich  kolejność). W
zmodyfikowanym rozwiązaniu, już podczas wyszukiwania moglibyśmy decydować o priorytecie
poszczególnych artykułów, a w przypadku bardzo dużej ilości wyników, nawet rezygnować z
prezentowania   tych,   w   których   nie   widać   istotnego   powiązania   pomiędzy   poszukiwanymi
słowami.

–

Wyszukiwanie po „najczęstszych sąsiadach”

Zarówno   przy   pierwszej   jak   i   przy   drugiej   (zawężonej)   koncepcji   pojawia   się   nam   w
wyszukiwaniu   nowa,   bardzo   interesująca   opcja   –   możliwość     zastosowania   w   algorytmie
wyszukiwania   dodatkowego   kryterium:   wyszukiwanie   po   „najczęstszych   sąsiadach”,   czyli
słowach   bezpośrednio   następujących,   lub   bezpośrednio   poprzedzających   słowo   aktualnie
wyszukiwane   (z   tym,   że   w     przypadku   zastosowania   słów   poprzedzających,   referencje   do
sąsiadów musiałyby być dwukierunkowe). Nie należy oczywiście brak tej opcji pod uwagę jako
jedno   z  głównych kryteriów   wyszukiwania,   raczej  jako   kryterium  dodatkowe,   uzupełniające.
Ważne   byłoby   tutaj   również   odpowiednie   zastosowanie   “wyszukiwania   po   sąsiadach”.   Nie
wszystkie słowa występujące obok siebie są przecież ze sobą powiązane, nie wszystkie pary słów
muszą nieść jakąś wartość dla wyszukiwania. Na pewno należałoby pominąć spójniki, wyrazy
oddzielone znakami przestankowymi, kończącymi zdanie. Być może interesujące byłyby dla nas
jedynie występujące obok siebie rzeczowniki (np. “prezydent Kwaśniewski”, “piłkarz Boniek”,
“system operacyjny”). To  kwestie  do dokładnego zbadania  przed ewentualną  implementacją.
Proponowana struktura  danych oferuje  jednak taką możliwość i sposobów  jej  wykorzystania
może być, jak widać wiele.

2. Asocjacja słowo – wątek

Najczęściej występujący scenariusz związany z wysłaniem wiadomości na grupę dyskusyjną

wygląda następująco:

1. Osoba A wysyła na tematycznej grupie dyskusyjnej wiadomość z opisem problemu lub z

pytaniem, które pragnie ona zadać osobom bardziej kompetentnym

2. Osoba B odpowiada na zadane pytanie, lub też odsyła do innego źródła informacji na temat

poruszony przez osobę A w pierwszym poście

3. Ciąg dalszy może mieć już wiele alternatywnych scenariuszy:

a) Dyskusja rozwija się, pada więcej odpowiedzi, ewentualnie osoba A prosi o kolejne
informacje, informuje o kolejnych problemach związanych ze zgłębianiem tematu
b) Dyskusja podąża innym torem, zmieniając temat

c) Dyskusja kończy się

etc.

Oczywiście jest to tylko przykładowy scenariusz. Zależnie od specyfiki grupy, pierwszy post

może być równie dobrze informacyjny (np. grupy ogłoszeniowe), zachęcający do dyskusji na jakiś
temat   (grupy  polityczne,   światopoglądowe),   etc.   Jednak   wydaje  się,   że   towarem,   którego   zwykle
poszukują  osoby korzystające z wyszukiwarek internetowych, a w szczególności wyszukiwarki grup
dyskusyjnych, są informacje na konkretny temat, czyli tak naprawdę odpowiedzi na pytania, z którymi
nie mogą sobie sami dać rady. Powróćmy więc do powyższego scenariusza, z pytaniem osoby A i
odpowiedzią   osoby   B.   Zakładając,   że   odpowiedź   jest   sensowna,   poprawna   i   na   temat,     bardzo
prawdopodobne   jest,   że   zawiera   ona   również   wiele   słów   kluczowych,   które   może   wpisać   w
wyszukiwarce nasz standardowy użytkownik poszukujący na ten właśnie temat informacji. Czyli –
słowa kluczowe odnośne tematu wątku znajdują się równie dobrze w jego pierwszym jaki i drugim i
być może również kolejnych postach.
Wyobraźmy sobie teraz sytuację, w której osoba wpisuje do wyszukiwarki zapytanie, np. “firewall
konfiguracja   Windows   XP”.     Wyszukiwarka   znajdzie   oczywiście   wszystkie   artykuły,   w   których
wystąpiły   te   właśnie   słowa.   Nie   znajdzie   jednak   artykułów,   w   których   nie   pojawia   się   słowo
“firewall”.   A   taki   może   być   właśnie   pierwszy   post   osoby   próbującej   się   dowiedzieć   jak
skonfigurować   system   Windows   XP,   ale   nie   mającej   o   tym   zielonego   pojęcia   (tym   bardziej   nie
wiedzącej czym może być rzeczony firewall i do czego może on służyć). “Firewall” znajduje się za to
w odpowiedzi na pierwszą wiadomość. Osoba kompetentna wyjaśnia w jaki sposób włączyć zaporę
ogniową w systemie Windows i do czego ona właściwie służy. I tutaj pojawia się właśnie problem.
Ten wątek nie zostanie znaleziony przez wyszukiwarkę, gdyż nie uwzględnia ona zależności między
postami. Zostanie natomiast znaleziony inny artykuł, który wprawdzie zawiera wszystkie wymagane
słowa,   ale   nie   doczekał   się   odpowiedzi.   Problem   jest   więc   nierozwiązany.   A   użytkownik
sfrustrowany.
Aby   zaradzić   takim   sytuacjom   jak   ta   opisana   powyżej,   należy   zastanowić   się,   czy   nie   byłoby
sensowne  zindeksować  nie tylko same artykuły, ale również powiązania między nimi. Chodzi o to,
żeby wyszukiwarka przeszukiwała słowa kluczowe nie tak jak dzieje się to teraz, w pojedynczych
artykułach, ale w całych wątkach, czyli grupach artykułów  dotyczących tego samego zagadnienia.
Problem ten rozwiązać można na dwa sposoby:

1. Kwestię znajdowania słów w całym wątku można pozostawić wyszukiwarce – tzn w

algorytmie wyszukiwania dodać warunek, mówiący o tym, że jeśli znaleziony artykuł ma
dziecko lub rodzica, należy również przeszukać te powiązane z nim artykuły w
poszukiwaniu szukanych słów kluczowych

2. Zająć się problemem już na poziomie indeksowania. Oprócz (zamiast?) tworzenia powiązań

między artykułem a słowami w nim występującymi, tworzyć od razu obiekt wątku
grupującego artykuły i z nim wiązać poszczególne słowa poprzez obiekty pozycji (zobacz
rysunek Powiązanie wątek – słowo).

Największą wadą pierwszej koncepcji jest to, że nie wszystkie artykuły “załapią się” do drugiej

tury, tzn do przeszukania artykułów z nimi powiązanych. Wszystko zależy od tego, jakie kryteria
zostaną przyjęte w znajdowaniu pierwszej grupy artykułów. Odpadną tu najprawdopodobniej wątki,
w których kolejne słowa kluczowe pojawiają się oddzielnie w kolejnych wiadomościach. Drugą wadą
pierwszej koncepcji jest szybkość działania. Jeśli artykuł jest częścią dużego wątku (z zdarzają się
wątki nawet kilkusetpostowe), wyszukiwanie w nim informacji może się niebezpiecznie wydłużyć.
Drugie  rozwiązanie  (schemat przedstawiony  na  rysunku powyżej)  przerzuca odpowiedzialność  na
algorytm indeksowania, dzięki czemu przy wyszukiwaniu  różnica w szybkości będzie praktycznie
niezauważalna.  Słowo  powiązane  będzie  dalej  z listą  pozycji,  tyle  że pozycje  te  tyczyć się  będą
zarówno artykułu jak i całego wątku. Przy założeniu, że rezygnujemy zupełnie z powiązania artykuł –
słowo,  zastosowanie   tego  rozwiązania   nie   odbije   się   w  żaden   sposób   na   wielkości   danych.   Jeśli
będziemy   chcieli  zindeksować  jednocześnie   artykuły   i   wątki,   narzut   pojawi   się,   ale   będzie,
stosunkowo niewielki, więc akceptowalny.

Archiwizacją ściągniętych w ten sposób danych zajmuje się backuper, który przegląda nowe

artykuły   i   umieszcza   je   w   postaci   rekordów   w   relacyjnej   bazie   danych   PostgreSQL.   Kolejnym
krokiem jest migracja danych z relacyjnej bazy do bazy obiektowej. Dopiero artykuły zachowane jako
proste obiekty w bazie Objectivity/DB poddawana są dalszej obróbce.
Parsowaniem  i indeksowaniem zajmuje  się moduł zwany  indekserem.  W ten sposób, z artykułów
składowanych   jako   tekst,   uzyskujemy   obiekty   posiadające   pewną   strukturę,   która   odpowiada
faktycznej strukturze tych artykułów na serwerze grup. Innymi słowy – oddzielamy samą treść posta
od informacji  dodatkowej, takiej  jak data jego wysłania, autor wiadomości, tytuł, czy powiązania
artykułu   z  innymi   artykułami   w  sieci.   Tak   stworzony   nowy  obiekt   zapisywany  jest   na   trwałe   w
docelowej   bazie   danych.   Jest   już   gotowy   do   dalszego   przetwarzania   go,   w   celu   stworzenia
pomocniczej struktury danych, ułatwiającej w przyszłości wyszukiwanie zawartych w nim treści. To
przetwarzanie nazywamy indeksowaniem artykułu, czyli podzieleniem jego treści  na poszczególne
słowa i stworzeniem logicznej struktury tych słów w bazie danych. Zindeksowany artykuł pozostaje
od tej pory na stałe w swoim miejscu w bazie i nie powinien być już więcej modyfikowany. Dopiero
od tej chwili  wyszukiwarka “dowiaduje się” o istnieniu nowego artykułu i bierze go pod uwagę przy
zwracaniu wyników zapytania.
Sama wyszukiwarka jest ważnym, aczkolwiek dość  niewielkim w porównaniu do innych modułem, z
tego względu, że większość skomplikowanych operacji na bazie danych wykonywana jest podczas
indeksowania i optymalizacji. Zadaniem wyszukiwarki jest zwrócenie wyników zapytania zleconego
przez użytkownika, poprzez przeszukanie bazy pod kątem słów użytych w zapytaniu. Przeszukanie to
ogranicza   się   do   przechodzenia   po   referencjach   między  obiektami,   co   zdecydowanie  skraca   czas
oczekiwania na wynik. Każde zapytanie zapisywane jest w bazie, wraz ze zwróconymi wynikami, co
w znacznym stopniu ogranicza marnotrawstwo mocy obliczeniowej, czyli zbyt częste wykonywanie
przez bazę powtarzalnych operacji.
Ostatnią,   ale   wcale   nie   najmniej   istotną   częścią   aplikacji   jest   działający   w   tle   program,   którego
zadaniem jest przeszukiwanie najczęściej pojawiających się zapytań i aktualizowanie ich wyników,
składowanych na stałe w bazie danych. Ze względu na dużą powtarzalność zapytań do bazy, taka
optymalizacja jest niezbędna do utrzymania płynności działania i nie dopuszczania do niepotrzebnego
przeciążania bazy danych.
Opisany powyżej schemat został przedstawiony graficzne na rysunku: Schemat działania aplikacji.

Istotną częścią projektu jest również sam frontend, czyli aplikacja działająca po stronie

przeglądarki internetowej, udostępniająca użytkownikom zindeksowane zasoby polskiego Usenetu.
Implementacja frontendu nie była w projekcie priorytetem, tak więc udostępnia on jedynie formularz
do wpisywania zapytań, stronę z wynikami zapytania oraz możliwość przeglądania całych wątków,
zawierających artykuły, będące wynikami zapytania.

W poniższym rozdziale szczegółowo przedstawiona została struktura danych w postaci opisu

klas, użyte algorytmy oraz sposoby optymalizacji poszczególnych modułów, składających się na
prezentowany system.

5.1.

Opis najważniejszych klas

Zarówno projekt systemu, jak i implementacja została zaplanowana tak, aby wszystkie istotne

elementy systemu miały swoje bezpośrednie odzwierciedlenie w strukturze obiektów. Chodzi o to,
żeby   struktura   danych   w   jak   największym   stopniu   odzwierciedlała   rzeczywistość.   Abstrakcja
obiektowa   pozwala   w   prosty   sposób   zrozumieć   system,   ponieważ   operuje   ona   na   pojęciach
używanych   w   świecie   rzeczywistym.   Przyjrzyjmy   się   więc   najważniejszym   klasom   i   ich
podstawowym metodom.

Klasa Article

Opis:

Klasa reprezentuje pojedynczy artykuł grup dyskusyjnych. Służy do przechowywania

sparsowanych i zindeksowanych artykułów. Tutaj znajdują się właściwe teksty artykułów oraz ich
nagłówki, a także referencje do struktur pomocniczych w algorytmie wyszukiwania, czyli listy pozycji
oraz słów występujących w artykule. Wszystkie statyczne operacje na artykułach realizowane są
również przy użyciu tej właśnie klasy

Zależności z innymi klasami:

●

private

ToManyRelationship words

Relacja ze słowami artykułu. Artykuł może zawierać wiele słów, każde słowo może występować
w wielu artykułach.

●

private

ToManyRelationship positions

Relacja z pozycjami słów w artykule. Pozycje wiążą słowa i artykuły. Każdy artykuł łączy się z
liczbą pozycji równą liczbie słów znajdujących się w temacie i treści artykułu.

●

private

ToManyRelationship children

Relacja z artykułami – dziećmi w wątku, odpowiedziami na dany artykuł.

●

private

ToOneRelationship father

Relacja z ojcem, czyli artykułem, na który ten artykuł jest odpowiedzią.

●

private

ToOneRelationship threadHead

Relacja z pierwszym artykułem wątku.

●

private

ToManyRelationship threadContent

Relacja odwrotna do “threadHead”. Będąc z w pierwszym artykule wątki relacja zwraca
wszystkie artykuły znajdujące się w tym wątku.

Najważniejsze metody:

●

public

static

Article addArticle(String messageId, String text, String type)

Metoda

służy

dodania

artykułu

bazy

danych.

Artykuł

dodawany

jest

jako

obiekt

korzeń,

gdzie

unikalny

identyfikator

obiektu

federacji

składa

się

przedrostka

“

ART_”

oraz

Message_ID

artykułu.

●

private void

parseMessage(String

plain)

Metoda

wywoływana

konstruktora

klasy Article,

służy

sparsowania

tekstu

artykułu

wyodrębnienia

niego:

nagłówków,

które są następnie

reprezentowane

jako

oddzielne

pola

klasy,

- właściwego

tekstu, który będzie w następnej kolejności przekazany do indeksowania

●

public

void

indexArticle()

throws

NoSuchWordException

Metoda

indeksująca

sparsowany

artykuł.

Jest

najważniejsza

metoda

artykule. Rozdziela

ona

treść

artykułu

pojedyncze

słowa

Word

tworzy

dowiązania do

tych

słów

obiekcie

Article.

Jeśli

dane

słowo

nie

występuje

jeszcze

bazie, jest

ono

niej

dodawane. Dla

każdego

kolejnego

słowa

artykule

tworzona

jest

pozycja,

która

odpowiada faktycznej

lokalizacji

danego

słowa

artykule.

Pozycje

wiążą

się

poprzez

relacje (relationships)

zarówno

słowem

jak

artykułem. Po

zakończeniu

tej

metody,

artykuł

powiązany

jest

pozycjami

słowami

tym

samym staje

się

widoczny

dla

silnika

wyszukiwarki.

Klasa Word

Opis:
Klasa reprezentuje pojedyncze słowo lub znak występujący w artykule. Jest powiązana ze

słowem będącym swoją formą podstawową (po kanonizacji leksemu) , jak również ze wszystkimi
słowami o tym samym leksemie, dla których dane słowo jest formą kanoniczną. Klasa odpowiada
również za wszystkie statyczne operacje na obiektach słów, w tym operacje związane ze
znajdowaniem formy kanonicznej słowa oraz operacje na bazie danych.

Zależności z innymi klasami:

●

private

ToManyRelationship articles

Relacja ze artykułami powiązanymi ze słowem, czyli tymi, w których dane słowo występuje.
Artykuł może zawierać wiele słów, każde słowo może występować w wielu artykułach.

●

private

ToManyRelationship positions

Relacja z pozycjami słów w artykule. Pozycje wiążą słowa i artykuły. Każdy artykuł łączy się z
liczbą pozycji równą liczbie słów znajdujących się w temacie i treści artykułu.

●

private

ToManyRelationship allQueries;

Relacja z wynikami wyszukiwania rozpoczynającymi się od tego słowa. Relacja ta jest podstawą
dla mechanizmu prezentowania scache'owanych wyników zapytań.

Najważniejsze metody:

●

public

static

Article addWord(String word_name)

Metoda

służy

dodania

nowego

słowa

bazy

danych.

Słowo

dodawane

jest

jako

obiekt

korzeń,

gdzie

unikalny

identyfikator

obiektu

federacji

składa

się z

przedrostka

WRD_

oraz

nazwy

słowa.

●

public

static

void

scanWordsWithGram(GramUtil gramUtil)

Metoda

skanuje

słowa,

które

nie

zostały

jeszcze

przetworzone

przez

Grama

celu

znalezienia

formy

kanonicznej. Dla

każdego

takiego

słowa,

wywoływana

jest

metoda

findNormalisedForm,

która

ustawia

formę

kanoniczną

dla

znalezionego

słowa

●

public

boolean

findNormalisedForm(GramUtil gramUtil)

Metoda

służy

"zindeksowania"

słowa

Gramem,

tzn

znalezienia

wszystkich

form

podstawowych

(najczęściej

jednej)

stworzeniu

linków

(referencji)

pomiędzy

tymi

słowami.

Mogą

zostać

dodane

nowe

słowa,

jeśli

ich

wcześniej

nie

było

bazie

Klasa

SearchResults

Opis:
Klasa reprezentuje listę wyników zapytania (SearchResult). Tutaj wykonywane są wszystkie

metody operujące  na  wynikach,  jak również same metody dotyczące  poszczególnych algorytmów
wyszukiwania.   Klasa   jest   powiązana   z   klasą   Word,   a   konkretnie   z   pierwszym   słowem   danego
zapytania, w celu umożliwienia prezentacji  scache-owanych  wyników przy powtórnym wykonaniu
tego samego zapytania.

Zależności z innymi klasami:

●

private

ToManyRelationship exactResults;

Relacja z wynikami wyszukiwania zawierającymi dokładny ciąg zapytania.

●

private

ToManyRelationship moreResults;

Relacja z wynikami wyszukiwania zawierającymi podciąg(i) zapytania.

●

private

ToManyRelationship allWordsResults;

Relacja z wynikami wyszukiwania zawierającymi wszystkie słowa z zapytania.

●

private

ToManyRelationship someWordsResults;

Relacja z wynikami wyszukiwania zawierającymi niektóre słowa z zapytania.

●

private

ToOneRelationship word;

Relacja z pierwszym słowem zapytania. Każdy obiekt reprezentujący listę wyników zapytania
jest powiązany z jednym słowem, słowo może być powiązane z wieloma wynikami.

Najważniejsze metody:

●

private

void

parseQuery()

throws

ArticleNotFoundException

Metoda

parsuje

zapytanie

(szukany

ciąg),

dzieląc

na pierwsze

słowo

resztę

(firstWord,

query).

●

private

void

searchExact(Word firstWord)

Algorytm 1: wyszukiwanie ciągów znaków.

●

private

void

findExactResults(Iterator it,

int

currentWordNumber,

int

exactSize)

private

void

findExactResultsWithGram(Iterator it,

int

currentWordNumber,

int

exactSize)

Metoda pomocnicza. Przeszukujemy

wszystkie

pozycje

dla

pierwszego

słowa

kwerendy. Dla

każdej

pozycji

szukamy

kolejnych

pozycji

sprawdzamy czy

tworzą

one

ciąg

jaki

było

zapytanie. Znalezione

dokładne

ciągi

wrzucamy

do listy exactResults,

„

półciągi"

listy

moreResults

(jeśli

zaznaczona

jest

opcja

znajdowania

półciągów).

●

private

long

findExactPhase(WordPosition currentPos,

int

currentWordPosition)

private

long

findExactPhaseWithGram(WordPosition currentPos,

int

currentWordPosition)

Metoda

pomocnicza.

Dla

każdego

znalezionego

artykułu

kolei

pobieramy

słowa

wyszukiwanego

ciągu. Jeśli

znajdzie

się

artykuł,

dokładnie

takim

ciągiem,

dodajemy

listy

exactPhaseArticles.

●

private

void

searchAllWords()

Algorytm 2: wyszukiwanie części wspólnej artykułów

zawierających

wszystkie

lub

niektóre

(minimum jedno)

zapytania.

Klasa SearchResult
Opis:

Klasa reprezentuje pojedynczy wynik zapytania, czyli wskazanie na odpowiednią pozycję,

powiązaną z artykułem, będącym faktycznym wynikiem zapytania. Klasa udostępnia metody służące
do obliczenia wagi artykułu. Elementy tej klasy wchodzą w skład list wyników klasy SearchResults.

Zależności z innymi klasami:

Analogiczne relacje do klasy SearchResults, z tym że typu ToOneRelationship – jeden wynik

wyszukiwania może znajdować się w tylko jeden kolekcji wyników.

Najważniejsze metody:

●

private

void

calculateWeight()

Metoda

wykorzystywana

jest

obliczenia

wagi

rezultatu

zapytania na

podstawie

wcze niej

pobranych

warto ci

takich

jak:

ilość

znalezionych

słów

zapytania

–

ilość

słów

występujących

ciągu

–

pozycje

słów

artykułach

szczególności

pozycja

temacie

artykułu czy

tekście

)

–

rodzaj

znalezionych

słów

(dokładne

szukane

słowa

czy

formy

kanoniczne)

●

public

int

compareTo(Object o)

Metoda porównuje dwa obiekty klasy SearchResult w celu posortowania wyników w zależności
od priorytetu wyświetlania (wagi) kolejnych artykułów.

Klasa NntpArticle

Opis:
Klasa reprezentuje nieprzetworzony artykuł, w stanie zaraz po pobraniu z serwera grup

dyskusyjnych lub relacyjnej bazy danych, gdzie został zarchiwizowany. Klas odpowiada również za
indeksowanie grupy takich artykułów, w czasie którego tworzone są docelowe obiekty klasy Article,
będące sparsowanymi i zindeksowanymi obiektami NntpArticle.

Najważniejsze metody:

●

public

static

void

indexNntpArticles(

long

count)

throws

NoGramException

Jest to główna metoda wywoływana przez indekser. Służy do zindeksowania nowo pobranych
artykułów klasy NntpArticle

poprzez stworzenie ich odpowiedników klasy Article, a następnie

sparsowanie i zindeksowanie ich w oddzielnej bazie danych.

Opisane powyżej główne klasy aplikacji przedstawiono poniżej na poglądowym diagramie klas

w celu przedstawienia zależności między nimi.

Pobrane

posty

umieszczane

są

bazie

jako

obiekty

pl.edu.pjwstk.NewsSearch.NntpArticle.

Backuper – skrypt w języku Python do archiwizacji postów w relacyjnej bazie danych
W trakcie prac nad stworzeniem naszego oprogramowania powstał problem archiwizacji

artykułów grup dyskusyjnych. Nie mając pełnego zaufania od oprogramowania ściągającego posty
grup   dyskusyjnych,   a   także   nie   mając   zaufania   do   sprzętu   (awaria   dysku)   stwierdziliśmy,   że
potrzebujemy   prostego   mechanizmu   archiwizacji.   Najprostszym   rozwiązaniem   jakie   przyszło   do
głowy   była   relacyjna   baza   danych.   Nie   chcieliśmy   za   bardzo   angażować   się   w   tworzenie
skomplikowanych rozwiązań w technologiach, które mało znaliśmy. Dlatego też wybraliśmy bazę
PostgreSQL oraz język Python. Struktura bazy jest bardzo prosta i składa się tylko z dwóch encji:
group_news i message.

Rysunek 19. Struktura relacyjna archiwum grup

dyskusyjnych

Skrypt uruchamiany jest ręcznie a jedynym jego zadaniem jest połączeniem się z lokalnym

serwerem   newsów,   pobranie   listy   grup   dyskusyjnych   a   następnie   dla   każdej   grupy   wczytanie
wszystkich  postów.  Narzędzie to  działa  przyrostowo.  Uruchomione  ponownie   wczyta tylko nowe
posty. Wszystkie operacje bazodanowe odbywają się w transakcjach. Mechanizm skonstruowany jest
tak,   aby   można   było   przerwać   działanie   programu   w   dowolnym   momencie,   bez   ryzyka   utraty
spójności danych. W razie  potrzeby działanie programu może zostać przerwane,  a po ponownym
uruchomieniu program zacznie od ostatnio zapisanych danych.

5.3.

Implementacja indeksowania

Implementacja algorytmu indeksowania wypracowana w projekcie aplikacji i przedstawiona w

rozdziale Opis rozwiązania: Algorytm indeksowania zakładała zamknięcie indeksowania każdego
artykułu w jednym cyklu obejmującym:

–

parsowanie artykułu,

–

tworzenie struktury wątków,

–

tworzenie powiązań między słowami w artykule,

–

analizę fleksyjną.

W praktyce takie rozwiązanie okazało się jednak mało wydajne. Tworzenie struktury wątków,

gdy nie zindeksowane zostały jeszcze wszystkie wiadomości pociąga za sobą komplikacje techniczne
(np. konieczność tworzenia atrap postów – nie zapełnionych danymi obiektów, przechowujących

jedynie   unikalne   Message-ID   i   powiązania   do   artykułów   już   zindeksowanych).   Z   kolei   analiza
fleksyjna wszystkich kolejnych słów w artykule jest niepraktyczna ze względu na zbyt duże ilości
porównań   –   dla   każdego   słowa   w   artykule   należałoby   sprawdzać   czy   nie   zostało   już   ono
zindeksowane. Ponadto, program do analizy fleksyjnej – Gram – z którym komunikacja odbywa się
poprzez standard   CORBA, bywa mało  wydajny,  szczególnie  jeśli   stosujemy go zbyt  intensywnie
podczas   indeksowania.   Dlatego   też,   początkowa   koncepcja   została   nieco   zmodyfikowana   w   celu
zwiększenie efektywności mechanizmu indeksowania. Części odpowiedzialne za tworzenie wątków
oraz analizę fleksyjną zostały przeniesione do oddzielnych podaplikacji, natomiast właściwy algorytm
indeksowania  został  zawężony do  dwóch  najważniejszych  czynności,  czyli  parsowania  artykułu  i
indeksowania sparsowanych danych. W pierwszej kolejności omówimy więc właściwy mechanizm, a
następnie przejdziemy do dwóch wydzielonych modułów.

Właściwy mechanizm indeksowania
Indeksowanie artykułu rozpoczyna się w momencie stworzenia nowego obiektu klasy Article,

w   metodzie  indexArticles()  klasy  NntpArticle.   Metoda   ta   odpowiedzialna   jest   za   indeksowanie
ściągniętych   z   serwera   grup   dyskusyjnych   „surowych”   artykułów,   składających   się   jedynie   z
czystego,   nieprzetworzonego   tekstu.   Przetwarzanie   kolejnych   niezindeksowanych   artykułów
realizowane   jest   w   trzech   krokach.   Najpierw   tworzony   jest   obiekt   artykułu.   Podczas   tworzenia
obiektu   następuje   parsowanie   artykułu,   czyli   wstępna   strukturyzacja   danych   artykułu.   Następnie
artykuł   dodawany  jest  do  bazy danych.  Gdy znajduje   się   już  w  bazie,   wywoływana  jest   metoda
indexArticle()  dodanego obiektu  klasy  Article, tworząca  właściwą  strukturę  powiązań  artykułu  ze
słowami poprzez listę pozycji.

Parsowanie artykułu
Metoda parseMessage odpowiedzialna za parsowanie artykułu wywoływana jest już w

konstruktorze   klasy  Article.   Jej   zadaniem   jest   odseparowanie   nagłówków   wiadomości   od   treści
artykułu i umieszczenie  uzyskanych w ten sposób informacji  w odpowiednich polach klasy. Pola
odpowiadają zazwyczaj nazwom nagłówków wiadomości, zdefiniowanych przez protokół NNTP.
Działanie metody parseMessage  można opisać w następujący sposób:

1. Pobierz treść wiadomości w oryginalnym formacie
2. W pętli pobieraj kolejne linijki wiadomości (oddzielone znakiem końca linii)

3. Sprawdź czy linia nie rozpoczyna się od nazwy nagłówka, jeśli tak pobierz tę nazwę

a) Jeśli mamy nagłówek: sparsuj dane znajdujące się po nagłówki, zależnie od nazwy
nagłówka:

- jeśli nagłówek jest polem typu tekstowego (większość nagłówków) – zapisz wartość pola
do odpowiedniego pola w klasie
- jeśli nagłówek jest polem typu data, parsuj datę wywołując metodą parseDate i następnie
zapisz wartość wynikowego obiektu klasy Timestamp do odpowiedniego pola klasy

b) Jeśli nie mamy nagłówka, oznacza to że linia opisuje nagłówek składający się z kilku
linii, zapisujemy więc całą linię do tymczasowego obiektu i parsujemy dalej

4. Gdy napotkamy ostatni nagłówek, zaczynamy parsować tekst wiadomości – kolejne linie

dodajemy poprzez konkatenację do pola klasy odpowiedzialnego ze przechowywanie
pełnego tekstu wiadomości

Algorytm kończy się po sparsowaniu ostatniej linijki oryginalnej wiadomości. Po wykonaniu

parsowania, w nowym obiekcie klasy Article mamy już zainicjowane wszystkie pola odpowiadające
standardowym nagłówkom wiadomości (a być może również niektóre z niestandardowych
nagłówków) oraz właściwą treść artykułu, w polu text.

Tworzenie powiązań

Gdy mamy już wydzielone wszystkie informacje potrzebne do stworzenia docelowej struktury

danych   na   podstawie   artykułu,   możemy  przejść   do   właściwej   fazy   indeksowania,   polegającej   na
stworzeniu łatwo dostępnej struktury powiązań referencyjnych pomiędzy poszczególnymi obiektami
w bazie danych. Odpowiedzialna jest za to metoda indexArticle klasy Article. Każde ze słów użytych
w artykule zostaje wydzielone i na jego podstawie tworzymy unikalny obiekt klasy Word. Obiekt ten
łączymy   z   artykułem   używając   pomocniczego   obiektu   klasy  WordPosition,   który   przechowuje
referencje   do   słowa   i   artykułu,   jak   również   mówi   nam   o   pozycji   zajmowanej   przez   słowo   w
indeksowanym artykule. W miarę indeksowania tworzy się lista takich pozycji, ponieważ każdy z
obiektów  WordPosition    zawiera   referencje   do   poprzedniej   i   następnej   pozycji   w   artykule.   Ta
struktura będzie później podstawą algorytmu wyszukiwania opartego na wyszukiwaniu identycznych
podciągów słów.
Działanie metody indexArticle możemy opisać poprzez następujący algorytm:

1. Pobieramy właściwy tekst artykułu, który po sparsowaniu znajduje się w polu text

indeksowanego obiektu klasy Article.

2. Pobieramy kolejne słowo z tekstu artykułu – konkretnie pobieramy kolejny napis oddzielony

znakami separującymi, takimi jak tab, spacja, czy znacznik końca linii.

3. Pobieramy z bazy obiekt odpowiadający temu słowu (dokładnie pobieramy obiekt-korzeń o

unikalnym identyfikatorze w postaci: WRD_pobrane_słowo.

4. Jeśli słowo istnieje w bazie (w wyniku pobrania obiektu-korzenia dostaliśmy obiekt klasy

Word), przechodzimy do kroku 6.

5. Jeśli słowa nie ma w bazie, dodajemy słowo do bazy, wykorzystując statyczną metodę klasy

Word addWord i pobieramy stworzony obiekt.

6. Tworzymy powiązanie między obiektem Word (dodanym lub pobranym z bazy) a

indeksowanym artykułem.

7. Tworzymy nowy obiekt klasy WordPosition z ustawionym polem określającym numer tej

pozycji w indeksowanym artykule i dodajemy go do bazy używając metody statycznej klasy
WordPosition: addPosition. Zwrócony obiekt zapisujemy do zmiennej newPosition.

8. Jeśli mamy tymczasową zmienną lastPosition, ustawiamy ją jako poprzednią pozycję nowo

dodanej pozycji newPosition, poprzez stworzenie powiązania między tymi dwoma
obiektami.

9. Przypisujemy nowo dodaną pozycję do artykułu oraz wiążemy ją z odpowiadającym

słowem.

10. Wywołujemy metodę increaseSumPositions na aktualnym obiekcie Word, która powiększa

zmienną przechowującą liczbę pozycji powiązanych z danym słowem.

11. Referencję do obiektu newPosition przepisujemy do tymczasowej zmiennej lastPosition –

przyda się ona przy następnym przejściu pętli.

Schemat działania metody indexArticle został przedstawiony graficznie na rysunku: Diagram

przepływu  dla   funkcji   indeksowania.  Metoda  indexArticle  kończy  swoje   działanie,  gdy powyższy
algorytm zostanie zastosowany dla wszystkich kolejnych słów artykułu. W tym momencie, stworzona
utworzona jest już dla zindeksowanego artykułu podstawowa struktura danych, na której opiera się
aplikacja. Do zrobienia są jednak jeszcze dwie ważne rzeczy, które również mają niebagatelny wpływ
na działanie programu. Chodzi o zindeksowanie tematu oraz próbę wydobycia informacji na temat
autora   dopiero   co   zindeksowanego   artykułu.   Obie   te   informacje   wykorzystywane   są   podczas
wyliczania wagi dla  poszczególnych wyników wyszukiwania. Przyjrzyjmy się więc dokładniej w jaki
sposób uzyskujemy te właśnie informacje.

Analiza fleksyjna słów
Analiza fleksyjna słów odbywa się w całości w metodzie

scanWordsWithGram() klasy Word. Przed

wywo aniem metody, tworzony jest obiekt GramUtil, odpowiedzialny za interakcj  z programem Gram, u ywaj c
protoko u   CORBA.   Analiza   polega   na   przeszukaniu   wszystkich   s ów   bazy,   które   nie   zosta y   jeszcze
zindeksowane   poprzez   Gram.   S

to wszystkie słowa ze znacznikiem

alreadyNormalised = false. Dla

wszystkich takich s ów wywoywana jest metoda findNormalisedForm(), która odpowiada za zaindeksowanie
konkretnego s owa W

. Dzia anie tej metody mo emy opisa poprzez zast puj c y algorytm:

1. Konwertujemy napis słowa tak, aby zawierał tylko małe litery.

2. Przesyłamy powstały w ten sposób napis do metody getNormalisedWord obiektu GramUtil

– metoda zwraca formę lub formy podstawowe indeksowanego słowa w postawi napisu.

3. Jeśli metoda nie zwróciła napisu, lecz wartość null, przechodzimy do punktu 9, w

przeciwnym wypadku idziemy do następnego kroku.

4. Analizujemy zwrócony napis. Może on zawierać jedno lub więcej słów, będących

podstawową formą słowa indeksowanego. W pętli pobieramy kolejne słowa z napisu
(używając do tego klasy Javy: StringTokenizer).

5. Pobieramy kolejne znormalizowane słowo W

z bazy danych (na podstawie zwróconego

napisu).

6. Jeśli słowo istnieje w bazie, przechodzimy do punktu 7, w przeciwnym razie przechodzimy

do następnego punktu.

7. Dodajemy znormalizowane słowo W

do bazy danych.

8. Tworzymy powiązanie między słowem indeksowanym W

a jego znormalizowaną formą W

a) Wywo ujemy

metodę addParent(normalisedWord) na obiekcie indeksowanym W

. Metoda

ta dodaje do tablicy słów będących podstawową formą indeksowanego słowa, nowego
rodzica.

b) Wywołujemy metodę addChild(indexedWord) na obiekcie znormalizowanym W

.Metoda

ta dodaje do tablicy dzieci słowa (słów powiązanych fleksyjnie) słowo indeksowane W

9. Zaznaczmy słowo jako znormalizowane, znacznik: alreadyNormalised = true. Nie będzie

ono brane pod uwagę w kolejnym wywołaniu analizy fleksyjnej.

Jak widać, aby artykuły oraz znajdujące się w nich słowa mogły być rzeczywiście użyteczne dla

algorytmu wyszukiwania danych, potrzebne  jest  wykonanie wielu operacji,  nazwanych tu ogólnie
indeksowaniem   danych.   Nie   wszystkie   z   tych   operacji   muszą   zostać   jednak   wykonane,   aby
wyszukiwanie   miało   szansę   zadziałać.   Już   po   wykonaniu   podstawowego   parsowania   artykułu   i
zindeksowania jego treści, mechanizm wyszukiwania bierze pod uwagę zindeksowane artykuły przy
poszukiwaniu wyników. Im więcej z opisanych powyżej dodatkowych operacji zostanie wykonanych,
tym większa jest jednak szansa, że wyszukiwane rezultaty będą dokładne i trafne, spełniając  tym
samym wymagania potencjalnego użytkownika.

5.4.

Implementacja wyszukiwania

Klasą odpowiedzialną ze działanie mechanizmu wyszukiwania jest SearchResults.

Wyszukiwanie odbywa się poprzez statyczne metody tej klasy. Obiekty klasy SearchResults służą
natomiast do składowania informacji o wynikach wyszukiwania. Obiekty te mogą zostać utrwalone w
bazie danych. W takim przypadku są one wykorzystywane jako cache wyników danego zapytania.
Ponowne wywołanie identycznego zapytania będzie skutkowało prezentacją już raz wyszukanych
wyników.

W pracy zostały zaimplementowane dwa główne mechanizmy wyszukiwania, opisane

wcześniej w rozdziale czwartym, czyli:

–

wyszukiwanie oparte na znajdowaniu dokładnych ciągów podanych w zapytaniu

–

wyszukiwanie części wspólnej wszystkich artykułów zawierających słowa z zapytania

Oba algorytmy dzielą się na mniejsze funkcje, odpowiedzialne za znajdowanie konkretnej

informacji. W obu algorytmach zaimplementowane jest dodatkowo wyszukiwanie z analizą fleksyjną.
Wykorzystywana   jest   do   tego   struktura   powiązań   fleksyjnych   pomiędzy  słowami,   wygenerowana
podczas   indeksowania,   dzięki   zastosowaniu   programu   Neurosoft   Gram.   Oprócz   tego,   na
implementację wyszukiwania  składa się również składowanie wyników zapytań w bazie danych, w
strukturze   umożliwiającej   pobranie   ich   i   wyświetlenie   przy   ponownym   wywołaniu   identycznego
zapytania.   W   tym   podrozdziale   przyjrzymy   się   dokładnej   implementacji   obu   mechanizmów
wyszukiwania, jak również zastosowanej w aplikacji metodzie cache'owania wyników zapytań.

Wyszukiwanie metodą znajdowania wspólnych ciągów słów

Pierwszą omawianą implementacją wyszukiwania jest metoda znajdowania wspólnych z

zapytaniem podciągów słów. Algorytm ten jest podzielony na kilka niezależnych funkcji. Wykonanie
każdej z tych funkcji zależy od ustawionych parametrów zapytania, które zaimplementowane są jako
boolean'owskie pola klasy SearchResults. Parametry te uwzględniają takie sprawy jak:

–

czy poszukiwać w artykułach dokładnych ciągów słów, równoznacznych z podanym zapytaniem?

–

czy poszukiwać również podciągów (ciągów nie zawierających wszystkich kolejnych słów
zapytania, lecz zawierających co najmniej dwa słowa)

–

czy w wyszukiwać bez względu na fleksję wyrazów (czyli – czy korzystać ze stworzonej podczas
indeksowania struktury zależności fleksyjnych między słowami)

–

czy pominąć scache'owane wyniki zapytania – gdy atrybut ma wartość prawda, nie jest brana pod
uwagę struktura wygenerowana podczas historycznych zapytań, znalezione wyniki są więc zawsze
aktualne, czas wykonywania operacji jest jednak znacznie dłuższy

–

czy pominąć powszechne słowa – gdy ta opcja jest zaznaczona pomijane są słowa, które występują
w zdefiniowanej wcześniej części wszystkich artykułów (np. w 20 procentach artykułów) –
znajdowane ciągi nie są w tym wypadku identyczne z zapytaniem, operacja wykonuje się jednak
znacznie szybciej, gdyż nie ma potrzeby przeglądania wszystkich artykułów powiązanych z bardzo
popularnymi słowami

Dwa ostatnie parametry odnoszą się również do drugiego sposobu wyszukiwania. Standardowo

zaznaczone są wszystkie opcje oprócz pomijania wyników z cache.

–

pozycja dodawana jest do listy dokładnych wyników (gdy znaleziono całkowity ciąg,
identyczny z zapytaniem),

–

do listy podciągów (gdy znaleziono podciąg co najmniej dwóch słów),

–

lub ignorowana (gdy nie znaleziono podciągu).

Identyczny mechanizm stosowany jest dla kolejnych słów zapytania, z tym że przy kolejnych

słowach, możliwe jest już tylko dodanie pozycji do listy podciągów. Dla wyszukiwania z
uwzględnieniem fleksji, oprócz zwykłego porównania słów z zapytania i z artykułu, porównywane są
również wszystkie możliwe formy słowa z zapytania.

Wyszukiwanie metodą znajdowania części wspólnej artykułów

Wyszukiwanie tą metodą charakteryzuje się jednakowym podejściem do wszystkich słów

zapytania   użytkownika   –   kolejność   słów   nie   jest   dla   nas   w   tym   przypadku   istotna.  Istotne   jest
natomiast znalezienie artykułów zawierających jak największą liczbę znajdujących się w zapytaniu
słów.   Sam   algorytm   znajdowania   artykułów   jest   bardzo   prosty   i   sprowadza   się   do   pobrania
wszystkich artykułów związanych z poszczególnymi słowami zapytania. Ciekawszy jest sposób, w
jaki tworzymy na podstawie pobranych list artykułów, docelową listę wyników zapytani.
Zaraz po wywołaniu metody searchAllWords klasy SearchResults, odpowiedzialnej za wyszukiwanie
metodą znajdowania części wspólnej, tworzona jest tymczasowa struktura wyników, w postaci tablicy
haszowanych   zbiorów  (HashSet[]  allFoundResults)  artykułów.   Każda   pozycja   tablicy   odpowiada
zbiorowi   artykułów   dla   każdego   kolejnego   słowa   zapytania.   Po   wykonaniu   pierwszej   fazy
wyszukiwania,   cała   tablica   zbiorów   powinna   być   wypełniona   artykułami.   W   tym   momencie
przechodzimy   do   drugiej   fazy   algorytmu,   tj.   wyodrębniania   z   tablicy   zbiorów   konkretnej   listy
wyników.

Algorytm wyodrębniania listy dokładnych wyników polega na wykonywaniu w pętli operacji

intersekcji kolejnych zbiorów. Możemy go zapisać w postaci następujących kroków:

1. Tworzymy nowy zbiór HashSet allInOne

2. Inicjujemy zbiór wartościami pierwszego elementu tablicy zbiorów wyników: allInOne :=

allFoundResults[1]

3. Dla każdego kolejnego zbioru od 2 do ostatniego elementu tablicy wyników (

allFoundResults.length) wykonujemy operację intersekcji ze zbiorem allInOne.

Po wykonaniu tej operacji, w zbiorze allInOne znajdują się tylko artykuły zawierające

wszystkie słowa analizowanego przez nas zapytania. Ostatnią rzeczą jaką musimy zrobić jest
stworzenie listy obiektów klasy SearchResult zawierających artykuły ze zbioru allInOne. Dla każdego
obiektu ustawiamy zmienną allFoundResults na true – jest to zmienna brana pod uwagę przy
wyliczaniu wagi dla wyników zapytania.

W podobny sposób możemy wyodrębnić listy niedokładnych wyników zapytania,

zawierających   jedno   lub   więcej   słów   kluczowych   podanych   w   zapytaniu   użytkownika.   Gdy   w
wynikach zapytania mają się pojawić również artykuły zawierające  tylko część słów podanych w
zapytaniu, możemy jednak zrezygnować z opisanego wyżej mechanizmu i zastosować uniwersalny
algorytm.   Algorytm   ten   również   polega   na   tablicy   zbiorów  allFoundResults,   z   tym   że   w   tym
przypadku  zastosujemy tymczasową,  dwuwymiarową  tablicę  haszowaną,  do grupowania  wyników
zapytania. Kluczami w tej tablicy będą artykuły, będące wynikami wyszukiwania wszystkich słów
zapytania (ewentualnie z uwzględnieniem analizy fleksyjnej). Wartościami tablicy haszowanej będą
natomiast tablice  o rozmiarze równym ilości słów zapytania. W każdym kolejnym polu tablicy dla
konkretnego artykułu, trzymać będziemy liczbę oznaczającą ilość wystąpień odpowiedniego słowa

zapytania   w   tym   artykule.   Dla   słów   pominiętych   tablice   te   nie   będą   zainicjowane.   Algorytm
wyodrębnienia   wyników   polegać   będzie   zatem  na   uzupełnieniu   wartości   zainicjowanej   tablicy,   a
następnie na jej podstawie utworzenie dwóch list wyników: dla artykułów zawierających wszystkie
słowa   zapytania   i   dla   tych   zawierających   tylko   niektóre   ze   słów.   Algorytm   ten   możemy   więc
przedstawić za pomocą następujących kroków:

1. Konstruujemy haszowaną tablicę

groupedArticles

2. W pętli pobieramy listy artykułów powiązanych z kolejnymi słowami zapytania i

do i

3. Dla każdej listy tworzymy iterator i w pętli pobieramy kolejne artykuły
4. Dla każdego pobranego artykułu:

Sprawdzamy czy występuje już jako klucz w tymczasowej tablicy haszowanej

groupedArticles

a) je li tak, zwi kszamy warto

na aktualnej pozycji

i o jeden (kolejne słowo występujące w

artykule)

jeśli nie, dodajemy do tablicy nowy element z artykułem jako kluczem oraz inicjujemy

wartość klucza jako pustą tabelę o rozmiarze równym ilości słów zapytania i ustawiamy na
pozycji i tablicy wartość 1 (pierwsze słowo w artykule)

5. Kończymy obie pętle
6. Iterujemy kolejne artykuły w nowo powstałej tymczasowej haszowanej tablicy

7. Dla każdego artykułu tworzymy obiekt SearchResult – wynik wyszukiwania i inicjujemy

jego wartości: foundWords, foundDistinctWords i allWordsFound

8. W zależności czy zostały znalezione wszystkie słowa zapytania, czy tylko niektóre,

dodajemy obiekt do listy allWordsResults lub someWordsResults obiektu SearchResults

Obliczanie wagi wyników zapytania

Ostatnią fazą algorytmu wyszukiwania jest nadawanie wagi poszczególnym wynikom oraz

ostateczne posortowanie wyników przed wyświetleniem na ekranie.
Przed nadaniem wag, zebrane wyniki ze wszystkich rodzajów wyszukiwania kopiowane do
tymczasowej kolekcji o rozmiarze równym ilości wszystkich wyników wyszukiwania. Następnie dla
każdego wyniku (obiektu klasy SearchResult) wykonywana jest metoda calculateWeight(),
odpowiedzialna za wyliczenie wagi wyniku na podstawie zebranych wcześniej parametrów. Waga
obliczana jest na podstawie następujących parametrów, zebranych wcześniej podczas wykonywania
algorytmów wyszukiwania:

–

ilość kolejnych słów zapytania w artykule wynikowym

–

ilość znalezionych, unikalnych słów zapytania w artykule (maksymalnie równa liczbie
wszystkich niepominiętych słów zapytania)

–

sumaryczna ilość wszystkich słów zapytania występujących w artykule wynikowym (z
powtórzeniami)

–

czy znaleziono dokładny ciąg?

–

czy znaleziono wszystkie słowa zapytania?

–

sumaryczna różnica odległości między słowami zapytania, w znalezionym artykule

Algorytm wyliczania wagi na podstawie powyższych parametrów przedstawia się więc

następująco:

1. Jeśli w wyniku występują podciągi słów z zapytania:

a) dla pierwszych dwóch słów zwiększamy wagę o stałą

WEIGHT_CONSECUTIVE_WORD

(domyślnie 2 punkty)

b) dla każdego kolejnego słowa w ciągu, ale maksymalnie dla ilości słów równej ilości słów
zapytania, zwiększamy wagę iloczyn stałej

WEIGHT_CONSECUTIVE_WORD

i pozycji słowa

w ciągu
c) dla pozostałych słów (dodatkowe znalezione ciągi) zwiększamy wagę o ½ stałej

WEIGHT_CONSECUTIVE_WORD

2. Jeśli w artykule występuje ciąg identyczny z zapytaniem, dodajemy do wagi bonus za

dokładny wynik w wysokości stałej

WEIGHT_CONSECUTIVE_WORD

(domyślnie 10

punktów). Premia ta występuje tylko raz, tzn jeśli dokładny ciąg występuje w artykule
wielokrotnie, traktowany jest standardowo.

3. Dla każdego unikalnego słowa zapytania znalezionego w artykule zwiększamy wagę o stałą

równą

WEIGHT_DISTINCT_WORD

(domyślnie 1 punkt)

4. Dla każdego kolejnego wystąpienia jednego ze słów zapytania, zwiększamy wagę o stałą

równą

WEIGHT_ADDITIONAL_WORD

(domyślnie 0.05 punktu)

5. Jeśli sumaryczna różnica wszystkich pozycji na których występują znalezione słowa w

artykule jest mniejsza od podwojonej ilości tych słów (innymi słowy – jeśli interesujące nas
słowa znajdują się maksymalnie w odstępach co dwa słowa w artykule), mnożymy
otrzymaną ilość punktów za wystąpienia słów przez wyliczony współczynnik zależności.
Maksymalnie jest to 10 punktów, gdy słowa znajdują się w ciągu (niekoniecznie takim jak
zapytanie). Im większe odstępy tym mniejszy współczynnik.

6. Każde znalezione słowo występujące w temacie artykułu dostaje automatycznie wagę dwa

razy większą niż standardowo.

Po wykonaniu tych operacji, w kolekcji wyników znajdują się artykuły z obliczonymi wagami,

gotowe   do  sortowania.   Operacja  sortowania   jest  to  standardowa  operacja   do   sortowania  kolekcji
oferowana  prze Javę (klasa Collections, metoda sort), wykorzystująca  metodą  compareTo(Object)
zdefiniowaną   dla   klasy   SearchResult.   Posortowane   wyniki   wrzucane   są   do   tablicy   sortedResults
obiektu SearchResults i prezentowane są na ekranie w kolejności od najbardziej do najmniej trafnych.

Implementacja cache'owania wyników
Aby przyspieszyć wykonywanie powtarzalnych operacji – w szczególności aby nie trzeba było

wyliczać powtórnie wyników dla identycznych zapytań, powstał mechanizm cache'owania wyników –
czyli przechowywania raz wyliczonych wyników zapytania w łatwo dostępnym miejscu, gotowych do
pobrania przy kolejnym wystąpieniu podobnego zapytania.

System cache'owania wyników zapytań polega na utrwalaniu w bazie obiektów klasy

SearchResults,   zawierających   kolekcje   obiektów   klasy  SearchResult,   przechowujących   artykuły
będące   wynikami   zadanego   zapytania.   W   celu   optymalizacji   dostępu   do   wyników,   klasa
SearchResults powiązana jest poprzez zależność jeden do wielu z klasą Word. W praktyce oznacza to,
że   każde   ze   słów   posiada   łatwo   dostępną   informację   o   wszystkich   zapytaniach   i   ich   wynikach,
zaczynających   się   właśnie   od   tego   słowa.   Dzięki   temu,   w   początkowej   fazie   analizy   zapytania,
możemy łatwo sprawdzić, czy dane zapytanie zostało już kiedyś wykonane i jeśli tak, zaprezentować
od   razu   listę   wyników,   bez   wykonywania   skomplikowanego   i   zasobochłonnego   algorytmu

6. Problemy związane z zastosowanym rozwiązaniem

Rozdział ten zawiera omówienie trudności przy realizacji pracy, zalet i wad przyjętego

rozwiązania. Jest tu również mowa o potencjalnych zastosowaniach pracy oraz planach rozwojowych
w zakresie tematu pracy i dalszych prac, które należałoby wykonać w przyszłości w celu rozwoju
(zwiększenie efektywności, dodanie nowej funkcjonalności) i pielęgnacji prezentowanego
rozwiązania.

6.1.

Problemy napotkane podczas implementacji

Podczas implementacji napotkaliśmy na bardzo wiele problemów, głównie natury technicznej.

Część z nich była nawet w pewnym momencie zagrożeniem dla powodzenia całego projektu, gdyż
blokowała możliwość dalszego rozwoju prac nad konkretnym zagadnieniem. Problemy te można
podzielić na trzy zasadnicze grupy:

–

Problemy wynikające z naszej niewiedzy lub braku doświadczenia w konkretnej dziedzinie.
Znaczna część pracy powstała w nowej dla nas technologii, w związku z tym sporo problemów
wynikło z niedostatecznego przestudiowania dokumentacji, czy nieznajomości specyfiki danego
produktu.

–

Problemy związane z niedoskonałością lub nieadekwatnością zastosowanych narzędzi, w tym
bibliotek – głównie problemy wydajnościowe przy bardzo dużych ilościach przetwarzanych
danych.

–

Problemy związane z błędami w oprogramowaniu.

Większość problemów, na jakie napotkaliśmy udało nam się rozwiązać samodzielnie, poprzez

studiowanie dokumentacji, szukanie informacji w sieci Internet, na grupach dyskusyjnych, czy też na
specjalistycznych kanałach IRC. W kwestiach związanych z Objectivity wielką pomocą okazał się
support ze strony firmy, w osobie pana Roberta Cheong'a. W tym podrozdziale opisane zostaną
najciekawsze problemy, na które natrafiliśmy podczas prac nad projektem. Problemy pogrupowane
zostały ze względu na moduły, których dotyczą.

Fetcher i backuper:

–

Brak bibliotek w Javie obsługujących protokół NNTP.

Początkowo korzystaliśmy z biblioteki gnu.inet.nntp jednak okazało się, że nie dość że jest
powolna to potrafi zawiesić się w trakcie działania. Rozwiązaniem okazało się stworzenie własnej
prostej biblioteki. Zaimplementowane zostały tylko niezbędne do działania komendy.

–

Duża ilość danych

W momencie pisania pracy na lokalnym serwerze newsów znajduje się około 11GB postów.
Przeniesienie takiego zbioru danych do obiektowej bazy danych poprzez protokół NNTP zajmuje
klika dni pracy bez przerwy. Jakiekolwiek zmiany w strukturze obiektów mogą wymusić ponowne
załadowanie całego zbioru.

–

Mechanizm ściągający posty z serwera internetowego. Lokany serwer newsów pobiera wszystkie
posty z serwera news://news.task.gda.pl. Proces ściągania uruchamiany jest codziennie
w nocy. Obecnie proces ten trwa ok 22 godzin. W niedługiej przyszłości zadanie to przekroczy 24
godziny. Nie jesteśmy pewni jakie konsekwencje może to spowodować. Prawdopodobnie trzeba
będzie przestawić mechanizm tak, aby uruchamiał się co dwa dni. Rozwiązaniem problemu może
być przeniesienie lokalnego serwera newsów na bardziej wydajną maszynę. W tej chwili jest to
Intel Celeron 333Mhz 64RAM z 120GB dysku twardego.

Indekser:

–

Brak możliwości stworzenia relacji wiele-do-wiele pomiędzy obiektami tej samej klasy

Przy implementacji zależności fleksyjnych pomiędzy słowami okazało się, że każde słowo może
być powiązane nie tylko z wieloma słowami, dla których jest ono formą podstawową (z dziećmi),
lecz  również  samo posiadać  może  wiele  form podstawowych  (np.  w przypadku  słów  o wielu
znaczeniach). W takiej sytuacji niezbędnym okazało się zamodelowanie wewnętrznego powiązani
typu wiele-do-wiele pomiędzy obiektami klasy Word. To niestety okazało się niemożliwe, stosując
standardowy mechanizm  relationships  oferowany przez Objectivity. Kod wprawdzie wykonywał
się i nie powodował wyrzucania wyjątków, jednak przy pierwszej operacji zapisu obiektu takiej
klasy,   występował   błąd   natywnej   biblioteki   używanej   prze   Objectivity/DB,   powodujący
zakończenie działania aplikacji.
Pierwszym   rozwiązaniem,   które   zastosowaliśmy   w   celu   ominięcia   tego   problemu   było
zrezygnowanie   z   relacji   i   użycie   dwóch   kolekcji   (ojców   i   dzieci)   reprezentowanych   przez
oferowane przez Objectivity struktury danych jak mapy i drzewa. To również okazało się niestety
nie najlepszym pomysłem, z powodu, że każda kolekcja tworzyła dodatkowy kontener w bazie
danych.  Liczba   takich   kontenerów   jest   ograniczona   i   wyczerpuje   się   po   zindeksowaniu  około
10,000 słów.
Ostatecznie  zdecydowaliśmy się  więc  na  zastosowanie  asocjacji  w postaci  tradycyjnych  tablic
obiektów   (ojców   i   dzieci).   Przy   każdorazowym   dodaniu   nowego   powiązanego   słowa,   tablica
wymaga   przebudowania   (alokacji   nowego   miejsca   w   pamięci   i   skopiowania   zawartości   starej
tablicy). Jest to jednak rozwiązanie bezpieczne i przy niedużej ilości powiązań dla pojedynczego
słowa (maksymalnie pojawia się do 50 dzieci i do 5 ojców) sprawdza się znakomicie.

–

Brak możliwości przeprowadzania wielkich transakcji (z kilkoma tysiącami operacji) ze względu
na ograniczenie pamięci RAM
Początkowo   indeksowanie   (zarówno   artykułów   jak   i   słów   do   analizy   fleksyjnej)
przeprowadzaliśmy w bardzo dużych transakcjach. Wynikało to z tego, że standardowy iterator
obiektów   dostarczony   przez   Objectivity   może   działać   tylko   obrębie   jednej   transakcji.   Po
zatwierdzeniu,   stan   iteratora   jest   zerowany   i   nie   ma   możliwości   pobrania   niezindeksowanych
jeszcze obiektów. Niestety, tak duże transakcje powodowały po zindeksowaniu kilkunastu tysięcy
artykułów   błąd   wirtualnej   maszyny   Javy   polegający   na   braku   pamięci   RAM   do   wykonania
kolejnych operacji.

Rozwiązanie problemu polegało na podziale operacji indeksowania na mniejsze transakcje (np.
zatwierdzenie   transakcji   i   rozpoczęcie   nowej   co   500   artykułów).   Każdy   ze   zindeksowanych
artykułów (lub słów, w przypadku analizy fleksyjnej)  zostawał zaznaczony jako przetworzony.
Iterator tworzony jest od nowa po każdym zatwierdzeniu operacji w bazie, ale bierze pod uwagę
tylko   te   obiekty,   które   nie   zostały   już   wcześniej   przetworzone   przez   indekser   (skanowanie   z
atrybutem).   W   ten   sposób   indeksowanie   może   przebiegać   bez   ingerencji   i   nie   powoduje
nadmiernego zużywania pamięci RAM.

Wyszukiwarka:

–

Przy pracach nad mechanizmem wyszukiwania zauważyliśmy, że niektóre zapytania wykonują się
znacznie dłużej niż inne, mimo że liczba słów użytych w zapytaniu, czy nawet same słowa są
identyczne. Po analizie okazało się, że problem występuje, gdy pierwszym słowem zapytania jest
słowo bardzo popularne, powiązane z dużą ilością artykułów (czy nawet z większością z nich).
Takie słowa to na przykład niektóre zaimki, przyimki, partykuły. Omijania słów występujących
zbyt często (zbyt wiele powiązań z artykułami, co w znaczny sposób pogarszało wydajność
wyszukiwania) okazało się konieczne. Takie rozwiązanie niestety powodowało zmniejszenie

skuteczności samego wyszukiwania ciągów – gdy pierwszym słowem ciągu jest wyraz popularny,
ciąg   taki   nie   zostanie   nigdy   znaleziony,   ponieważ   pierwsze   słowu   musi   zostać   pominięte.
Rozwiązaniem   tego   problemu   okazało   się   sprawdzanie   najpierw   rzadszych   słów   a   następnie
nawigacja po referencjach w obie strony (a nie tylko w jedną, jak w standardowym wyszukiwaniu
ciągów)  w celu  znalezienia   dokładnego ciągu  występującego  w  zapytaniu.  Wydajność  takiego
wyszukiwania jest znacznie większa, a nie pociąga za sobą żadnych ograniczeń funkcjonalnych.
Problem został więc rozwiązany pomyślnie.

Frontend:

–

Konfiguracja serwera aplikacji Jakarta-Tomcat 4.0, aby współgrał z bazą Objectivity/DB

Początkowo nie udawało nam się uzyskać dostępu do bazy danych z artykułami poprzez interfejs
internetowy. Problemem okazał się standardowy poziom bezpieczeństwa Tomcata, który zabrania
wykonywania   kodu   zawierającego   odniesienia   do   natywnych   bibliotek   spoza   Javy.   Takiej
biblioteki   używa   właśnie   Objectivity.   Przy   każdym   uruchomieniu   strony   JSP,   przy   próbie
odwołania   się   do   federacji   wyrzucany   był  SecurityException   –  wyjątek   wskazujący   na   próbę
wywołania niechcianego kodu spoza aplikacji.
Rozwiązanie tego problemu sprowadziło się do rezygnacji z usługi SecurityManager oferowanego
przez Tomcat, poprzez zaznaczenie w pliku konfiguracyjnym /etc/default/tomcat4 opcji:

# Use the Java security manager? (yes/no, default: yes)
TOMCAT4_SECURITY=no

Ogólne problemy z administracją bazą danych Objectivity/DB:

–

Problemy z ewolucją schematu

W trakcie prac bardzo często występowała potrzeba zmiany schematu bazy danych (zmiany takie
implikują np. dodanie nowych metod w klasach trwałych, czy zmiana nazewnictwa pól). Problem z
ewolucją schematu jest taki, że każda zmiana w bazie powinna być przeprowadzona jednocześnie
w   obu   kopiach   bazy,   jeśli   chcemy   zachować   przenaszalność.   W   pierwszej   fazie   projektu   nie
przykładaliśmy do tej kwestii większej wagi, co spowodowało w efekcie całkowita niespójność
pomiędzy używanymi przez nas instancjami baz danych. Rozwiązaniem był do pewnego momentu
mechanizm   uaktualniania   schematu   poprzez   narzędzia  ooschemadump  i  ooschemaupgrade.
Niestety mechanizm ten zawiódł, gdy w grę wchodziła  nie tylko synchronizacja  schematu, ale
również synchronizacja samych danych

–

Trudności z importem danych między dwoma stacjami roboczymi

W pewnym momencie podczas pracy nad projektem zaszła potrzeba importu całej bazy danych,
zawierającej ściągnięte z serwera artykuły (obiekty NntpArticle) z jednej federacji do drugiej.
Problemu nie udało się rozwiązać w bezpośredni sposób. Bazy danych w Objectivity nie mogą być
przenoszone z jednej federacji do drugiej bez zachowania pewnych zasad dotyczących między
innymi rejestrowania klas. Na wprowadzanie tych zasad było już w projekcie jednak za późno.
Problem został więc rozwiązany połowicznie, poprzez zastosowanie programu ooinstallfd, do
kopiowania całych federacji.

6.2.

Wady i zalety przyjętego rozwiązania

Wady:

–

Słaba przenaszalność (Objectivity). Oprogramowanie nasze jest bardzo ściśle związane z
systemem Objectivity/DB. Próba przeniesienia systemu na inną bazę danych (obiektową lub
relacyjną) oznaczała by de facto zaprogramowanie całej aplikacji od nowa. Wszystkie operacje są
bardzo zszyte z zasadą działania i budową Objectivity/DB. Kolejnym problemem przy migracji na
inny system bazodanowy jest przeniesienie danych. Obecnie chyba żadna obiektowa baza danych
nie oferuje możliwości zrzutu danych do formatu rozpoznawalnego przez inne produkty. W celu
przeniesienia danych na inny system należałoby stworzyć specjalne programy zapisujące dane do
pliku o ściśle określonym formacie rozumianym przez inne systemy bazodanowe.

–

Słaba rozszerzalność – zapytania są zaszyte w kodzie, jeśli chcielibyśmy otrzymać dodatkowe
informacje (np. dodatkowe raporty, wyszukiwanie w oparciu o inny algorytm, o inne dane)
najprawdopodobniej niezbędna byłaby modyfikacja kodu aplikacji

–

“Ręczna” optymalizacja zapytań – niekoniecznie wada (plusem jest szybkość, minusem
nieuniwersalność rozwiązania)

–

Skalowalność. Nie wiadomo jak mechanizm indeksujący i wyszukujący zachowa się przy bardzo
dużych zbiorach danych. Archiwum polskich grup dyskusyjnych z całego roku przed
zindeksowanie zajmuje około 12GB przestrzeni na dysku. Po indeksowaniu może powstać baza 10
lub więcej razy większa. Tak obszerne zbiory danych powodują konieczność zastosowania
klastrów serwerów. W chwili obecnej nasze oprogramowanie nie jest przystosowane do działania
na kilku maszynach jednocześnie w trybie rozkładania obciążenia na mniej zajęte maszyny.

–

Uzależnienie się od GRAM-a. Bez tego oprogramowania nasz system jest zwyczajną
wyszukiwarką działającą na zasadzie indeksu.

Zalety:

–

Szybkość działania. Porównując szybkość pobierania artykułu z PostgreSQL dla danego Message-
ID z pobieraniem tego samego artykułu z Objectivity/DB widać było znaczącą różnice w prędkości
działania na korzyść obiektowej bazy danych.

–

Łatwiejsza implementacja. Praca została zaprogramowana w jednym języku – Java. W przypadku
skorzystania   z   relacyjnej   bazy   danych   należałyby   stworzyć   zapytania   SQL-owe   oraz
zaprogramować   całe   “sklejenie”   Javy   ze   strukturą   w   bazie   danych.   Mapowanie   obiektów   na
struktury   relacyjne   jest   kosztowne   i   w   znaczny   sposób   komplikuje   kod   programu   utrudniając
zrozumienie jego koncepcji.

–

Przejrzystość implementacji – obiektowe podejście do projektowania i programowania w znaczny
sposób ułatwia zrozumienie koncepcji aplikacji poprzez odwoływanie się do bardziej
zrozumiałych abstrakcji.

–

Dobra integracja danych trwałych i nietrwałych – cecha wynikająca z zastosowania bazy
obiektowej. Operacje na obiektach trwałych i nietrwałych wykonywane są w ten sam sposób.
Zaoszczędza to pracy programistycznej i wpływa pozytywnie na przejrzystość kodu aplikacji.

–

Duże możliwości optymalizacyjne, w tym rozproszenie bazy danych, stworzenie klastra. Baza
Objectivity/DB reklamowana jest jako największa obecnie baza na świecie. Akcelerator cząstek w
Stanford korzysta z bazy rozproszonej na 100 serwerów linuksowych, przechowujących w sumie
895 terabajtów danych (stan na 16.06.2004). Spodziewamy się że przy rozłożeniu naszej bazy
zindeksowanych artykułów na kilka serwerów wzrosłaby wydajność systemu bez ingerencji w kod.
System Objectivity/DB jest przystosowany do działania głównie w rozproszeniu.

6.3.

Zastosowanie pracy

Główne zastosowanie naszej pracy to oczywiście znajdowanie dokładnej informacji w

archiwum polskich grup dyskusyjnych.

W chwili obecnej nie istnieją w Internecie wyszukiwarki grup dyskusyjnych uwzględniające

specyfikę języka polskiego. Najpopularniejszym narzędziem służącym do przeszukiwania Usenetu
jest mechanizm Google. Opiera się on prostym indeksie słów. Znajduje tylko te słowa, które zostały
wpisane jako zapytanie. Nie znajduje artykułów, które zawierają lekko odmienione formy szukanych
słów.

Celem naszej pracy była realizacja ciekawego pomysłu zbudowania wyszukiwarki opartej na

obiektowej bazie danych. W Internecie jest mnóstwo mechanizmów wyszukujących strony WWW,
dlatego skupiliśmy się na obszarze słabo zagospodarowanym pod tym względem. Możemy pokusić się
o stwierdzenie, że nasza praca jest pod tym względem dość wyjątkowa. Nie słyszeliśmy do tej pory o
polskiej wyszukiwarce grup dyskusyjnych, a tym bardziej o mechanizmie opartym na obiektowej
bazie danych, wykorzystującym analizę fleksji języka polskiego.

Od początku nasze narzędzie budowane było z myślą o typowej wyszukiwarce udostępnianej

przez WWW. Standardowym scenariuszem wykorzystania takiego mechanizmu jest wpisanie
zapytania w postaci szukanych słów i przejście na stronę wyników, gdzie prezentowana jest lista
znalezionych artykułów posortowanych według trafności. Niestety z braku możliwości wyszukiwarka
nasza prawdopodobnie nie będzie udostępniona publicznie. W warunkach rzeczywistych możemy się
spodziewać sporego ruchu generowanego na serwerze. W celu uruchomienia produkcyjnego serwera
należałoby pomyśleć o zapewnieniu stabilności przy dużym obciążeniu oraz o solidnym
przetestowaniu oprogramowania pod względem wydajności.

Przy drobnych modyfikacjach w kodzie można jednak we względnie krótkim czasie dostosować

nasz mechanizm do indeksowania i wyszukiwania innych zbiorów danych takich jak:

•

zasoby intranetowe

•

strony WWW (ogólnie)

•

specyficzne strony WWW – np. fora dyskusyjne lub blogi

6.4.

Plany na przyszłość

Mimo, że prezentowane rozwiązanie jest kompletne, zarówno pod względem koncepcji jak i

implementacji, to  w dalszym ciągu istnieje bardzo wiele sposobów, dzięki którym możliwe będzie w
przyszłości   znaczne     polepszenie   jego   wydajności   i   być   może   również   funkcjonalności.   Warto
zwrócić uwagę, że przy projektowaniu i wdrożeniu omawianego systemu pojawiały się dość często
komplikacje   natury   czysto   technicznej   –   problemy   związane   z   niedoborem   zasobów,   takich   jak
miejsce na dysku twardym, czy mała ilość pamięci RAM. Biorąc pod uwagę te czynniki, aplikacja
została   zaprojektowana   w   ten   sposób,   by   działać   wydajnie   na   komputerze   osobistym.   Jest   to
oczywiste   ograniczenie.   Programy   tego   typu   działają   zazwyczaj   w   oparciu   o   ogromne   sieci
połączonych   ze   sobą   maszyn.   To   pozwala   na   znacznie   większą   swobodę,   zarówno   w   kwestii
złożoności   obliczeń,   jak   i   w   planowaniu   fizycznej   struktury   danych   (np.   możliwość   masowego
stosowania redundancji w celu optymalizacji działania, etc). Nic nie stoi jednak na przeszkodzie, aby
na podstawie aktualnego rozwiązania stworzyć aplikację komercyjną, w projekcie, w którym wydajna
praca programu na komputerze klasy PC nie będzie wcale wymagana.
W   chwili   obecnej   aplikacja   składa   się   z   pięciu   zasadniczych   modułów:   fetchera,   backupera,
indeksera, wyszukiwarki i optymalizatora (jest jeszcze frontend, który jednak nie odgrywa większej
roli,   jeśli   chodzi   o   efektywność   i   szybkość   znajdowania   informacji).   Jak   się   wydaje,   największe
oszczędności można poczynić w trzech  ostatnich  modułach, głównie jednak dzięki modyfikacjom

indeksera artykułów. Tam bowiem tworzy się struktura danych oraz powiązania między obiektami,
dzięki którym możemy w szybki sposób nawigować w celu uzyskania z bazy danych potrzebnych nam
informacji.
Biorąc to wszystko pod uwagę, ewentualne modyfikacje podzielić możemy na co najmniej cztery
rodzaje, ze względu na poziom abstrakcji:

●

modyfikacje koncepcyjne – czyli zasadnicze zmiany w strukturze aplikacji, sposobie zapisywania
danych (w tym stosowanie nadmiarowych powiązań i kolekcji powiązań, czy fizyczna
redundancja danych), modyfikacje w algorytmach indeksujących, bądź wyszukujących dane, czy
usprawnienia polegające na przerzuceniu części funkcji wykonywanych przez obecne moduły do
oddzielnej aplikacji, działającej na przykład w tle, tym samym mniej obciążając system

●

optymalizacja na poziomie kodu – przepisanie lub usprawnienie kodu aplikacji z nastawieniem
na jak największą efektywność, zastosowanie innych języków programowania bądź szybszych,
wydajniejszych bibliotek w ramach jednego języka

●

optymalizacja na poziomie fizycznym – np. zastosowanie innego systemu plików, zastosowanie
innej techniki indeksowania lub przechowywania danych w bazie, etc

●

optymalizacja na poziomie sprzętu – na przykład zainwestowanie w sprzęt pozwalający osiągnąć
lepszą wydajność (dyski RAID, komputery wieloprocesorowe, fizyczne klastry z wielu maszyn,
etc)

W tym miejscu zajmiemy się głównie tą pierwszą grupą, czyli modyfikacją i ulepszeniem

koncepcji   aplikacji,   z   nastawieniem   na   poprawę   wydajności   oraz   zwiększenie   funkcjonalności
rozwijanego systemu. Pozostałe techniki będą natomiast wspomniane, ale nie zamierzamy się nimi
zajmować   szczegółowo,   gdyż   wybiegają   one   (szczególnie   optymalizacja   programu   na   poziomie
fizycznym   i   sprzętu)   nieco   poza   ramy   inżynierii   oprogramowania,   a   co   za   tym   idzie,   również
niniejszej pracy.
Po kolei więc, zajmiemy się teraz sprawami związanymi z koncepcją oraz implementacją systemu,
których modyfikacja może w istotny sposób wpłynąć na jego wydajność.

Optymalizacja i zmiany schematu, redundancja danych

To zagadnienie zostało już omówione w sposób szczegółowy w rozdziale Opis rozwiązania:

Alternatywne rozwiązania.

Aktualizacja scache'owanych wyników

Implementacja bota aktualizującego scache'owane wyniki zapytań jest jednym w kluczowych

zadań na najbliższy czas, jeśli myślimy o poważnym zastosowaniu omawianego w pracy rozwiązania.
Samo przechowywanie starych wyników zapytań, bez ich częstej aktualizacji bardzo szybko obniży
wiarygodność serwisu – po prostu nie będą znajdowane najnowsze artykuły. Aktualizacja wyników
powinna się odbywać w miarę często, dla popularnych zapytań nawet raz dziennie. W ramach
oszczędzania pamięci dyskowej, można by pomyśleć o usuwaniu zapytań bardzo mało popularnych
(np. takich które wystąpiły tylko raz lub dwa razy, ponad pół roku temu). Przechowywanie wszystkich
zapytań wraz z wynikami może w znaczący sposób zwiększyć rozmiar bazy danych.

Błędy ortograficzne, “literówki” i skróty w indeksowanych artykułach

W momencie obecnym aplikacja nie uwzględnia w żaden sposób błędów i literówek

występujących   w   artykułach   poddawanych   mechanizmowi   indeksowania.   Założenie,   że   artykuły
takich   błędów   nie   posiadają   jest   szlachetne   ale   jak   najbardziej   nieprawdziwe.   Prawdziwą   zmorą
wszystkich wyszukiwarek internetowych są liczne błędy występujące w indeksowanych danych. W
wyszukiwarkach   tekstów  napisanych   w  języku  polskim,  szczególnie  tych   potocznych,  do  których

zaliczają się wiadomości grup dyskusyjnych, jest to szczególnie uciążliwa niedogodność. Wiele osób
pomija   bowiem   w   tekście   specyficzne   dla   języka   polskiego   „ogonki”,   popełnia   literówki   („nei”,
„keidy”, etc), czy też zwyczajne błędy ortograficzne. Masowo stosowane są także różnego rodzaju
skróty związane zarówno ze specyficznym slangiem związanym z konkretnym tematem grupy,  z tzw.
nowomową   internetową,   jak   i   ze   zwyczajnym   lenistwem.   Sprawdzanie   pisowni   przy   wysyłaniu
wiadomości e-mail lub NNTP jest wciąż zwyczajem tylko nielicznych.
Im  więcej  jednak   błędów   w   indeksowanych   artykułach,   tym  mniej   dokładne   potencjalne   wyniki
wyszukiwania i tym gorsza obiektywna efektywność wyszukiwarki. Aby temu zaradzić, należałoby
zastosować podczas indeksowania specjalne mechanizmy służące do identyfikacji błędów w tekście
artykułu.   Nierozważne   zastosowanie   „inteligentnych”   sposobów   weryfikacji   tekstu   może   jednak
okazać   się   niebezpieczne.   Czysto   statystyczne   metody   mają   to   do   siebie,   że   nie   sprawdzają   się
zazwyczaj   w   kilku   procentach   przypadków.   A   to   może   wystarczyć   to   ośmieszenia   produktu
bazującego   na   takich   algorytmach.   Eliminacja   wszystkich   błędów   to   zadanie   niewykonalne   dla
automatycznego   bota.   Biorąc   to   pod   uwagę,     należałoby   zastosować   metodę   pośrednią   i
półautomatyczną, zorientowaną na wychwycenie najczęstszych i najbardziej oczywistych przypadków
błędów (które prawdopodobnie stanowią zdecydowaną większość pomyłek). Identyfikacja najczęściej
pojawiających się literówek, czy też automatyczne zamienienie słów z pominiętymi „ogonkami” na
ich odpowiedniki znajdujące się w bazie danych zdecydowanie polepszyłoby precyzję i efektywność
wyszukiwania, nie poddając tym samym w wątpliwość wiarygodności mechanizmu.

Zindeksowanie starszych danych

Dla potrzeb testowania zostały do tej pory ściągnięte dane ze wszystkich polskich grup

dyskusyjnych z całego ostatniego roku. Dane ściągane i backupowane były na bieżąco, przez serwer
grup dyskusyjnych  Leafnode. Aby wyszukiwarka mogła rzeczywiście zaistnieć na rynku niezbędne
będzie jednak ściągnięcie i zindeksowanie dużo starszych danych. Myślimy tu o co najmniej kilku (a
najlepiej kilkunastu) latach wstecz. Może to niestety zrodzić kilka problemów. Pierwszym z nich jest
dostęp do starszych newsów. Możliwe że niezbędne byłoby ściąganie artykułów z innego archiwum,
np. z katalogów Google (które zawierają prawie całe archiwum grup dyskusyjnych od początku ich
istnienia,   wykupione   w   2001   roku   od   Deja   News).   Po   drugie,   mogą   wystąpić   problemy   z
indeksowaniem starszych artykułów – ze względu na różnice w nagłówkach wiadomości. Być może
potrzebne   byłoby   przepisanie   lub   naniesienie   poprawek   na   algorytm   parsowania   wiadomości   w
indekserze. Oba te problemy wydają się jednak minimalne, w porównaniu z największym kłopotem –
jak znaleźć miejsce na przechowywanie zindeksowanych archiwów. Przy zastosowaniu omówionej
kilka   akapitów   wcześniej   struktury   słów   opartej   o   haszowane   tablice   referencji,   całe   archiwum
mogłoby liczyć się nawet w setkach terabajtów...

Rozszerzenie mechanizmu na inne typy danych

Rozszerzenie mechanizmu indeksowania i wyszukiwania na inne typy danych (np. intranet,

dokumenty tekstowe w różnych formatach, strony www) jest nietrywialne. Już na samym wstępie
wspomniano, że każdy rodzaj danych potrzebuje specyficznego podejścia i uniwersalne mechanizmu
zazwyczaj  nie sprawdzają  się w specyficznych zastosowaniach.  W szczególności, algorytm, który
sprawdza   się   w   wyszukiwaniu   grup   dyskusyjnych   nie   musi   koniecznie   mieć   zastosowania   w
przeszukiwaniu   intranetu,   czy   sieci   Internet.   Dlatego   też,   jeśli   chcielibyśmy   rozszerzyć
funkcjonalność aplikacji o nowe rodzaje danych, potrzebne byłoby nie tylko napisanie odpowiedniego
fetchera   (to   stosunkowo   proste   zadanie),   ale   dostosowanie   całej   struktury   danych,   algorytmu
indeksowania, wyszukiwania i optymalizacji (a nawet frontend) do nowego typu informacji. Nie jest
to wprawdzie równoznaczne z napisaniem drugiej aplikacji zajmującej się nowymi danymi. Wiele
wykorzystanych w projekcie mechanizmów jest na tyle uniwersalnych, że można je zastosować  do
wielu   rodzajów   przetwarzanych   danych.   Jest   to   jednak   zajęcie   czasochłonne   i   wymagające

odpowiedniej analizy oraz przeprojektowania części aplikacji. Kierunek, w którym należałoby pójść,
myśląc   o   możliwości   dodawania   z   czasem   obsługi   nowych   typów   danych,   to   wyodrębnienie   z
aktualnego projektu elementów wspólnych (np. stworzenie uniwersalnej klasy Artykuł) i oddzielna
implementacja   wyspecjalizowanych   elementów,   korzystających   ze   wspólnych   zasobów   (z   klasy
Artykuł dziedziczyłyby klasy wyspecjalizowane, jak Artykuł WWW, Artykuł NNTP, Artykuł PDF,
etc, odpowiedzialne za specyficzne operacje na swoich typach danych). Dużym ułatwieniem jest tutaj
technologia  w jakiej  napisany   został   projekt.   Objectivity   bardzo  dobrze  radzi   sobie   ze zmianami
schematu   danych   (mechanizm  Active   Schema)   podczas   pielęgnacji   projektu.   Java   jest   natomiast
bardzo wygodna przy wprowadzaniu zaawansowanych zależności pomiędzy obiektami w aplikacji.

Priorytety wyników wyszukiwania – zindeksowanie autorów

Wydaje się, że szczególnie przy wyszukiwaniu wiadomości w archiwach specjalistycznych

grup dyskusyjnych spore znaczenie może mieć to, kto jest autorem danego posta. Jeśli jest to osoba
kompetentna,   prawdopodobnie  chcielibyśmy,  żeby jej   wiadomości  zyskiwały  wyższy  priorytet  od
wiadomości początkujących użytkowników. Gdyby udało się w prosty sposób wymyślić mechanizm
identyfikacji autora i nadawania mu pewnej “kompetencji”, informację tę można by zastosować przy
obliczaniu wagi wyników wyszukiwania. Cały problem polega na tym, że trudno ocenić kompetencje
czy wiedzę jedynie po ilości wysłanych postów, czy też ilości odpowiedzi na dany post. Możliwe, że
oprócz   standardowych   mechanizmów   statystycznych   potrzebna   byłaby   ręczna   weryfikacja   tego
rodzaju danych.
Technicznie,  do  zindeksowania   autora  artykułu  służyłaby  metoda  indexAuthor()  w klasie   Article.
Miałaby   ona   za zadanie  identyfikację  autora na  podstawie  wartości  pól nagłówków wiadomości
NNTP, takich jak:

–

From,

–

Message-ID,

–

Mime-Version,

–

Content-Type.

Pewne dane dodatkowe można by uzyskać także poprzez zbadanie podpisu autora (w postach

na grupach dyskusyjnych przyjęło się, że podpis oddzielony jest od reszty wiadomości znacznikiem
podwójnym myślnikiem i spacją: “-- “.
Oczywiście   najwięcej   informacji   o  użytkowniku  możemy  ustalić   poprzez   zbadanie   adresu   e-mail
użytkownika. Reszta informacji ma charakter dodatkowy i brana jest pod uwagę w przypadku braku
możliwości identyfikacji tylko poprzez sam adres mailowy.
Idąc dalej tym tropem, możliwe jest stworzenie profilu autora z możliwością przejrzenia wszystkich
jego postów w usenecie. Już samo wypisanie grup dyskusyjnych, w których dany autor zamieszcza
swoje wypowiedzi mówi sporo o zainteresowaniach osoby. Informacje takie można by wykorzystać
na wiele sposobów. Od stworzenia zaawansowanych statystyk, do analizy biznesowej zainteresowań
użytkowników   włącznie.   Użytkownicy   to   bowiem   potencjalni   klienci,   których   zainteresowania
przekładają   się   zazwyczaj   na  potrzeby   materialne,   a  taka   informacja  jest   w   dzisiejszym  biznesie
bezcenna.

Użycie zaawansowanych mechanizmów dostarczonych przez Grama

–

Lista najczęstszych i najistotniejszych słów – możliwość wykorzystania “streszczenia” artykułu
(czyli listy najistotniejszych słów występujących w artykule) do usprawnienia mechanizmu
indeksowania (nie ma sensu indeksować słów nie przekazujących żadnej treści)