Automatyczne dzielenie wyrazów należy do podstawowych zadań wykonywanych przez programy komputerowe służące do składania tekstów.

Jednym z najciekawszych algorytmów dzielenia wyrazów, a przy tym dokładnie opisanych i udokumentowanych, posługuje się system TeX. Jego ,,ciekawość'' polega na tym, że jest to algorytm uniwersalny, tzn. dający się przystosować do dzielenia wyrazów w różnych językach, a jednocześnie zdumiewająco prosty i efektywny w implementacji. Warto się temu algorytmowi przyjrzeć.

Reguły dzielenia wyrazów w języku polskim

,,(...) Dzielenie wyrazów przy przenoszeniu wyrazów z jednego wiersza do następnego opiera się w ortografii polskiej na dwóch kryteriach: fonetycznym i morfologicznym. Kryterium fonetyczne nakazuje przenoszenie części wyrazu z jednego wiersza do drugiego zgodnie z podzielnością na sylaby, np. "bu rza", "nie wy trzy ma nie", "li tość", "po na pi sy wa li by", "za nie po ko jo ny", "wy so ko", "le piej", "te go", "prze ciw". Kryterium morfologiczne nakazuje przenoszenie części wyrazu z jednego wiersza do drugiego zgodnie z podzielnością na przedrostek i rdzeń, a w wyrazach złożonych --- w miejscu złożenia, np. "przed murze", "pod punkt", "wy brzeże", "roz łąka", "od dźwięk", "przy kład", "za płata", "na trafić", "wy ścigi", "o brona", "bez wstyd", "u kładowy", "po dróż", "pod oficer", "pod oddział", "na przód", "pod o pieczny", "po dmuch", "noc leg", "konio krad". (...)''

przy czym

,,(...) kryterium morfologiczne jest nadrzędne w stosunku do kryterium fonetycznego (...)''

Zasady ogólne wyglądają prosto i przejrzyście. Omówienie zasad szczegółowych zajmuje Szymczakowi pięć stron i o ile człowiekowi mogłoby to wystarczyć, to jednak zalecenia takie jak:

,,(...) Jeżeli przejrzystość podziału na przedrostek i rdzeń jest w dzisiejszej świadomości językowej zatarta (podkr. aut.), grupy spółgłoskowe znajdujące się na granicy cząstek dzielimy dowolnie, np. "o błok" a. "ob łok", "o tręby" a. "ot ręby", (...)''

bardzo trudno zalgorytmizować.

Spróbujmy się zastanowić, czy nie ma takich zasad, od których nie byłoby wyjątków.

Dobrym kandydatem wydawać by się mogła reguła niedzielenia głosek "cz", "dz", "rz" oraz "sz". Niestety, są wyjątki od tej reguły: "tysiąc złotowy", "pod zwrotnikowy", "mar znąć" i "em es zet". Podobnie miękkie "ni" może ulec rozbiciu, na przykład w słowie "in iekcja".

To może chociaż da się ustalić, że sylaba nie może składać się z samych spółgłosek? Jest to w zasadzie dobra reguła, ale ma (co najmniej) jeden wyjątek: szkocki przedrostek "Mc" wolno oddzielić. Na przykład nazwisko "McMillan" wolno podzielić "Mc-Millan". Oczywiście implikuje to kłopoty z rzymskim zapisem liczb --- rok "MCMXCII" komputer mógłby uznać za szkockie nazwisko.

W takim razie może istnieją nie zakazy, a nakazy dzielenia, od których nie ma wyjątków? Np. nakaz rozdzielania par identycznych spółgłosek ("świec cy", "Jagieł ło", "łam my", "pan na", "ar ras", "las so", "get to" itp.). Odpowiedź, jak łatwo było przewidzieć, brzmi: ,,nie''. Np. kryterium morfologiczne nakazuje podział "ode ssie", a nie "odes sie", chyba że chodzi o "Odessę". A jeśli się zgodzić, że przedrostek rodzimy musi być oddzielony, to będzie kłopot ze słowem "zeppelin", bo jak komputer miałby się domyślić, że w tym przypadku nie chodzi o przedrostek "ze"? Mógłby wprawdzie wiedzieć, że żadne słowo w języku polskim nie zaczyna się od "pp" (chociaż jest słowo zaczynające się od trzech spółgłosek, z czego dwie pierwsze to "ww" --- proszę zgadnąć jakie to słowo). Ale jeśli jakiś autor chciałby oddać mowę jąkającego się bohatera pisząc np. "zeppsuuty", to co wtedy?

