FM-index

http://dbpedia.org/resource/FM-index an entity of type: Work

In computer science, an FM-index is a compressed full-text substring index based on the Burrows–Wheeler transform, with some similarities to the suffix array. It was created by Paolo Ferragina and Giovanni Manzini, who describe it as an opportunistic data structure as it allows compression of the input text while still permitting fast substring queries. The name stands for Full-text index in Minute space. The FM-index has found use in, among other places, bioinformatics. rdf:langString
En informatique, un FM-index est une structure d'indexation compressée sans perte, fondée sur la Transformée de Burrows-Wheeler, qui a des similitudes avec le tableau des suffixes. Cette structure de données a été créée par Paolo Ferragina et Giovanni Manzini, qui la décrivent comme étant un index multi-usages basé sur une structure de donnée astucieuse. Le nom signifie « Full-text index in Minute space ». Le FM-index a été utilisé entre autres en bio-informatique. rdf:langString
rdf:langString FM-index
rdf:langString FM-index
xsd:integer 22143928
xsd:integer 1076478286
rdf:langString In computer science, an FM-index is a compressed full-text substring index based on the Burrows–Wheeler transform, with some similarities to the suffix array. It was created by Paolo Ferragina and Giovanni Manzini, who describe it as an opportunistic data structure as it allows compression of the input text while still permitting fast substring queries. The name stands for Full-text index in Minute space. It can be used to efficiently find the number of occurrences of a pattern within the compressed text, as well as locate the position of each occurrence. The query time, as well as the required storage space, has a sublinear complexity with respect to the size of the input data. The original authors have devised improvements to their original approach and dubbed it "FM-Index version 2". A further improvement, the alphabet-friendly FM-index, combines the use of compression boosting and wavelet trees to significantly reduce the space usage for large alphabets. The FM-index has found use in, among other places, bioinformatics.
rdf:langString En informatique, un FM-index est une structure d'indexation compressée sans perte, fondée sur la Transformée de Burrows-Wheeler, qui a des similitudes avec le tableau des suffixes. Cette structure de données a été créée par Paolo Ferragina et Giovanni Manzini, qui la décrivent comme étant un index multi-usages basé sur une structure de donnée astucieuse. Le nom signifie « Full-text index in Minute space ». Cet index peut, en plus de la compression, être utilisé pour trouver de façon efficace le nombre d’occurrences d’un motif dans le texte compressé, ainsi que pour localiser la position de chaque occurrence du mot recherché dans le texte compressé. Aussi bien le temps que l'espace de stockage requis ont une complexité sublinéaire par rapport à la taille des données d’entrée. C'est-à-dire que le temps d'exécution et l'espace de stockage requis ne sont pas proportionnels à la taille des données d'entrée. Le FM-index a été utilisé entre autres en bio-informatique.
xsd:nonNegativeInteger 10438

data from the linked data cloud