matriz sufixo comprimido - Compressed suffix array

Em ciência da computação , um array de sufixos comprimido é uma estrutura de dados comprimidos para correspondência de padrões . Arranjos de sufixos comprimidos são uma classe geral de estrutura de dados que melhorar a matriz sufixo . Estas estruturas de dados habilitar a pesquisa rápida para uma arbitrária corda com um relativamente pequeno índice.

Dado um texto T de n caracteres de uma Σ alfabeto, uma matriz sufixo comprimido suporta busca de padrões arbitrários em T . Para um teste padrão de entrada P de m caracteres, o tempo de busca é, tipicamente, O ( m ) ou O ( m + log ( n )). O espaço utilizado é tipicamente , onde é a ordem entropia empírica k-th de texto a t . O tempo e espaço para a construção de uma matriz de comprimido sufixo são normalmente .

A instanciação original do array de sufixos comprimido resolveu um problema de longa data aberta, mostrando que a correspondência de padrão rápido era possível usando apenas uma estrutura de dados-espaço linear, ou seja, um proporcional ao tamanho do texto T , que leva pedaços. A matriz convencional sufixo e árvore de sufixos de uso de bits, o que é substancialmente maior. A base para a estrutura de dados é uma decomposição recursiva usando a "função vizinho", que permite que uma matriz de sufixo para ser representado por um de metade do seu comprimento. A construção é repetido várias vezes até que a matriz sufixo resultante utiliza uma série linear de bits. Na sequência dos trabalhos mostraram que o espaço de armazenamento real estava relacionada com a entropia de ordem zero e que o índice suporta auto-indexação. O espaço ligado foi ainda melhorada alcançar o objectivo final de entropia de ordem superior; a compressão é obtido dividindo a função vizinho por contextos de ordem elevada, e comprimindo cada partição com uma árvore de onda . O uso do espaço é extremamente competitivo em prática com outros compressores state-of-the-art, e também suporta correspondência de padrão rápido.

A memória acessos feitos por arranjos de sufixos comprimido e outras estruturas de dados compactados para correspondência de padrões tipicamente não são localizados, e estruturas, assim, estes dados têm sido notoriamente difícil de projetar de forma eficiente para uso em memória externa . Progressos recentes usando dualidade geométrica aproveita a bloquear o acesso fornecido pelo discos para acelerar o tempo de I / O significativamente Além disso, o desempenho da pesquisa potencialmente prático para um array de sufixos comprimido na memória externa foi demonstrada.

Implementações Open Source

Existem várias implementações de código aberto de arranjos de sufixos comprimido disponíveis (ver links externos abaixo). Gravata-borboleta e Bowtie2 são-fonte aberto comprimidos de matriz de sufixo implementações de alinhamento ler para utilização em bioinformática . A estrutura da biblioteca de dados sucinta (SDSL) é uma biblioteca contendo uma variedade de estruturas de dados comprimidos, incluindo arranjos de sufixos comprimido. FEMTO é uma implementação de arranjos de sufixos comprimido para memória externa. Além disso, uma variedade de implementações, incluindo os originais a índices de FM implementações, estão disponíveis no site Pizza & Chili (veja as ligações externas).

Veja também

Referências

  1. ^ Uma b c R. Grossi e JS Vitter, compactados Sufixo matrizes e Sufixo árvores, com aplicações em texto de indexação e cadeia correspondente, SIAM Journal na Computing, 35 (2), 2005, 378-407. Uma versão anterior apareceu em Proceedings da ACM Symposium 32 em Teoria da Computação, maio de 2000, 397-406.
  2. ^ Um b Paolo Ferragina e Giovanni Manzini (2000). "Estruturas oportunista dados com aplicações". Anais do Simpósio Anual 41 sobre Fundamentos da ciência da computação. p.390.
  3. ^ Um b R. Grossi, A. Gupta, e JS Vitter, High-Order Entropy-comprimido índices de texto, Anais da 14ª SIAM / Simpósio Anual sobre Discrete Algoritmos, ACM Janeiro de 2003, 841-850.
  4. ^ K. Sadakane, bancos de dados de texto compactado com Eficiente consulta algoritmos baseados na Compressed Sufixo Arrays, Actas do Simpósio Internacional de Algoritmos e Computação , Lecture Notes in Computer Science, vol. 1969, Springer, Dezembro de 2000, 410-421.
  5. ^ L. Foschini, R. Grossi, R. Gupta, e JS Vitter, indexação iguala Compressão: Experiências sobre Sufixo Arrays e árvores , ACM Transactions em algoritmos , 2 (4), 2006, 611-639.
  6. ^ W.-K. Hon, R. Shah, SV Thankachan, e JS Vitter, On indexação de texto Entropy-comprimido em memória externa, Anais da Conferência sobre Processamento de Cordas e Recuperação de Informações , agosto de 2009.
  7. ^ MP Ferguson, FEMTO: busca rápida de grandes coleções de seqüência , Anais da Conferência Anual 23 em Combinatória Matching Padrão , julho 2012

links externos

implementações: