Narzędzia do automatów skończonych

I czemu to służy?

• Poprawianiu pisowni
• Dopisywaniu znaków diakrytycznych
• Analizie i syntezie morfologicznej
• Pozyskiwaniu opisów morfologicznych nowych słów dla potrzeb słownika
• Otrzymywaniu idealnej funkcji mieszającej

Dostępne pakiety

fsa - automaty proste

• fsa_accent - dopisuje znaki diakrytyczne (ogonki). Szybki program. Słowniki charakteryzują się małym rozmiarem i powstają na podstawie zwykłych list słów. Można używać wielu słowników naraz. Interfejs do emacsa oparty na ispell.el.
• fsa_build - tworzy różne rodzaje prostych automatów. Nie wymaga wyrażeń regularnych, tablic itp. Jeden wiersz danych wejściowych traktowany jest jako jedno słowo. Dane muszą być uporządkowane leksykograficznie i nie zawierać kopii.
• fsa_ubuild - robi to samo, co fsa_build, ale wolniej i zużywając więcej pamięci. Natomiast nie wymaga uporządkowania danych i radzi sobie z kopiami.
• fsa_guess - dokonuje analizy morfologicznej słów zarówno znanych, jak i nieznanych. Analiza znanych słów może być poprawna w 100%, nieznanych - przybliżona, oparta na analizie przyrostków i przedrostków. Słownik budowany na podstawie słownika morfologicznego dla danego języka, więc gdy takowy jest dostępny, do budowy słownika dla tego programu nie jest wymagana specjalna wiedza językoznawcza. Możliwe jest także odgadywanie morfologicznych opisów słów w formacie mmorph (narzędzia do tworzenia słownika morfologicznego z ISSCO). Pomaga w tym interfejs Tcl/Tk. Mając podstawowy słownik morfologiczny można użyć tych narzędzi do jego powiększenia.
• fsa_hash - wdraża doskonałą funkcję mieszającą. Słowa na posortowanej liście są numerowane i program tłumaczy je na liczby i odwrotnie. Może to być użyte np. do indeksowania encyklopedii.
• fsa_morph - dokonuje analizy morfologicznej słów, tzn. dla danej formy odmienionej podaje odpowiedni wyraz słownikowy (hasło w słowniku) i kategorie. Możliwe jest użycie kilku słowników jednocześnie. Słowniki mają mały rozmiar, a dane dla nich mają prosty format. (Przykładowy skrypt w języku awk jest dostępny w pakiecie.) Program jest bardzo szybki. Interfejs dla emacsa ułatwia etykietowanie zbiorów tekstów.
• fsa_prefix - wypisuje słowa ze słownika zaczynające się podanym łańcuchem znaków.
• fsa_spell - poprawia pisownię tekstów. Dwuznaki wymawiane tak samo jak inne litery mogą być traktowane jako pojedyncze znaki, co sprawia, że jeśli użytkownik pomyli ,,ż'' z ,,rz'', to prawidłowe słowo pokaże się w podpowiedziach (o ile istnieje w słowniku).
• fsa_synth - tworzy formy powierzchniowe (np. formy fleksyjne) na podstawie wyrazu hasłowego i podanych cech formy powierzchniowej. Cechy mogą być dane w postaci wyrażenia regularnego. Wypisanie wszystkich form powierzchniowych dla danego wyrazu hasłowego także jest możliwe.
• fsa_visual - tworzy dane dla graficznego obrazowania automatów przez program vcg. Użyteczny dla celów diagnostycznych.
• W pakiecie znajdują się też różne skrypty, głównie to zmiany formatu danych, ale też np. skrypt w Tcl/Tk tworzący interfejs dla dodawania nowych słów do słownika morfologicznego.

utr - ,,automaty tłumaczące''

