Wyszukiwarka
Filtry
wszystkich: 18
Wyniki wyszukiwania dla: automaty skonczone
-
Incremental construction of finite-state automata
PublikacjaRozdział przedstawia algorytmy przyrostowego i półprzyrostowego tworzenia minimalnych deterministycznych automatów skończonych.
-
An implementation of deterministic tree automata minimization
PublikacjaWstępujący, deterministyczny, skończony automat drzewiasty (DTA) może być używany jako struktura danych do przechowywania zbiorów nieuporządkowanych drzew bez narzuconej liczby poddrzew. Takie automaty są zwykle rzadsze niż automaty działające na napisach i dlatego należy zwrócić szczególną uwagę na ich wydajną minimalizację. W dostępnej literaturze jest jednak ciężko znaleźć proste i szczegółowe opisy procedury minimalizacji....
-
Semi- incremental construction of minimal cyclic finite state automata usingcontinuation classes.
PublikacjaMinimalne automaty skończone są często wybierane do przedstawiania słowników morfologicznych języka naturalnego. Wśród ich zalet znajdują się duża szybkość rozpoznawania i małe wymagania pamięciowe. Tłumaczenie opisów morfologicznych opartych o klasy kontynuacji na minimalne, cykliczne automaty skończone jest tradycyjnie dokonywane w kilku fazach, zawierających tworzenie automatu niedeterministycznego z przejściami etykietowanymi...
-
An efficient incremental DFA minimization algorithm
PublikacjaW tym artykule przedstawiamy nowy algorytm minimalizacji deterministycznego automatu skończonego. Algorytm jest przyrostowy - może być zatrzymany w dowolnym momencie, dając częściowo zminimalizowany automat. Wszystkie inne (znane) algorytmy minimalizacji dają wyniki pośrednie nieprzydatne dla częściowej minimalizacji. Ponieważ pierwszy algorytm jest łatwo zrozumiały ale mało wydajny, rozważamy trzy praktyczne, znaczące usprawnienia....
-
Comparison of construction algorithms for minimal, acyclic, deterministicfinite state automata from sets of strings.
PublikacjaArtykuł porównuje różne metody tworzenia minimalnych, acyklicznych, deterministycznych automatów skończonych ze zbiorów słów. Wdrożone i porównane zostały metody przyrostowe, prawie przyrostowe i nieprzyrostowe.
-
Semi-incremental addition of strings to a cyclic finite automaton
PublikacjaMaszyny o skończonej liczbie stanów są szeroko stosowane jako słowniki w przetwarzaniu języka naturalnego. Odznaczają się szybkim czasem przetwarzania i małymi wymaganiami pamięciowymi. Przedstawiamy nowy algorytm dodawania nowych słów do języka cyklicznego automatu skończonego. Algorytm jest rozszerzeniem na automaty cykliczne półprzyrostowego algorytmu Watsona dla automatów acyklicznych. Przekształcenie jest dokonane w duchu...
-
Incremental and Semi-Incremental Construction of Pseudo-Minimal Automata
PublikacjaPrzedstawione zostają modyfikacje trzech algorytmów przyrostowego i półprzyrostowego tworzenia automatów minimalnych w taki sposób, aby tworzyły automaty pseudominimalne. Istniejący od dawna algorytm Revuza tworzy takie automaty szybciej i zużywając mniej pamięci, ale wymaga kłopotliwego sortowania. Nie nadaje się też do dodawania nowych słów do automatu - ważnej czynności w realizacji dynamicznej doskonałej funkcji mieszającej....
-
Dynamic Perfect hashing with finite-state automata
PublikacjaMinimalna doskonała funkcja mieszająca dostarcza odwzorowania zbioru n niepowtarzalnych słów w zwarty zakres n liczb całkowitych. Gdy jest realizowane za pomocą automatów skończonych, odwzorowanie wynika z porządku słów (zwykle alfabetycznego) w zbiorze. Dodanie nowych słów zmieniłoby porządek słów rozpoznawanych przez automat, zmieniając całe odwzorowanie i czyniąc je bezużytecznym w wielu dziedzinach. Dlatego nazywamy je statycznym....
-
Gazetteer compression technique based on substructure recognition
PublikacjaAutomaty skończone są najlepszą formą reprezentacji słowników do przetwarzania języka naturalnego. Przedstawiamy nową technikę kompresji, która jest szczególnie użyteczna w stosunku do pewnego rodzaju słowników. Zastępujemy wielokrotnie występujące podstruktury ich niepowtarzalnymi reprezentantami. Do ich znalezienia traktujemy wektor przejść jako tekst i stosujemy technikę kompresji tekstu w stylu Ziv-Lempel, która znajduje powtórzenia...
-
Incremental and pseudo-incremental construction of pseudo-minimal automata.
PublikacjaAutomaty pseudominimalne mają dla każdego słowa w języku automatu co najmniej jeden element własny (stan lub przejście), który nie jest współdzielony z żadnym innym słowem. Przedstawiamy przyrostowe i półprzyrostowe algorytmy tworzenia takich automatów.
-
Les transducteurs à sorties variables
PublikacjaW przetwarzaniu języka naturalnego słowniki elektroniczne wiążą ze słowami informacje. Najwydajniejsza reprezentacja takich słowników używa maszyn ze skończoną liczbą stanów (automatów prostych lub automatów Mealy'ego). W tym artykule wzorując się na algorytmach bezpośredniej budowy minimalnego automatu deterministycznego proponujemy nowy typ automatu Mealy'ego. Ta nowa forma pozwala na szybkie obliczanie informacji wyjściowej...
-
Finite-state lexical tools
PublikacjaArtykuł przedstawia trzy pakiety oprogramowania zawierające narzędzia poziomu leksykalnego wykorzystujące automaty skończone: dwa zbiory samodzielnych programów i skryptów pomocniczych - jeden używający prostych automatów skończonych, drugi używający automatów Mealy`ego oraz bibliotekę funkcji. Wszystkie przedstawione pakiety posiadają podobne funkcje. Zamiast opisywać poszczególne pakiety, opis skupiony jest na dostarczanych przez...
-
Finite automata for compact representation of tuple dictionaries.
PublikacjaOpisane zostaje uogólnienie struktury danych - słownika, zwane słownikiem n-tek. Słownik n-tek przedstawia odwzorowanie n-tek łańcuchów znaków na pewne wartości. Motywacją dla powstania tej struktury danych są praktyczne zastosowania w przetwarzaniu języka i mowy, w których obszerne słowniki n-tek używane są do przedstawiania modeli języka. Przedstawiona zostaje technika oszczędnej reprezentacji słowników n-tek. Ta technika...
-
Extension of selected ADFA construction algorithms to the case of cyclic automata.
PublikacjaW niedawnym artykule Rafael Carrasco i Mikel Forcada przedstawiają przyrostowy algorytm dodawania słów do minimalnego, acyklicznego automatu skończonego. Ten algorytm jest uogólnieniem przyrostowego algorytmu tworzenia acyklicznych deterministycznych automatów skończonych (ADFAs). Przedstawiamy podobne uogólnienia dwóch innych algorytmów tworzenia ADFAs. Chociaż te ougólnienia zostały już opublikowane w maju i czerwcu 2004 r.,...
-
Finite automata for compact representation of language models in NLP
PublikacjaPrzedstawiona zostaje technika reprezentacji modeli języka w przetwarzaniu języka naturalnego wymagająca mało pamięci. Po krótkim omówieniu przyczyn poszukiwania oszczędnej reprezentacji takich modeli języka, pokazane jest, jak automaty skończone mogą być użyte w tym celu. Technika może być postrzegana jako zastosowanie i rozszerzenie doskonałej funkcji mieszającej z wykorzystaniem automatów skończonych. Pierwsze doświadczenia...
-
Smaller Representation of Finite State Automata
PublikacjaThis paper is a follow-up to Jan Daciuk's experiments on space-effcient finite state automata representation that can be used directly for traversals in main memory. We investigate several techniques of reducing memory footprint of minimal automata, mainly exploiting the fact that transition labels and transition pointer offset values are not evenly distributed and so are suitable for compression. We achieve a gain of around 20-30%...
-
Natural language dictionaries implemented as finite automata
PublikacjaRozdział przedstawia wykorzystanie automatów skończonych jako słowników języka naturalnego. Podane są podstawy teoretyczne. Omówione są zastosowania: realizacja doskonałej funkcji mieszającej, analizy i syntezy morfologicznej, poprawiania pisowni i dopisywania znaków diakrytycznych, wydobywanie informacji. Podano algorytmy tworzenia automatów oraz omówiono sposoby reprezentacji automatów z uwzględnieniem kompresji.
-
Smaller representation of finite state automata
PublikacjaThis paper is a follow-up to Jan Daciuk's experiments on space-efficient finite state automata representation that can be used directly for traversals in main memory (Daciuk, 2000)[4]. We investigate several techniques for reducing memory footprint of minimal automata, mainly exploiting the fact that transition labels and transition pointer offset values are not evenly distributed and so are suitable for compression. We achieve...