论文标题
AWLCO：全窗口长度共同出现
AWLCO: All-Window Length Co-Occurrence
论文作者
论文摘要
一系列事件中的分析模式在文本分析，计算机编程和基因组学研究中应用。在本文中，我们考虑了全窗口长度分析模型，该模型分析了各个长度窗口的一系列事件。我们研究了全壁窗格分析模型的确切共同计数问题。我们的第一种算法是一种离线算法，该算法通过对序列进行多个通过并计算单窗口长度的共发生来计算全窗口长度的共发生。该算法具有每个窗口长度的时间复杂性$ O（n）$，因此总复杂度为$ O（n^2）$，而空间复杂度$ O（| i |）$对于尺寸n的顺序和大小$ | i | $的项目集。我们提出了AWLCO，这是一种在线算法，该算法在单个通行证中计算全窗口长度的共发生，预期的时间复杂度为$ O（n）$，而空间复杂性则为$ O（\ sqrt {n | i |}）$。之后，我们将用例概括为模式，我们提出了一种算法，该算法与预期的时间复杂性$ o（n | i |）$和空间复杂性$ o（\ sqrt {n | i | i | i | i |} + e _ {max} | i | i | i | e_ max} $ rangige是a rar far far fartime
Analyzing patterns in a sequence of events has applications in text analysis, computer programming, and genomics research. In this paper, we consider the all-window-length analysis model which analyzes a sequence of events with respect to windows of all lengths. We study the exact co-occurrence counting problem for the all-window-length analysis model. Our first algorithm is an offline algorithm that counts all-window-length co-occurrences by performing multiple passes over a sequence and computing single-window-length co-occurrences. This algorithm has the time complexity $O(n)$ for each window length and thus a total complexity of $O(n^2)$ and the space complexity $O(|I|)$ for a sequence of size n and an itemset of size $|I|$. We propose AWLCO, an online algorithm that computes all-window-length co-occurrences in a single pass with the expected time complexity of $O(n)$ and space complexity of $O( \sqrt{ n|I| })$. Following this, we generalize our use case to patterns in which we propose an algorithm that computes all-window-length co-occurrence with expected time complexity $O(n|I|)$ and space complexity $O( \sqrt{n|I|} + e_{max}|I|)$, where $e_{max}$ is the length of the largest pattern.
