ALG3

5.7. Uniwersalna struktura słownikowa 153

Najwyższa już pora wyjaśnić właściwy temat naszych rozważań. Otóż wiele programów z różnych dziedzin, ale operujących tekstem wprowadzanym przez użytkownika, może posiadać funkcję sprawdzania poprawności ortograficznej wprowadzanych pieczołowicie informacji (patrz np. arkusze kalkulacyjne, edytory tekstu). Całkiem prawdopodobne jest, iż wielu Czytelników chciałoby móc zrealizować w swoich programach taki „mały weryfikator”, jednak z uwagi na znaczne skomplikowanie problemu nawet się do niego nie przymierzają. W istocie z problemem weryfikacji ortograficznej są ściśle związane następujące pytania, na któr e odpowiedź wcale nie jest jednoznaczna i prosta:

•    jakich struktur danych używać do reprezentacji słownika?

•    jak zapamiętać słownik na dysku?

•    jak wczytać słownik „bazowy” do pamięci?

•    jak uaktualniać zawartość słownika?

Konia z rzędem temu, kto bez wahania ma gotowe odpowiedzi na te pytania! Oczywiście na wszystkie naraz, bowiem nierozwiązanie na przykład problemu zapisu na dysk czyni resztę całkowicie bezużyteczną.

Ze wszelkiego rodzaju słownikami wiąże się również problem ich niebagatelnej objętości. O ile jeszcze możemy się łatwo pogodzić z zajętością miejsca na dysku, to w przypadku pamięci komputera decyzja już nie jest taka prosta -średniej wielkości słownik ortograficzny może z łatwością „zatkać” całą dostępną pamięć i nie pozostawić miejsca na właściwy program. No, chyba, że ma on wypisywać komunikat: „Out of memory” ... Sprawy komplikują się niepomiernie, jeśli w grę wchodzi tak bogaty język, jakim jest np. nasz ojczysty - z jego mnogimi formami deklinacyjnymi, wyjątkami od wyjątków etc. Zapamiętanie tego wszystkiego bez odpowiedniej kompresji danych może okazać się po prostu niewykonalne.

Istnieją liczne metody kompresji danych, większość z nich ma jednak charakter archiwizacyjny - służący do przechowywania, a nie do dynamicznego operowania danymi. Marzeniem byłoby posiadanie struktury' danych, która przez swoją naturę automatycznie zapewnia kompresję danych już w pamięci komputera, nie ograniczając dostępu do zapamiętanych informacji.

Prawdopodobnie wszyscy Czytelnicy domyślili się natychmiast, że USS należy do tego typu struktur danych.

Idea USS opiera się na następującej obserwacji: wiele słów posiada te same rdzenie (przedrostki), różniąc się jedynie końcówkami (przy rostkami). Przykładowo

Ang. Rrak pamięci