Niejednoznaczności typu ,,"odessie"'' stanowią dla komputera trudność praktycznie nie do pokonania. Choć jest ich niewiele, to jednak zdarzają się i utrudniają życie, np.: "podróżować" --- być w podróży lub pokryć różem lica; "odziewać" --- ubierać lub odpowiedzieć w taki sam sposób komuś, kto ziewnął; "podrobić" --- np. karmę ptactwu lub podpis; "Tarzanie" --- słowo to może oznaczać wzywanie znanego bohatera komiksów lub czynność tarzania się; "narwali" --- to słowo z kolei można rozumieć jako czas przeszły dokonany albo dopełniacz liczby mnogiej.

W sytuacjach tego typu jedynie kontekst semantyczny decyduje o podziale słowa. Rozsądnie jest nie żądać zbyt wiele od programów składających teksty i zostawić człowiekowi możliwość ingerencji w bardziej skomplikowanych przypadkach.

Sporo trudności nastręcza dzielenie nazwisk i nazw własnych. O nazwiskach szkockich już była mowa. Ale i polskie nazwy potrafią sprawić kłopot. Na przykład czy w nazwisku "Utnik" głoskę "u" należy traktować jako przedrostek, tak jak w słowie "u tnie"? Szczególnie trudne do podziału są słowa będące zbitką dwóch lub więcej słów. Zalecany jest oczywiście podział w miejscu złożenia: "noc leg", "trzech set letni" itp. Zdarzają się jednak czasem bardzo osobliwe nazwy własne, np. "Wierzch las". Chociaż taki właśnie podział wydaje się uzasadniony, to przecież trudno dać głowę, że nazwy tej nie da się wywieść od "wierzenia" i "chlastania". Podobnie gdyby jakaś miejscowość nazywała się "Szynkwas", to nazwa mogłaby się wywodzić ostatecznie --- choć jest to mało prawdopodobne --- od "szyn" i "kwasu".

"Zeppelin" i "szynkwas" to przykłady słów obcych bądź obcego pochodzenia, które zadomowiły się w naszym języku. Słowa tej kategorii, takie jak np. "er zac", "jazz man" czy "soft ware", to źródło nowych utrapień dla kogoś, kto chciałby sformalizować reguły dzielenia wyrazów w języku polskim.

W tej sytuacji nie dziwią wyniki testów porównawczych W. Puzy (W. Puza, praca magisterska pt. ,,Analiza porównawcza wybranych programów Desktop Publishing (DTP)'', Instytut Poligrafii Politechniki Warszawskiej), który stwierdził, co następuje:

,,(...) Test sprawdzający poprawność dzielenia polskich słów wyodrębnił 3 różne poziomy skuteczności testowanych programów:

