| dbo:abstract
|
- Sufixový strom je speciální druh trie, která uchovává všechny sufixy (podřetězce od nějakého znaku až do konce) nějakého řetězce. Každý vnitřní vrchol odpovídá prefixu nějakého sufixu, tedy nějakému podslovu. Je-li tato trie komprimovaná (cesty ve stromu jsou nahrazeny hranou), dá se reprezentovat v prostoru lineárním k délce řetězce. Existují algoritmy pro postavení sufixového stromu v lineárním čase. Sufixový strom umožňuje rychle řešit řadu řetězcových úloh, například , hledání nejdelšího opakujícího se podslova nebo Burrowsovu-Wheelerovu transformaci. (cs)
- Ein Suffixbaum ist eine vielseitige Datenstruktur, die effiziente Lösungen zahlreicher Probleme im Bereichder Stringverarbeitung ermöglicht. Ein Suffixbaum speichert alle Suffixe (Endungen) einer Zeichenkette. Er kann in linearer Zeit mit linearem Speicherverbrauch aufgebaut werden und ermöglicht, einmal aufgebaut, das schnelle Durchführen vieler Operationen wie zum Beispiel die Suche nach Wörtern oder Sätzen in längeren Texten. (de)
- En informatique, un arbre des suffixes (en anglais suffix tree) est une structure de données arborescente contenant tous les suffixes d'un texte. L'arbre des suffixes est utilisé pour l'indexation de textes et la recherche de motifs, notamment en bio-informatique. (fr)
- Dalam ilmu komputer, sebuah pohon sufiks (juga dinamakan pohon PAT atau dalam bentuk awalnya, pohon posisi) adalah suatu struktur data tertentu yang menggambarkan dari string yang diberikan melalui sebuah cara yang memperbolehkan sebuah implementasi yang cepat dari banyak operasi string yang penting.
* l
*
* s (in)
- In computer science, a suffix tree (also called PAT tree or, in an earlier form, position tree) is a compressed trie containing all the suffixes of the given text as their keys and positions in the text as their values. Suffix trees allow particularly fast implementations of many important string operations. The construction of such a tree for the string takes time and space linear in the length of . Once constructed, several operations can be performed quickly, for instance locating a substring in , locating a substring if a certain number of mistakes are allowed, locating matches for a regular expression pattern etc. Suffix trees also provide one of the first linear-time solutions for the longest common substring problem. These speedups come at a cost: storing a string's suffix tree typically requires significantly more space than storing the string itself. (en)
- Un albero dei suffissi (suffix tree in inglese) è una struttura dati che evidenzia la struttura interna di una stringa in un modo da facilitare operazioni comuni come la ricerca di sottostringhe. Gli alberi dei suffissi permettono di risolvere il problema del in tempo lineare (al pari di altri algoritmi come Knuth-Morris-Pratt, Boyer-Moore...) ma la loro principale virtù è che essi possono essere usati per risolvere in tempo lineare molti altri problemi più complessi del pattern matching esatto. L'applicazione classica degli alberi dei suffissi è il problema della sottostringa: dato un testo T di lunghezza n, dopo una preelaborazione del testo (costruzione dell'albero dei suffissi) che richiede tempo , è possibile rispondere in tempo alla domanda se una stringa S di lunghezza m compare in T. In altre parole, la preelaborazione del testo richiede tempo proporzionale alla sua lunghezza n ma dopo tale preelaborazione ogni ricerca nel testo T di una stringa S richiede soltanto tempo proporzionale alla lunghezza m della stringa cercata indipendentemente dalla lunghezza n del testo T. (it)
- 接尾辞木（せつびじき）またはサフィックス木（英: Suffix tree）は、与えられた文字列の接尾部を木構造(基数木)で表すデータ構造であり、多くの文字列操作の高速な実装に利用されている。 文字列 の接尾辞木は木構造であり、その枝には文字列が対応し、木構造の根から葉までの経路ごとにそれぞれ の接尾部の1つが対応している。従って、これは の接尾部に関する基数木である。 文字列 からそのような木構造を構築するには、 の長さに対して線形な時間と空間を要する。構築できれば、いくつかの操作が高速化される（ の部分文字列を探す、誤字をある程度許容した上での部分文字列特定、正規表現パターンとのマッチングなど）。接尾辞木は問題の線形な解法の1つでもある。これらの高速化の代償として、接尾辞木に要するメモリ空間は文字列そのものを格納するのに要するメモリ空間よりもかなり大きくなる。 (ja)
- Drzewo sufiksowe – struktura danych reprezentująca zbiór sufiksów danego ciągu znaków w sposób umożliwiający efektywne wykonywanie wielu istotnych operacji na łańcuchach znaków. (pl)
- Суффиксное дерево — бор, содержащий все суффиксы некоторой строки (и только их). Позволяет выяснять, входит ли строка w в исходную строку t, за время O(|w|), где |w| — длина строки w. (ru)
- Em ciência da computação, uma árvore de sufixos (também chamada árvore PAT ou, na forma anterior, árvore de posições) é uma trie comprimida, contendo todos os de um dado texto, assim como suas chaves e posições no texto como seus valores. Árvores de sufixo permitem uma implementação particularmente rápida de muitas operações importantes com strings. A construção de tal árvore para uma string leva tempo e espaço lineares no tamanho de . Uma vez construída, muitas operações podem ser realizadas rapidamente, por exemplo, localizar uma em , localizar uma substring se um certo número de erros for permitido, localizar acertos para uma expressão regular etc. Árvores de sufixo também proveem uma das primeiras soluções em tempo linear para o . Estes ganhos de velocidade vem com um custo: armazenar uma árvore de sufixos de uma string tipicamente requer significativamente mais espaço do que armazenar a própria string. (pt)
- Суфіксне дерево — основана на дереві структура даних. Знаходить застосування в алгоритмах на рядках. (uk)
- 后缀树（Suffix tree）是一种数据结构，能快速解决很多关于字符串的问题。后缀樹的概念最早由Weiner於1973年提出，既而由McCreight在1976年和Ukkonen在1992年和1995年加以改進完善。 一个string S的后缀树是一个边（edge）被标记为字符串的树。因此每一个S的后缀都唯一对应一条从根节点到叶节点的路径。这样就形成了一个S的后缀的基数树（radix tree）。后缀树是前缀树（trie）里的一个特殊类型。 (zh)
|
| rdfs:comment
|
- Sufixový strom je speciální druh trie, která uchovává všechny sufixy (podřetězce od nějakého znaku až do konce) nějakého řetězce. Každý vnitřní vrchol odpovídá prefixu nějakého sufixu, tedy nějakému podslovu. Je-li tato trie komprimovaná (cesty ve stromu jsou nahrazeny hranou), dá se reprezentovat v prostoru lineárním k délce řetězce. Existují algoritmy pro postavení sufixového stromu v lineárním čase. Sufixový strom umožňuje rychle řešit řadu řetězcových úloh, například , hledání nejdelšího opakujícího se podslova nebo Burrowsovu-Wheelerovu transformaci. (cs)
- Ein Suffixbaum ist eine vielseitige Datenstruktur, die effiziente Lösungen zahlreicher Probleme im Bereichder Stringverarbeitung ermöglicht. Ein Suffixbaum speichert alle Suffixe (Endungen) einer Zeichenkette. Er kann in linearer Zeit mit linearem Speicherverbrauch aufgebaut werden und ermöglicht, einmal aufgebaut, das schnelle Durchführen vieler Operationen wie zum Beispiel die Suche nach Wörtern oder Sätzen in längeren Texten. (de)
- En informatique, un arbre des suffixes (en anglais suffix tree) est une structure de données arborescente contenant tous les suffixes d'un texte. L'arbre des suffixes est utilisé pour l'indexation de textes et la recherche de motifs, notamment en bio-informatique. (fr)
- Dalam ilmu komputer, sebuah pohon sufiks (juga dinamakan pohon PAT atau dalam bentuk awalnya, pohon posisi) adalah suatu struktur data tertentu yang menggambarkan dari string yang diberikan melalui sebuah cara yang memperbolehkan sebuah implementasi yang cepat dari banyak operasi string yang penting.
* l
*
* s (in)
- 接尾辞木（せつびじき）またはサフィックス木（英: Suffix tree）は、与えられた文字列の接尾部を木構造(基数木)で表すデータ構造であり、多くの文字列操作の高速な実装に利用されている。 文字列 の接尾辞木は木構造であり、その枝には文字列が対応し、木構造の根から葉までの経路ごとにそれぞれ の接尾部の1つが対応している。従って、これは の接尾部に関する基数木である。 文字列 からそのような木構造を構築するには、 の長さに対して線形な時間と空間を要する。構築できれば、いくつかの操作が高速化される（ の部分文字列を探す、誤字をある程度許容した上での部分文字列特定、正規表現パターンとのマッチングなど）。接尾辞木は問題の線形な解法の1つでもある。これらの高速化の代償として、接尾辞木に要するメモリ空間は文字列そのものを格納するのに要するメモリ空間よりもかなり大きくなる。 (ja)
- Drzewo sufiksowe – struktura danych reprezentująca zbiór sufiksów danego ciągu znaków w sposób umożliwiający efektywne wykonywanie wielu istotnych operacji na łańcuchach znaków. (pl)
- Суффиксное дерево — бор, содержащий все суффиксы некоторой строки (и только их). Позволяет выяснять, входит ли строка w в исходную строку t, за время O(|w|), где |w| — длина строки w. (ru)
- Суфіксне дерево — основана на дереві структура даних. Знаходить застосування в алгоритмах на рядках. (uk)
- 后缀树（Suffix tree）是一种数据结构，能快速解决很多关于字符串的问题。后缀樹的概念最早由Weiner於1973年提出，既而由McCreight在1976年和Ukkonen在1992年和1995年加以改進完善。 一个string S的后缀树是一个边（edge）被标记为字符串的树。因此每一个S的后缀都唯一对应一条从根节点到叶节点的路径。这样就形成了一个S的后缀的基数树（radix tree）。后缀树是前缀树（trie）里的一个特殊类型。 (zh)
- In computer science, a suffix tree (also called PAT tree or, in an earlier form, position tree) is a compressed trie containing all the suffixes of the given text as their keys and positions in the text as their values. Suffix trees allow particularly fast implementations of many important string operations. (en)
- Un albero dei suffissi (suffix tree in inglese) è una struttura dati che evidenzia la struttura interna di una stringa in un modo da facilitare operazioni comuni come la ricerca di sottostringhe. Gli alberi dei suffissi permettono di risolvere il problema del in tempo lineare (al pari di altri algoritmi come Knuth-Morris-Pratt, Boyer-Moore...) ma la loro principale virtù è che essi possono essere usati per risolvere in tempo lineare molti altri problemi più complessi del pattern matching esatto. (it)
- Em ciência da computação, uma árvore de sufixos (também chamada árvore PAT ou, na forma anterior, árvore de posições) é uma trie comprimida, contendo todos os de um dado texto, assim como suas chaves e posições no texto como seus valores. Árvores de sufixo permitem uma implementação particularmente rápida de muitas operações importantes com strings. (pt)
|
