| dbo:abstract
|
- In computer science, a suffix automaton is an efficient data structure for representing the substring index of a given string which allows the storage, processing, and retrieval of compressed information about all its substrings. The suffix automaton of a string is the smallest directed acyclic graph with a dedicated initial vertex and a set of "final" vertices, such that paths from the initial vertex to final vertices represent the suffixes of the string. In terms of automata theory, a suffix automaton is the minimal partial deterministic finite automaton that recognizes the set of suffixes of a given string . The state graph of a suffix automaton is called a directed acyclic word graph (DAWG), a term that is also sometimes used for any deterministic acyclic finite state automaton. Suffix automata were introduced in 1983 by a group of scientists from the University of Denver and the University of Colorado Boulder. They suggested a linear time online algorithm for its construction and showed that the suffix automaton of a string having length at least two characters has at most states and at most transitions. Further works have shown a close connection between suffix automata and suffix trees, and have outlined several generalizations of suffix automata, such as compacted suffix automaton obtained by compression of nodes with a single outgoing arc. Suffix automata provide efficient solutions to problems such as substring search and computation of the largest common substring of two and more strings. (en)
- 接尾辞オートマトン（せつびじオートマトン、英: suffix automaton）や有向非巡回文字列グラフ（ゆうこうひじゅんかいもじれつグラフ、英: directed acyclic word graph）とは、接尾辞を効率的に表現するデータ構造。接尾辞木や接尾辞配列と同様に、suffix という文字列に対して構築した場合、suffix, uffix, ffix, fix, ix, x が含まれている事、それ以外が含まれていない事が分かる。文字列の集合 U の接尾辞オートマトンは、Q を U を表現するトライ木のノードすると、最大 2Q - 2 個の状態がある。 接尾辞オートマトンは有限オートマトンの一種である。圧縮接尾辞木と解釈できる。 (ja)
- Су́ффиксный автома́т (англ. suffix automaton, directed acyclic word graph) — структура данных, позволяющая хранить в сжатом виде и обрабатывать информацию, связанную с подстроками данной строки. Представляет собой детерминированный конечный автомат, принимающий все суффиксы слова и только их, и обладающий наименьшим возможным числом состояний среди всех таких автоматов. Менее формально, суффиксный автомат — это ориентированный ациклический граф с выделенной начальной вершиной и набором «финальных» вершин, дуги которого помечены символами, такой что у любой вершины символы на исходящих из неё дугах попарно различны и для любого суффикса слова существует путь из начальной вершины в некоторую финальную вершину, символы на котором при конкатенации образуют данный суффикс. Из всех графов, удовлетворяющих данному описанию, суффиксным автоматом называется тот, который обладает наименьшим возможным числом вершин. Суффиксный автомат был впервые описан группой учёных из Денверского и Колорадского университетов в 1983 году, они же показали, что размер автомата линейно зависит от длины , а также предложили для его построения с линейным временем работы. В дальнейших работах на эту тему была обнаружена тесная связь суффиксного автомата с суффиксными деревьями, а сама концепция суффиксного автомата получила различные обобщения. Так были введены сжатый суффиксный автомат, получаемый из исходного процедурой, аналогичной той, которая применяется к суффиксному бору для получения суффиксного дерева, а также обобщённый суффиксный автомат, который строится для набора слов и принимает слова, являющиеся суффиксами хотя бы одного из данных. С помощью суффиксного автомата можно эффективно решать такие задачи как поиск подстроки в строке, определение наибольшей общей подстроки двух и более строк и другие. (ru)
- Су́фіксний автома́т (англ. suffix automaton, directed acyclic word graph) — структура даних, що дозволяє зберігати в стислому вигляді і обробляти інформацію, пов'язану з підрядками одного рядка. Є детермінованим скінченним автоматом, який приймає всі суфікси слова і тільки їх, і що має найменшу можливу кількість станів серед всіх таких автоматів. Менш формально, суфіксний автомат — це орієнтований ациклічний граф з виділеною початковою вершиною і набором «фінальних» вершин, дуги якого позначені символами, такий що у будь-якої вершини символи на вихідних з неї дугах попарно різні і для будь-якого суфікса слова існує шлях з початкової вершини в деяку фінальну вершину, символи на якому при конкатенації утворюють даний суфікс. З усіх графів, які відповідають даним опису, суффіксним автоматом називається той, який володіє найменшим можливим числом вершин. Суфіксний автомат був вперше описаний групою вчених з Денверського і Колорадського університетів в 1983 році, вони ж показали, що розмір автомата лінійно залежить від довжини , а також запропонували онлайн алгоритм для його побудови з лінійним часом роботи. У подальших роботах на цю тему був виявлений тісний зв'язок суфіксного автомата з суфікснимі деревами, а сама концепція суфіксного автомата отримала різні узагальнення. Так були введені стислий суфіксний автомат, який отримують із вихідного процедурою, аналогічною тій, яка застосовується до префіксного дерева для отримання суфіксного дерева, а також узагальнений суфіксний автомат, який будується для набору слів і приймає слова, які є суфіксами хоча б одного з цих. За допомогою суфіксного автомата можна ефективно розв'зувати такі задачі як пошук підрядка в рядку, визначення найдовшого спільного підрядка двох і більше рядків тощо. (uk)
|
| rdfs:comment
|
- 接尾辞オートマトン（せつびじオートマトン、英: suffix automaton）や有向非巡回文字列グラフ（ゆうこうひじゅんかいもじれつグラフ、英: directed acyclic word graph）とは、接尾辞を効率的に表現するデータ構造。接尾辞木や接尾辞配列と同様に、suffix という文字列に対して構築した場合、suffix, uffix, ffix, fix, ix, x が含まれている事、それ以外が含まれていない事が分かる。文字列の集合 U の接尾辞オートマトンは、Q を U を表現するトライ木のノードすると、最大 2Q - 2 個の状態がある。 接尾辞オートマトンは有限オートマトンの一種である。圧縮接尾辞木と解釈できる。 (ja)
- In computer science, a suffix automaton is an efficient data structure for representing the substring index of a given string which allows the storage, processing, and retrieval of compressed information about all its substrings. The suffix automaton of a string is the smallest directed acyclic graph with a dedicated initial vertex and a set of "final" vertices, such that paths from the initial vertex to final vertices represent the suffixes of the string. (en)
- Су́ффиксный автома́т (англ. suffix automaton, directed acyclic word graph) — структура данных, позволяющая хранить в сжатом виде и обрабатывать информацию, связанную с подстроками данной строки. Представляет собой детерминированный конечный автомат, принимающий все суффиксы слова и только их, и обладающий наименьшим возможным числом состояний среди всех таких автоматов. Менее формально, суффиксный автомат — это ориентированный ациклический граф с выделенной начальной вершиной и набором «финальных» вершин, дуги которого помечены символами, такой что у любой вершины символы на исходящих из неё дугах попарно различны и для любого суффикса слова существует путь из начальной вершины в некоторую финальную вершину, символы на котором при конкатенации образуют данный суффикс. Из всех графов, удо (ru)
- Су́фіксний автома́т (англ. suffix automaton, directed acyclic word graph) — структура даних, що дозволяє зберігати в стислому вигляді і обробляти інформацію, пов'язану з підрядками одного рядка. Є детермінованим скінченним автоматом, який приймає всі суфікси слова і тільки їх, і що має найменшу можливу кількість станів серед всіх таких автоматів. Менш формально, суфіксний автомат — це орієнтований ациклічний граф з виділеною початковою вершиною і набором «фінальних» вершин, дуги якого позначені символами, такий що у будь-якої вершини символи на вихідних з неї дугах попарно різні і для будь-якого суфікса слова існує шлях з початкової вершини в деяку фінальну вершину, символи на якому при конкатенації утворюють даний суфікс. З усіх графів, які відповідають даним опису, суффіксним автоматом (uk)
|
