autor: Bogus�aw Jackowski, Marek Ry�ko
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�.
,,(...) 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:
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.
2s0z1z0, 2s0z0l0n0, 2t1�0 itp. Zamiast cyfry skrajnej mo�e
wyst�pi� kropka, np.: .w0e3s2, .w0w8, 8r0s0z., 8r0z0�. itp. Ci�gi te
nazywa� b�dziemy wzorcami.
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?
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
Innymi s�owy program uzupe�nia zestaw wzorc�w kolejno dla coraz
wi�kszych cyfr i coraz d�u�szych wzorc�w, zostawiaj�c u�ytkownikowi na ka�dym
etapie mo�liwo�� ingerencji. Kryteria akceptowalno�ci okre�la si� przez
podanie trzech liczb: wagi dla podzia��w poprawnych wp,
wagi dla podzia��w niepoprawnych wn i poziomu
akceptowalno�ci p. Wzorzec jest akceptowany,
gdy {kpwp-knwn>= p},
gdzie kp i kn oznaczaj� odpowiednio
liczb� poprawnych i niepoprawnych podzia��w generowanych przez dany wzorzec.
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 wp, wn 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��.
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.
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"podczas gdy w j�zyku polskim stanowczo zaleca si� dostawienie dodatkowo ��cznika na pocz�tku nast�pnego wiersza:
"bia�o-" "-czerwony"TeX pozwala do��czy� do zestawu komend standardowych komendy definiowane przez u�ytkownika. W MeX-u zosta�a zdefiniowana komenda
\=,
kt�r� nale�y podczas przygotowywania tekstu umie�ci� w miejscu ��cznika.
Kontynuuj�c przyk�ad, "bia�o-czerwony" nale�a�oby poda� TeX-owi jako
bia�o\=czerwony. U�ytkownik musi pami�ta� o konsekwentnym
przestrzeganiu tej zasady, a o reszt� zadba ju� TeX. Pozostawienie zwyk�ego
��cznika oznacza s�owo niepodzielne. Jest to przydatne w przypadku takich
s��w jak np. "K-202", kt�rych oczywi�cie dzieli� nie nale�y.
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.