Jan Daciuk - Publications - Bridge of Knowledge

Search

Filters

total: 29

  • Category
  • Year
  • Options

clear Chosen catalog filters disabled

Catalog Publications

Year 2022
  • Language Models in Speech Recognition
    Publication

    - Year 2022

    This chapter describes language models used in speech recognition, It starts by indicating the role and the place of language models in speech recognition. Mesures used to compare language models follow. An overview of n-gram, syntactic, semantic, and neural models is given. It is accompanied by a list of popular software.

    Full text to download in external service

Year 2017
  • A new library for construction of automata
    Publication

    - Year 2017

    We present a new library of functions that construct minimal, acyclic, deterministic, finite-state automata in the same format as the author's fsa package, and also accepted by the author's fadd library of functions that use finite-state automata as dictionaries in natural language processing.

Year 2015
  • Preserving Trees in Automata
    Publication

    - Year 2015

    We present a method to store additional information in a minimal automaton so that it is possible to compute a corresponding tree node number for a state. The number can then be used to retrieve additional information. The method works for minimal (and any other) deterministic acyclic finite state automata (DFAs). We also show how to compute the inverse mapping.

    Full text to download in external service

Year 2014
  • Optimization of Automata
    Publication

    - Year 2014

    This book is conceived as an effort to gather all algorithms and methods developed by the author of the book that concern three aspects of optimization of automata: incrementality, hashing and compression. Some related algorithms and methods are given as well when they are needed to complete the picture.

Year 2013
Year 2012
  • Smaller representation of finite state automata
    Publication

    - THEORETICAL COMPUTER SCIENCE - Year 2012

    This 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...

    Full text available to download

Year 2011
  • Automaty jako narzędzia w przetwarzaniu języka
    Publication

    - Year 2011

    Rozdział zawiera definicję, notację i chcarakterystykę automatów oraz algorytmy ich przekształcania, umożliwiające ich skuteczne wykorzystanie w przetwarzaniu języka.

  • Przetwarzanie języka naturalnego
    Publication

    - Year 2011

    Rozdział opisuje przetwarzanie języka naturalnego z podziałem na warstwy przetwarzania. Omawia też zagadnienie jakości przetwarzania na przykładzie poprawiania błędów i optymalizacji reguł.

  • Smaller Representation of Finite State Automata
    Publication

    This 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%...

    Full text to download in external service

Year 2010
  • Natural language dictionaries implemented as finite automata
    Publication

    - Year 2010

    Rozdział 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.

    Full text to download in external service

Year 2009
  • A perfect hashing incremental scheme for unranked trees using pseudo-minimal automata
    Publication

    We describe a technique that maps unranked trees to arbitrary hash codes using a bottom-up deterministic tree automaton (DTA). In contrast to other hashing techniques based on automata, our procedure builds a pseudo-minimal DTA for this purpose. A pseudo-minimal automaton may be larger than the minimal one accepting the same language but, in turn, it contains proper elements (states or transitions that are unique) for every input...

    Full text to download in external service

  • Incremental construction of Minimal Tree Automata [online]
    Publication

    - ALGORITHMICA - Year 2009

    We describe an algorithm that allows the incremental addition or removal of unranked ordered trees to minimal frontier-to-root deterministic tree automaton (DTA). The algorithm takes a tree t and a minimal DTA A as input; it outputs a minimal DTA A' which accepts the language L(A) accepted by A incremented (or decremented) with the tree t. The algorithm can be used to efficiently maintain dictionaries which store large collections...

    Full text to download in external service

Year 2008
  • Perfect hashing tree automata
    Publication

    - Year 2008

    We present an algorithm that computes a function that assigns consecutive integers to trees recognized by a deterministic, acyclic, finite-state, bottom-up tree automaton. Such function is called minimal perfect hashing. It can be used to identify trees recognized by the automaton. Its value may be seen as an index in some other data structures. We also present an algorithm for inverted hashing.Przedstawiamy algorytm, który oblicza...

    Full text to download in external service

  • Perfect hashing with pseudo-minimal bottom-up deterministic tree automata
    Publication

    - Year 2008

    We describe a technique that maps unranked trees to their hash codes using a bottom-up deterministic tree automaton (DTA). In contrast to techniques implemented with minimal tree automata, our procedure builds a pseudo-minimal DTA. Pseudo-minimal automata are larger than the minimal ones but in turn the mapping can be arbitrary, so it can be determined prior to the automaton construction. We also provide procedures to build incrementally...

Year 2007
  • An implementation of deterministic tree automata minimization
    Publication

    - Year 2007

    Wstę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....

Year 2006
  • Gazetteer compression technique based on substructure recognition
    Publication

    - Year 2006

    Automaty 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...

    Full text to download in external service

  • Incremental and pseudo-incremental construction of pseudo-minimal automata.
    Publication

    - Year 2006

    Automaty 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.

    Full text to download in external service

  • Les transducteurs à sorties variables
    Publication

    - Year 2006

    W 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...

    Full text to download in external service

Year 2005
  • Dynamic Perfect hashing with finite-state automata
    Publication

    - Year 2005

    Minimalna 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....

  • Incremental and Semi-Incremental Construction of Pseudo-Minimal Automata
    Publication

    - Year 2005

    Przedstawione 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....

Year 2004
  • Comments on ''Incremental construction and maintenance of minimal finite-state automata'' by Rafael C. Carrasco and Mikel L. Forcada.
    Publication

    - Year 2004

    W opublikowanym niedawno artykule (czerwiec 2002) Rafael Carrasco i Mikel Forcada przedstawili dwa algorytmy: jeden dotyczący przyrostowego dodawania łańcuchów znaków do języka minimalnego, deterministycznego, cyklicznego automatu skończonego, drugi dotyczący przyrostowego usuwania łańcuchów znaków z automatu. Pierwszy algorytm jest uogólnieniem ,,algorytmu dla danych nieuporządkowanych'' - drugiego z dwóch przyrostowych algorytmów...

  • Extension of selected ADFA construction algorithms to the case of cyclic automata.
    Publication

    - Year 2004

    W 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 tuple dictionaries.
    Publication

    - THEORETICAL COMPUTER SCIENCE - Year 2004

    Opisane 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...

    Full text available to download

  • Finite-state lexical tools
    Publication

    - Year 2004

    Artykuł 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...

  • Semi-incremental addition of strings to a cyclic finite automaton
    Publication

    - Year 2004

    Maszyny 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...

Year 2003
Year 2002
  • Finite automata for compact representation of language models in NLP
    Publication

    Przedstawiona 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...

seen 2644 times