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
|
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
|
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
|
------------------------------------------------------------------------------
with Ada.Containers.Indefinite_Doubly_Linked_Lists;
with Natools.S_Expressions;
private with Ada.Containers.Indefinite_Ordered_Maps;
private with Ada.Containers.Indefinite_Ordered_Sets;
private with Ada.Finalization;
package Natools.Smaz_Tools is
pragma Preelaborate;
package String_Lists is new Ada.Containers.Indefinite_Doubly_Linked_Lists
(String);
procedure Read_List
(List : out String_Lists.List;
Descriptor : in out S_Expressions.Descriptor'Class);
-- Read atoms from Descriptor to fill List
List_For_Linear_Search : String_Lists.List;
function Linear_Search (Value : String) return Natural;
-- Function and data source for inefficient but dynamic function
-- that can be used with Dictionary.Hash.
procedure Set_Dictionary_For_Map_Search (List : in String_Lists.List);
function Map_Search (Value : String) return Natural;
-- Function and data source for logarithmic search using standard
-- ordered map, that can be used with Dictionary.Hash.
type Search_Trie is private;
procedure Initialize (Trie : out Search_Trie; List : in String_Lists.List);
function Search (Trie : in Search_Trie; Value : in String) return Natural;
-- Trie-based search in a dynamic dictionary, for lookup whose
-- speed-vs-memory is even more skewed towards speed.
procedure Set_Dictionary_For_Trie_Search (List : in String_Lists.List);
function Trie_Search (Value : String) return Natural;
-- Function and data source for trie-based search that can be
-- used with Dictionary.Hash.
type String_Count is range 0 .. 2 ** 31 - 1;
-- Type for a number of substring occurrences
package Methods is
type Enum is (Encoded, Frequency, Gain);
end Methods;
|
149
150
151
152
153
154
155
156
157
|
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
|
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
|
function To_Scored_Word
(Cursor : in Word_Maps.Cursor;
Method : in Methods.Enum)
return Scored_Word;
package Scored_Word_Sets is new Ada.Containers.Indefinite_Ordered_Sets
(Scored_Word);
package Dictionary_Maps is new Ada.Containers.Indefinite_Ordered_Maps
(String, Natural);
Search_Map : Dictionary_Maps.Map;
type Trie_Node;
type Trie_Node_Access is access Trie_Node;
type Trie_Node_Array is array (Character) of Trie_Node_Access;
type Trie_Node (Is_Leaf : Boolean) is new Ada.Finalization.Controlled
with record
Index : Natural;
case Is_Leaf is
when True => null;
when False => Children : Trie_Node_Array;
end case;
end record;
overriding procedure Adjust (Node : in out Trie_Node);
overriding procedure Finalize (Node : in out Trie_Node);
type Search_Trie is record
Not_Found : Natural;
Root : Trie_Node (False);
end record;
Trie_For_Search : Search_Trie;
end Natools.Smaz_Tools;
|