Indeks autouzupełniania tytułów w bibliotece
W bibliotece szkolnej powstał moduł autouzupełniania tytułów. Baza zawiera 180 000 tytułów, średnio 42 znaki, w tym polskie litery. Serwer ma 64 MB RAM dostępne dla indeksu, a aplikacja obsługuje 50 000 zapytań dziennie o prefiks długości od 2 do 10 znaków. Nowe tytuły dodawane są rzadko: około 20 tygodniowo; usuwanie prawie nie występuje. Zespół rozważa trzy rozwiązania: posortowaną tablicę tytułów z wyszukiwaniem binarnym, tablicę mieszającą (hash) oraz trie. W testach posortowana tablica dawała poprawne wyniki, ale dodanie tytułu wymagało przesunięcia średnio 90 000 elementów. Hash odpowiadał szybko na dokładne tytuły, ale nie na prefiksy. Trie z 32-znakowym alfabetem i wskaźnikami 4-bajtowymi zajął więcej pamięci, niż początkowo szacowano. Trzeba wybrać strukturę i sposób normalizacji liter, aby wyszukiwanie prefiksów było przewidywalne, a pamięć nie przekroczyła limitu. Wymagania: poprawność dla liter wielkich i małych oraz polskich znaków diakrytycznych, akceptowalny czas odpowiedzi do 200 ms.
1. Wybierz strukturę dla opisanych wymagań i uzasadnij, porównując pamięć oraz koszt operacji.
Read the worked answer
Najrozsądniejszy jest posortowany indeks tytułów z wyszukiwaniem binarnym, ewentualnie przebudowywany okresowo po dodaniu nowych tytułów. 180 000 tytułów po około 42 znaki to około 7,6 mln znaków; nawet z narzutem na obiekty i wskaźniki mieści się to w kilkunastu–dwudziestu MB, czyli w 64 MB. Zapytanie o prefiks to O(log n + k), gdzie k to liczba wyników; przy 50 000 zapytań dziennie i krótkich prefiksach jest to akceptowalne. Hash odpada, bo nie obsługuje prefiksów bez dodatkowego indeksu. Trie teoretycznie daje O(długość prefiksu), ale pamięć jest ryzykiem: pesymistycznie 180 000×42≈7,56 mln węzłów; przy 32 wskaźnikach po 4 B to ponad 960 MB, a nawet po kompresji wspólnych prefiksów trudno zagwarantować 64 MB. Rzadkie dodawanie (20 tygodniowo) sprawia, że koszt O(n) przy wstawieniu jest do przyjęcia, jeśli przebudowa odbywa się poza godzinami szczytu.
2. Opisz normalizację tekstu i sposób obsługi polskich znaków oraz wielkości liter.
Read the worked answer
Należy rozdzielić tekst wyświetlany od klucza wyszukiwania. Tytuł przechowujemy w oryginale, a do indeksu tworzymy klucz: ujednolicenie Unicode, zamiana na małe litery, redukcja wielokrotnych spacji i opcjonalne usunięcie diakrytyków, np. Łódź→lodz. Dzięki temu zapytanie lodz znajdzie Łódź, a LÓDŹ też. Trzeba ustalić politykę: czy diakrytyki mają znaczenie. W polskiej bibliotece zwykle warto je ignorować w wyszukiwaniu, ale zachować w prezentacji. Normalizacja musi być deterministyczna i taka sama przy budowie indeksu i przy zapytaniu. Warto użyć casefold() lub odpowiednika oraz normalizacji NFC/NFD, a nie ręcznej zamiany pojedynczych liter. Testy powinny obejmować ą/ć/ę/ł/ń/ó/ś/ź/ż, wielkie litery, spacje i znaki interpunkcyjne.
3. Oszacuj, czy 64 MB wystarczy dla trie, i wskaż, co zmienić, jeśli nie.
Read the worked answer
Dla 180 000 tytułów po 42 znaki pesymistyczna liczba węzłów to około 7,56 mln. Nawet jeśli każdy węzeł ma tylko 32 wskaźniki po 4 B, same wskaźniki zajmą około 968 MB; dochodzi narzut na licznik, flagę końca i alokację obiektów. Wspólne prefiksy zmniejszą tę liczbę, ale bez pomiaru nie ma gwarancji zmieszczenia się w 64 MB. Bezpieczny wniosek: zwykłe trie z tablicą 32 wskaźników nie spełnia limitu. Alternatywy: trie skompresowane (radix/patricia), które łączy łańcuchy jednoznaczne, mapa posortowanych tytułów z przebudową, albo hash plus osobny posortowany indeks prefiksów. Jeśli pozostajemy przy trie, trzeba zmniejszyć alfabet przez normalizację, użyć indeksów 2-bajtowych lub dynamicznych map dzieci, ale i tak należy wykonać realny pomiar pamięci na pełnym zbiorze.