• tr_accent - dopisuje (odtwarza) znaki diakrytyczne (,,ogonki''). Szybki program, używa tych samych słowników co tr_spell i tr_morph. Może używać kilu słowników naraz. Dostępny interfejs do emacsa (oparty na ispell.el).
• tr_morph - dokonuje zarówno analizy morpfologicznej, jak i generacji form odmienionych. Może używać kilku słowników naraz - tych samych, co tr_accent i tr_spell. Interfejs do emacsa ułatwia oznaczanie zbiorów tekstów.
• tr_prefix - wypisuje hasła w słowniku, których formy powierzchniowe (formy odmienione) zaczynają się podanym łańcuchem znaków.
• tr_spell - poprawia pisownię słów. Szybki. Używa tych samych samych słowników co tr_accent i tr_morph. Może używać kilku słowników naraz. Dwuznaki wymawiane tak samo jak inne litery mogą być traktowane jako pojedyncze znaki, co sprawia, że jeśli użytkownik pomyli ,,ż'' z ,,rz'', to prawidłowe słowo pokaże się w podpowiedziach (o ile istnieje w słowniku).
• tr_ubuild - tworzy ,,automaty tłumaczące'' dla tr_accent, tr_morph, tr_prefix i tr_spell. Automaty tłumaczące szczególnie dobrze nadają się do przechowywania informacji morfologicznych.

Słowniki

Reguły dotyczące końcówek nazw

fsa

lista słów w formie prostego automatu - używana przez fsa_accent i fsa_spell.

fsm

morfologia w formie prostego automatu - używana przez fsa_morph

atg

lista a tergo form odmienionych z doczepionymi kategoriami - używana przez fsa_guess skompilowany bez opcji GUESS_LEXEMES lub uruchomiony z opcją -a. Używana do odgadnięcia kategorii słów na podstawie ich końcówek.

atl

lista a tergo form odmienionych z doczepionymi odpowiednimi wyrazami słownikowymi i kategoriami - używana przez fsa_guess skompilowany z opcją GUESS_LEXEMES, ale bez GUESS_PREFIX, lub uruchamiany z opcją -p. Używana do odgadywania wyrazów słownikowych i kategorii odpowiadających formom odmienionym na podstawie końcówek.

atp

lista a tergo form odmienionych z doczepionymi odpowiednimi wyrazami słownikowymi i kategoriami - używana przez fsa_guess skompilowany z opcjami GUESS_LEXEMES i GUESS_PREFIX. W tym typie automatu przedrostki przechowywane są w inny sposób, tak że automat jest mniejszy i możliwe są pewne dodatkowe uogólnienia. Używana jest do odgadywania wyrazów słownikowych i kategorii na podstawie końcówek i przedrostków.

tr

automat tłumaczący - używany przez programy o nazwach zaczynających się na ,,tr_'' (programy z pakietu utr).

Dostępne słowniki

deutsch1.fsa.gz

Lista niemieckich słów z ftp.informatik.tu-muenchen.de:/pub/doc/dict/. Siedmiobitowa, umlauty jako dodatkowe e, scharfes s jako ss. Ciężko przerobić na ośmiobitowe, bo nie każde oe to o umlaut, nie każde ss to scharfes s itd.

english.fsa.gz

Lista angielskich słów z /usr/dict/words.

francais.atl.gz

Francuski słownik a tergo z wyrazami słownikowymi z ISSCO

francais.fsa.gz

Lista słów francuskich z ISSCO

francais.fsm.gz

Morfologia francuska (prosty automat) z ISSCO

francais.tr.gz

Francuski automat tłumaczący z ISSCO

french_moby.fsa.gz

Lista słów francuskich z Projectu Moby

polski.fsa.gz

Lista polskich słów z artykułów z Dziennika Bałtyckiego

Inne napisane przeze mnie oprogramowanie dotyczące automatów skończonych

• biblioteka funkcji do przetwarzania języka naturalnego - podzbiór funkcji pakietu fsa, ale zawierający dodatkowo modele języka.
• przyrostowa minimalizacja automatów skończonych i inne algorytmy minimalizacji dla porównania.
• różne algorytmy tworzenia acyklicznych automatów skończonych.

• Pakiet fsa i związana z nim biblioteka fadd są używane w Alpino - analizatorze składniowym dla języka niderlandzkiego.
• Dawid Weiss przetłumaczył większośc pakietu fsa (oprócz tworzenia automatów) na język Java. Jego zbiór klas Javy jest używany w jego projekcie polskiego ,,lametyzatora''.
• Guillaume Rousse napisał skrypt w perlu umożliwiający korzystanie z pakietu fsa w tym języku.
• Marcin Miłkowski pielęgnuje słownik ortograficzny, który używa programu fsa_spell z pakietu fsa.

Dodatkowe informacje na temat automatów skończonych

