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)
|