• Cyfroset, TeX -- ok. 10% błędów
• Dywiz (dedykowany dla Quark'a) -- powyżej 20% błędów
• Bizon (dedykowany Calamusowi), VP Commander (dedykowany Venturze) -- powyżej 50% błędów. (...)''

Można oczywiście polemizować z wytycznymi językoznawców. Zalecany przez Szymczaka podział "za jrzeć" lub "po jmać" wydaje się dziś anachroniczny. Pójście dalej tym tropem, przy równoczesnym zasłanianiu się ,,wymaganiami komputerów'', powoduje, że zbyt kuszące staje się maksymalne upraszczanie reguł, oczywiście z uszczerbkiem dla języka polskiego.

Autor TeX-a obrał zupełnie inną drogę: szukał takiego algorytmu, który byłby w zasadzie niezależny od reguł dzielenia wyrazów; reguły dzielenia miałyby być określone za pomocą danych do tego algorytmu. Algorytm spełniający te wymagania skonstruował F. M. Liang (rozprawa doktorska pt. ,,Word Hy-phen-a-tion by Com-put-er'', Uniwersytet Stanforda, USA, 1983). Udało mu się nawet coś więcej: dane są stosunkowo łatwe do utworzenia, nie jest do tego bynajmniej potrzebna wiedza informatyczna.

Jak TeX dzieli wyrazy

Przypuśćmy teraz, że mamy dane jakieś słowo, np. odkaszlnąć. Najpierw zamieniamy je na postać taką, jaką mają wzorce, wstawiając pomiędzy literami cyfrę 0, a na brzegach kropki, otrzymując .o0d0k0a0s0z0l0n0ą0ć. (kropka --- jak stąd widać --- oznacza skraj słowa). Następnie wyszukujemy w naszym zbiorze danych wszystkie wzorce, które na to słowo dają się nałożyć w taki sposób, że zgadzają się położenia liter i kropek, ale niekoniecznie cyfr; w szczególności cyfra może się nakładać na kropkę, ale nie na literę. Powiedzmy, że znaleźliśmy następujące wzorce: .o2d2, .o0d3k2, 0ą1, 2d1k0, 2l1n0, 2s0z1l0, 2s0z0l0n0, 8ć., 0a1, 0o1, 0s4z0. Jeśli je nałożymy na słowo .o0d0k0a0s0z0l0n0ą0ć. i spośród cyfr nakładających się na siebie weźmiemy największe, to otrzymamy .o2d3k2a2s4z2l1n0ą8ć. --- i to już wszystko. Zgodnie z algorytmem Lianga słowo wolno podzielić jedynie w takim miejscu, w którym pojawia się cyfra nieparzysta. Oznacza to, że algorytm dopuszcza w tym wypadku dwa punkty podziału: "od-kaszl-nąć".

Wzorce przechowywane są w pamięci komputera jako struktura drzewiasta (dokładniej "trie"; p. D. E. Knuth, ,,The Art of Computer Programming'', tom 3, ,,Sorting and Searching''). Pozwala to na znaczne upakowanie danych przy zachowaniu szybkiego dostępu do informacji, a równocześnie struktura danych i algorytm są stosunkowo łatwo implementowalne.

Warto podkreślić, że dzięki efektywności zastosowanej metody TeX może przechowywać w pamięci kilka różnych zestawów wzorców i dzielić wyrazy w kilku językach w obrębie jednego dokumentu (a nawet akapitu).

Problem jedynie w tym skąd wziąć wzorce?

Automatyczne tworzenie danych dla algorytmu dzielenia wyrazów

 m  := maksymalna długość wzorca
 for c := 1 to 9 do
   begin
        ustal kryteria akceptowalności dla wzorców
     for l:=1 to m do
       begin
            dla każdego słowa w słowniku sprawdź, czy nie 
	    dostarcza ono informacji o możliwości wstawienia 
	    cyfry c we wzorcach długości l przy 
	    zadanych kryteriach akceptowalności
       end
  end

W niektórych przypadkach może się zdarzyć, że program nie znajdzie zestawu wzorców dzielącego poprawnie wszystkie słowa. Powodem mogą być błędne dane (np. w słowniku może się znaleźć dwa razy to samo słowo, ale inaczej podzielone) bądź niewłaściwy dobór liczb w_p, w_n oraz p w kolejnych iteracjach. Różne strategie dobierania wartości tych współczynników wpływają na objętość wynikowego zestawu wzorców. Minimalizacja liczby wzorców w wygenerowanym automatycznie zestawie wymaga pewnej wprawy i --- oczywiście --- przestudiowania pracy doktorskiej Lianga, gdzie zagadnienie to jest szczegółowo omówione.

Jak widać ,,nauczenie'' TeX-a zasad dzielenia wyrazów w danym języku jest właściwie kwestią odpowiednio zasobnego słownika podzielonych poprawnie wyrazów. Dostarczenie takiego słownika to zadanie dla językoznawców. Natomiast dalszy etap jest ideowo prosty, nie wymaga znajomości technik programowania, ani żadnych innych specjalnych umiejętności. Potrzebna jest jedynie cierpliwość.

Ręczne tworzenie danych dla algorytmu dzielenia wyrazów

W 1984 J. Désarménienowi udało się zamknąć reguły dzielenia wyrazów dla języka francuskiego w zestawie liczącym 804 wzorce i dla języka włoskiego w zestawie liczącym zaledwie 88 wzorców, podczas gdy standardowy zestaw wzorców dla amerykańskiego TeX-a zawiera ich 4447 (J. Désarménien, ,,The use of TeX in French: hyphenation and typography'', w: D. Lucarella (ed.), ,,TeX for Scientific Documentation, Proc. of the First European Conference, Addison-Wesley, 1984). Sukces podejścia Désarméniena zainspirował H. Kołodziejską, która w roku 1987 opublikowała listę 2168 wzorców dla języka polskiego (H. Kołodziejska, ,,Dzielenie wyrazów w systemie TeX'', Sprawozdania Instytutu Informatyki Uniwersytetu Warszawskiego, nr 165, 1987). Wynik Kołodziejskiej zdawał się potwierdzać wstępne założenia. Niestety. Po kilku latach intensywnego testowania (maczali w tym palce m.in. autorzy niniejszej pracy) wzorców znacznie przybyło. Po gruntownej przeróbce liczebność zestawu wzorców wzrosła do 4053 i wolno przypuszczać, że to jeszcze nie koniec.

W tych warunkach zasadne staje się pytanie, czy nie należałoby zrewidować założenia o regularności zasad podziału słów w języku polskim. Jest prawdopodobne, że program Lianga mógłby wygenerować mniej liczny zestaw wzorców.

Tym niemniej, jak wynikało z porównań poczynionych przez Puzę (p. wyżej), zestaw wzorców dla języka polskiego w swojej obecnej postaci daje wyniki zadowalające. Zważywszy, że Puza w istocie dysponował jedną z wersji pośrednich zestawu i że zestaw aktualny jest znacznie udoskonalony w stosunku do tamtej wersji, można oczekiwać jeszcze lepszych rezultatów.

Najaktualniejsza wersja tego zestawu wchodzi w skład pakietu MeX (polskiej adaptacji TeX-a). Pakiet ten jest dystrubuowany w postaci źródłowej jako produkt "public domain" przez GUST.

Inne aspekty automatycznego dzielenia wyrazów

W przypadku TeX-a nierozsądne byłoby manipulowanie za każdym razem przy zestawie wzorców. Użytkownik TeX-a może podzielić słowo według własnego uznania na dwa sposoby.

Pierwszy sposób to umieszczenie go na liście wyjątków, nadrzędnej w stosunku do wzorców. Jest to, niestety, metoda wygodna jedynie w językach niefleksyjnych. W języku polskim umieszczenie jakiegoś słowa na liście wyjątków wiąże się (w przypadku TeX-a) z podaniem od razu wszystkich jego odmian, co jest raczej nieporęczne. Na szczęście problem taki nie pojawia się zbyt często. Głównym powodem tego typu zabiegów bywają słowa złożone lub obcego pochodzenia (bądź i jedno, i drugie).

Drugi sposób polega na wskazaniu w tekście dodatkowych miejsc podziału (ang. discretionary hyphens). Większość systemów DTP oferuje taką możliwość użytkownikom. W przypadku TeX-a należy ostrożnie posługiwać się tą metodą, bo można przeszkodzić TeX-owi w automatycznym wstawianiu drobnych odstępów między znakami (inaczej podcięć, ang. implicit kerns).

TeX oferuje użytkownikowi jeszcze parę innych możliwości, pozwalających na panowanie nad algorytmem podziału wyrazów.

Zabronienie podziału wyrazu jest w TeX-u sprawą trywialną, wystarczy wyraz ,,zamknąć'' w tzw. pudełko (TeX-owa komenda \hbox).

Użytkownik może też określić minimalną długość oddzielonego początku i końca słowa. Domyślnie TeX nie podzieli słowa krótszego niż pięcioliterowe: początek nie może być krótszy niż dwie litery, koniec --- nie krótszy niż trzy litery. Przy składaniu w wąskiej szpalcie może się pojawić konieczność złagodzenia tych rygorów, zwłaszcza że w języku polskim za dopuszczalne uznaje się oddzielanie pojedynczej samogłoski na początku słowa i dwuliterowej sylaby na końcu. Z drugiej strony w składzie wysokiej jakości powinno się unikać dzielenia wyrazów w ogóle, a tym bardziej na zbyt krótkie fragmenty. Możliwość sterowania wielkością dzielonego słowa jest więc bardzo przydatna w praktyce.

Zasady dobrego składu wymagają, aby wyrazy dzielone nie pojawiały się w sąsiednich wierszach i by ostatni wiersz na prawej stronie nie zawierał słowa dzielonego. Składy nie spełniające tych wymogów uważa się (i słusznie) za brzydkie. TeX dostarcza parametrów pozwalających skutecznie utrudniać brzydkie składanie. W szczególności można wręcz zabronić umieszczania słowa dzielonego w ostatnim wierszu na stronie. Może to sprawić pewne kłopoty algorytmowi łamiącemu wiersze na strony, ale to już zupełnie inna historia.

Zostaje jeszcze problem słów zawierających łącznik, np. "biało-czerwony". W języku angielskim słowa takie jak "machine-oriented" przenosi się

 "machine-"
 "oriented"

"biało-"
"-czerwony"

Uwagi końcowe

Praktyka pokazuje, że bardzo efektywny algorytm automatycznego podziału słów, w połączeniu z niekoniecznie bardzo wygodnymi możliwościami ingerowania ręcznego, stwarza użytkownikowi możliwość panowania w pełni nad procesem dzielenia słów przez system komputerowego składu tekstów.

Wydaje się nam, że rozwiązania zastosowane przez Knutha są na tyle uniwersalne (a do tego sprawdzone w praktyce), że warto je szerzej rozpropagować. Mogą się okazać szczególnie przydatne w Polsce, gdzie rynek software'owy dopiero powstaje i dobre nomen omen wzorce są rzeczą nie do pogardzenia.