Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagrams
Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagrams
复制标题
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Shuhei Denzumi;K. Tsuda;Hiroki Arimura;S. Minato
中科院分区：
文献类型：
--
作者：
Shuhei Denzumi;K. Tsuda;Hiroki Arimura;S. Minato
完整的反向文件是一种抽象数据类型，提供文本检索功能。使用它，我们可以检索给定文本的字符串的频率和出现次数。有各种完整的文本倒置文件。然而，对于图的完全倒置文件还没有研究。在有向无环图（DAG）中，我们定义了基于序列二进制决策图（SDD）的完全倒立文件。给出了有向无环图作为序列二值决策图的形式。我们分别为文本和DAG提出了新的完整倒置文件PosFSDD和PosFSDDdag。我们还提出了构造它们和从中检索发生信息的算法。通过计算实验验证了postfsdds的有效性。
A complete inverted file is an abstract data type that provides functions for text retrieval. Using it, we can retrieve frequencies and occurrences of strings for given texts. There have been various complete inverted files for texts. However, complete inverted files for graphs have not been studied. In this paper, we define complete inverted files based on sequence binary decision diagrams (SDD) for directed acyclic graphs (DAG). Directed acyclic graphs are given as sequence binary decision diagrams. We propose new complete inverted files called PosFSDD and PosFSDDdag for a text and a DAG, respectively. We also present algorithms to construct them and to retrieve occurrence information from them. Computational experiments are executed to show the efficiency of PosFSDDs.