Succinct data structures for flexible text retrieval systems
Succinct data structures for flexible text retrieval systems
复制标题
DOI：
10.1016/j.jda.2006.03.011
复制
发表时间：
2007-03
期刊：
影响因子：
--
通讯作者：
K. Sadakane
中科院分区：
文献类型：
--
作者：
K. Sadakane
我们提出了简洁的数据结构的文本检索系统，支持文档列表查询和排名查询的基础上的tf*idf（词频倍逆文档频率）分数的文件。针对这些问题的传统数据结构只支持对某些预定义关键字的查询。最近，Muthukrishnan提出了一种数据结构，用于以数据结构大小为代价的任意模式的文档列表查询。对于计算tf*idf分数，没有针对任意模式的有效数据结构。我们的新数据结构使用小空间支持这些查询。对于长度为n的文档集合，对于任何0<10 n <1，该空间仅为压缩文档大小的2/100倍加上10 n位。这比以前的O（nlogn）位数据结构小得多。查询时间是O（m+qlog n），用于列出和计算所有q个包含给定长度m的模式的文档的tf*idf分数。我们的数据结构是灵活的，在某种意义上说，他们支持查询任意模式。
We propose succinct data structures for text retrieval systems supporting document listing queries and ranking queries based on the tf*idf (term frequency times inverse document frequency) scores of documents. Traditional data structures for these problems support queries only for some predetermined keywords. Recently Muthukrishnan proposed a data structure for document listing queries for arbitrary patterns at the cost of data structure size. For computing the tf*idf scores there has been no efficient data structures for arbitrary patterns. Our new data structures support these queries using small space. The space is only 2/ϵ times the size of compressed documents plus 10n bits for a document collection of length n, for any 0<ϵ⩽1. This is much smaller than the previous O(nlogn) bit data structures. Query time is O(m+qlogϵn) for listing and computing tf*idf scores for all q documents containing a given pattern of length m. Our data structures are flexible in a sense that they support queries for arbitrary patterns.