对于Wheeler DFAs的LCP阵列的时空权衡
Nicola Cotumaccio1,2, Travis Gagie2, Dominik Köppl3
1GSSI, Italy.
International Symposium on String Processing and Information Retrieval : SPIRE ... : proceedings. SPIRE (Symposium)
|August 7, 2024
概括
我们介绍了一种新的采样技术,用于Wheeler决定性有限自动机 (DFAs) 上的最长共同前 (LCP) 数组. 这种方法可实现高效的LCP数组访问,减少空间复杂性,改善匹配统计计算.
科学领域:
- 理论计算机科学 理论计算机科学
- 数据结构和算法数据结构和算法
- 弦学和自动机理论
背景情况:
- 对于字符串处理至关重要的最长常见前 (LCP) 阵列已被泛化为惠勒决定性有限自动机 (DFAs).
- 对于Wheeler DFAs而言,现有的LCP阵列存储需要O (n) 位,与BOSS.等紧的DFA表示相比,这可能是空间效率低下的.
- 由于LCP阵列的空间需求,Wheeler DFAs上的匹配统计数据的有效计算受到阻碍.
研究的目的:
- 开发一个空间效率高的方法来访问Wheeler DFAs中的LCP阵列条目.
- 为了建立一个时空权衡,计算惠勒DFAs的匹配统计数据.
- 通过使用增强的BOSS表示来提高导航变量级de Bruijn图的时间复杂性.
主要方法:
- 提出了一种新型采样技术,使得对LCP数组条目的对数时间访问成为可能.
- 这种技术只需要线性数量的比特来存储,大大减少了空间复杂性.
- 增强了de Bruijn图的BOSS表示,以实现变量顺序de Bruijn图的更快的导航.
主要成果:
- 拟议的采样技术允许LCP数组在O (log n) 时间内访问,同时只使用O (log n) 位空间.
- 在计算惠勒DFAs匹配统计数据时,实现了一个新的时空权衡.
- 变量级de Bruijn图的导航得到了改进,达到n的对数时间复杂度,超过了以前的线性边界.
结论:
- 开发的采样技术为惠勒DFA中空间效率高的LCP阵列管理提供了实用解决方案.
- 这项研究在计算匹配统计和导航de Bruijn图表方面取得了重大改进.
- 这些发现有助于开发用于自动机和图表表示的更紧和更快的数据结构.
相关概念视频
01:10Interference: Path Lengths
1.3K
Consider two sources of sound, that may or may not be in phase, emitting waves at a single frequency, and consider the frequencies to be the same.
Two special sources may be considered when they are in phase. This can be easily achieved by feeding the two sources from the same source. An example would be synchronizing the two speakers by feeding them with the same source, such as the sound waves produced by a tuning fork. This setup ensures that the two sources have the same frequency and are...
Two special sources may be considered when they are in phase. This can be easily achieved by feeding the two sources from the same source. An example would be synchronizing the two speakers by feeding them with the same source, such as the sound waves produced by a tuning fork. This setup ensures that the two sources have the same frequency and are...
1.3K
01:20Discrete-Time Fourier Series
241
The Discrete-Time Fourier Series (DTFS) is a fundamental concept in signal processing, serving as the discrete-time counterpart to the continuous-time Fourier series. It allows for the representation and analysis of discrete-time periodic signals in terms of their frequency components. Unlike its continuous counterpart, which utilizes integrals, the calculation of DTFS expansion coefficients involves summations due to the discrete nature of the signal.
For a discrete-time periodic signal x[n]...
For a discrete-time periodic signal x[n]...
241
01:10Fast Fourier Transform
290
The Fast Fourier Transform (FFT) is a computational algorithm designed to compute the Discrete Fourier Transform (DFT) efficiently. By breaking down the calculations into smaller, manageable sections, the FFT significantly reduces the computational complexity involved. Direct computation of an N-point DFT requires N2 complex multiplications, whereas the FFT algorithm needs only (N/2)log2N multiplications, offering a much faster performance.
The computational efficiency of the FFT becomes...
The computational efficiency of the FFT becomes...
290
01:24Properties of DTFT I
383
In signal processing, Discrete-Time Fourier Transforms (DTFTs) play a critical role in analyzing discrete-time signals in the frequency domain. Various properties of the DTFTs such as linearity, time-shifting, frequency-shifting, time reversal, conjugation, and time scaling help understand and manipulate these signals for different applications.
The linearity property of DTFTs is fundamental. If two discrete-time signals are multiplied by constants a and b respectively, and then combined to...
The linearity property of DTFTs is fundamental. If two discrete-time signals are multiplied by constants a and b respectively, and then combined to...
383