-
Notifications
You must be signed in to change notification settings - Fork 11
/
Copy pathStringDictionaryRPDAC.h
162 lines (141 loc) · 5.8 KB
/
StringDictionaryRPDAC.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
/* StringDictionaryRPDAC.h
* Copyright (C) 2014, Francisco Claude & Rodrigo Canovas & Miguel A. Martinez-Prieto
* all rights reserved.
*
* This class implements a Compressed String Dictionary combining Re-Pair
* compression [1] and Directly Addresable Codes [2]:
*
* ==========================================================================
* [1] N. Jesper Larsson and Alistair Moffat.
* Off-Line Dictionary-Based Compression.
* Proceedings of the IEEE, 88: 1722-1732, 2000.
* [2] Nieves R. Brisaboa, Susana Ladra, and Gonzalo Navarro.
* DACs: Bringing Direct Access to Variable-Length Codes.
* Information Processing and Management 49(1):392-404, 2013.
* ==========================================================================
*
* This technique is inspired in the Re-Pair approach from:
*
* ==========================================================================
* "Compressed String Dictionaries"
* Nieves R. Brisaboa, Rodrigo Canovas, Francisco Claude,
* Miguel A. Martinez-Prieto and Gonzalo Navarro.
* 10th Symposium on Experimental Algorithms (SEA'2011), p.136-147, 2011.
* ==========================================================================
*
* The current approach enhances the original one with efficient locate and
* extract operations ** by prefix **.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*
*
* Contacting the authors:
* Francisco Claude: [email protected]
* Rodrigo Canovas: [email protected]
* Miguel A. Martinez-Prieto: [email protected]
*/
#ifndef _STRINGDICTIONARY_RPDAC_H
#define _STRINGDICTIONARY_RPDAC_H
#include <iostream>
using namespace std;
#include "StringDictionary.h"
#include "RePair/Coder/IRePair.h"
#include "utils/DAC_VLS.h"
#include "utils/LogSequence.h"
class StringDictionaryRPDAC : public StringDictionary
{
public:
/** Generic Constructor. */
StringDictionaryRPDAC();
/** Class Constructor.
@param it: iterator containing the original set of strings.
*/
StringDictionaryRPDAC(IteratorDictString *it);
/** Retrieves the ID corresponding to the given string.
@param str: the string to be searched.
@param strLen: the string length.
@returns the ID (or NORESULT if it is not in the bucket).
*/
uint locate(uchar *str, uint strLen);
/** Obtains the string associated with the given ID.
@param id: the ID to be extracted.
@param strLen: pointer to the extracted string length.
@returns the requested string (or NULL if it is not in the
dictionary).
*/
uchar* extract(size_t id, uint *strLen);
/** Locates all IDs of those elements prefixed by the given
string.
@param str: the prefix to be searched.
@param strLen: the prefix length.
@returns an iterator for direct scanning of all the IDs.
*/
IteratorDictID* locatePrefix(uchar *str, uint strLen);
/** Locates all IDs of those elements containing the given
substring.
@param str: the substring to be searched.
@param strLen: the substring length.
@returns an iterator for direct scanning of all the IDs.
*/
IteratorDictID* locateSubstr(uchar *str, uint strLen);
/** Retrieves the ID with rank k according to its alphabetical order.
@param rank: the alphabetical ranking.
@returns the ID.
*/
uint locateRank(uint rank);
/** Extracts all elements prefixed by the given string.
@param str: the prefix to be searched.
@param strLen: the prefix length.
@returns an iterator for direct scanning of all the strings.
*/
IteratorDictString* extractPrefix(uchar *str, uint strLen);
/** Extracts all elements containing by the given substring.
@param str: the substring to be searched.
@param strLen: the substring length.
@returns an iterator for direct scanning of all the strings.
*/
IteratorDictString* extractSubstr(uchar *str, uint strLen);
/** Obtains the string with rank k according to its
alphabetical order.
@param id: the ID to be extracted.
@param strLen: pointer to the extracted string length.
@returns the requested string (or NULL if it is not in the
dictionary).
*/
uchar* extractRank(uint rank, uint *strLen);
/** Extracts all strings in the dictionary sorted in
alphabetical order.
@returns an iterator for direct scanning of all the strings.
*/
IteratorDictString* extractTable();
/** Computes the size of the structure in bytes.
@returns the dictionary size in bytes.
*/
size_t getSize();
/** Stores the dictionary into an ofstream.
@param out: the oftstream.
*/
void save(ofstream &out);
/** Loads a dictionary from an ifstream.
@param in: the ifstream.
@returns the loaded dictionary.
*/
static StringDictionary *load(ifstream &in);
/** Generic destructor. */
~StringDictionaryRPDAC();
protected:
RePair *rp; //! RePair representation
};
#endif /* _STRINGDICTIONARY_RPDAC_H */