• Algorytmy dotyczące automatów skończonych.
• Poszukaj w The Computation and Language E-Print Archive artykułów Kemala Oflazera. Używam zmienionej wersji jego algorytmu poprawiania błędów literowych.
• To samo z Mehryar Mohri. Nie używam jego algorytmów minimalizacji automatów tłumaczących, ale artykuły są ciekawe. Więcej jego artykułów i trochę oprogramowania można znaleźć pod adresem AT&T.
• Najbardziej technicznie zaawansowane automaty tłumaczące ma Xerox. Moja praca powstała w wyniku przemyśleń po wysłuchaniu wystąpienia Lauri Karttunnena w Archamps. Xerox ma zbiór artykułów, i stronę poświęconą automatom skończonym z ciekawą wersja pokazową.
• Strona Gertjana van Noorda opisująca wywierający wrażenie zbiór narzędzi do automatów skończonych (z narzędziami do przedstawiania w formie obrazowej). Są dużo bardziej zaawansowane technicznie, choć mają trochę inne przeznaczenie. Nie używam ich algorytmów.
• Zbiór artykułów Bruce'a W. Watsona zawierający m.in. opis różnych algorytmów minimalizacji grafów i zbiór funkcji FIRE Engine (także dostępny przez ftp). Nie używam jego algorytmów; moje automaty są minimalizowane w trakcie powstawania.
  Bruce W. Watson pracuje teraz na politechnice w Eindhoven i na Uniwersytecie w Pretorii, w Południowej Afryce. Ponieważ mnóstwo osób poszukuje go, przydałby się ,,uniwersalny lokalizator Bruce'a W. Watsona", ale to beznadziejne zadanie.
• Tomasz Kowaltowski z zespołem (Cláudio L. Lucchesi and Jorge Stolfi) tworzy najmniejsze (w bajtach) automaty stosując specjalne kodowanie na poziomie pojedyńczych bitów. Począwszy od wersji 0.17 używam opisanej przez nich kompresji łańcuchów stanów.
• Automaty wzbudzające jeszcze większy podziw niż te z firmy Xerox używane są w projekcie INTEX. Zespół INTEX używa też automatów ze stosem (zdolnych do analizy gramatyk bezkontekstowych). Widziałem system w działaniu i szczególnie zachwyciła mnie łatwość wprowadzania nowych informacji i różnorodność danych wyjściowych. Istnieje także młodsza wersja tego systemu - Unitex, działająca w Unicode. Unitex jest dostępny na licencji GPL (bezpłatnie).
• Można przeczytać artykuł, który napisałem wspólnie z Brucem Watsonem i Richardem Watsonem na temat tworzenia minimalnych, deterministycznych, acyklicznych (tzn. nie zawierających pętli) automatów skończonych. Wykorzystuję opisane tam algorytmy w moich programach.
• Stoyan Mihov niezależnie ode mnie wynalazł algorytm dla danych posortowanych. W swoim artykule dostarcza dowodu na minimalne wymagania pamięciowe algorytmu. Wspólnie z Brucem Watsonem, Richardem Watsonem i Stoyanem Mihovem napisaliśmy nową, rozszerzoną wersję naszego artukułu. Ukazała się w Computational Linguistics 26(1), 2000.
• Vincent Le Maout napisał standardową bibliotekę wzorców dla automatów skończonych The Automaton Standard Template Library.
• Arnaud Adant rozszerzył ją w WFST.
• Pakiet fsa używany jest w - analizatorze składniowym dla języka niderlandzkiego.
• Wreszcie można przyjrzeć się mojej rozprawie doktorskiej (po angielsku).

Forsa

Programy są darmowe dla celów niehandlowych. Użycie w celach handlowych jest możliwe po uzyskaniu ode mnie pozwolenia (chciałbym dostać swój udział).

Programy nie są objęte żadną formą gwarancji. Jeśli straciłeś (straciłaś) milion złotych w wyniku użycia któregoś z programów, to był Twój milion, nie mój. Jest to taka sama gwarancja, jak do większości znanych programów, ale moja jest krótsza.

Począwszy od wersji 0.42, pakiet fsa może być rozpowszechniany z licencją GPL poza jednym plikiem pochodzącym z innego źródła i posiadającym inną licencję i prawa autorskie. Ponieważ prawniczy bełkot jest mało czytelny, nie wiem, jak GPL stosuje się w połączeniu z takimi pliki, więc nie jest tu załączona.

Błędy