source: proto/SymbolTable/README_SymbolTable @ 1684

Last change on this file since 1684 was 1278, checked in by vla24, 8 years ago

refactored some code

File size: 2.0 KB
Line 
1STANDARD LIBRARY SYMBOL TABLE
2
3A symbol table using STL C library.
4To compile      : make symtab_stl
5Data structure  : lib/symtab/symtab.*
6
7---------------------------------
8
9HASH TABLE (Jestress)
10
11This symbol table uses Jestress hashing function.
12To compile      : make symtab_hash
13Data structure  : lib/symtab/hash_symbol_table.*
14
15---------------------------------
16
17LENGTH SORTING
18
191. MASK-EQUAL-AND/OR
20This is Ken's implementation. We are using mask-equal-and/or method
21To compile      : make symtab_ls
22Data structure  : lib/symtab/ls_symbol_table*.*
23
242. USE_IDENTITY_SORT    f(L) = L
25Input:
26- a bitstream that marks start positions
27- a bitstream that marks end positions
28Sequentially scan symbols and group the symbols based on their length.
29To compile      : make symtab_id
30Data structure  : lib/symtab/pbgs_identity_symbol_table.h
31
32---------------------------------
33
34PARALLEL BITSTREAM-BASED LENGTH SORTING
35
361. USE_IDENTITY_SORT    f(L) = L
37Data structure          : lib/symtab/pbgs_identity_symbol_table.h
38There are 2 different implementations:
39  a. We evaluate the bitstreams using interpose32 and advance32.
40     To compile         : make symtab_pbgs_id_adv
41  b. We evaluate the bitstreams using one shift right for each bitutil.advance call
42     To compile         : make symtab_pbgs_id
43
442. USE_LOG_SORT         f(L) = log(L)
45To compile              : make symtab_pbgs_log
46Data structure          : lib/symtab/pbgs_log_symbol_table.h
47
483. USE_DIV_SORT         f(L) = L/4
49NOTE: This implementation is not ready yet
50To compile              : make symtab_pbgs_div
51Data structure          : lib/symtab/pbgs_div_symbol_table.h
52
53
54HASH TABLE IMPLEMENTATION NOTES:
55- All the 3 strategies are using the same hash table implementation (bitstream_hash_table.h) and the same comparison implementation (equal_compare.h).
56
57
58XMLWF IMPLEMENTATION NOTES:
59- XMLWF makes use of overlapping buffer so that the system could look ahead or look back as needed.
60  - For string buffer implementation, the system can look 32 bytes back/ahead (1 byte = 1 character)
61  - For hash value implementation, the system can look 128 bits back/ahead (1 bit = 1 character/position)
Note: See TracBrowser for help on using the repository browser.