Dico |
|
GNU Dictionary Server |
Sergey Poznyakoff |
6.2.2 Strategy Selectors
Wherever possible, modules should implement strategies using effective
look up algorithms. For example, ‘exact’ and ‘prefix’
strategies must normally be implemented using binary search in the
database index. The ‘suffix’ strategy can also be implemented
using binary search if a special reverse index is built for the
database (this is the approach taken by outline
and
dictorg
modules).
However, some strategies can only be implemented using a relatively expensive iteration over all keys in the database index. For example, ‘soundex’ and ‘levenshtein’ strategies cannot be implemented otherwise.
A strategy that can be used in iterative look ups must define a selector. Strategy selector is a function which is called for each database headword to determine whether it matches the search key.
It is defined as follows:
- selector: int select (int opcode, dico_key_t key, const char *headword)
A strategy selector. Its arguments are:
- opcode
The operation code. Its possible values are ‘DICO_SELECT_BEGIN’, ‘DICO_SELECT_RUN’ and ‘DICO_SELECT_END’, as described below.
- key
The search key.
- headword
The database headword.
The selector function is called before entering the iteration loop
with ‘DICO_SELECT_BEGIN’ as its argument. If necessary, it can
perform any additional initialization of the strategy, such as
allocation of auxiliary data structures, etc. The call_data
member of dico_key_t
structure (see call_data)
should be used to keep the pointer to the auxiliary data. The
function should return 0 if it successfully finished its
initialization and non-zero otherwise.
Once the iteration loop is finished, the selector will be called with ‘DICO_SELECT_END’ as its first argument. This invocation is intended to deallocate any auxiliary memory and release any additional resources allocated at the initialization state.
In these two additional invocations, the headword parameter will be ‘NULL’.
Once the iteration loop is entered, the selector function will be called for each headword. Its opcode parameter will be ‘DICO_SELECT_RUN’ and the headword parameter will point to the headword. The function should return 1 if the headword matches the key, 0 if it does not and a negative value in case of failure.
To illustrate the concept of strategy selector, let’s consider the
implementation of the ‘soundex’ strategy in dicod
.
This strategy computes a four-character soundex code for both search
key and the headword and returns 1 (match) if both codes coincide. To
speed up the process, the code for the search key is computed only
once, at the initialization stage, and stored in a temporary memory
assigned to the key->call_data
. This memory is reclaimed at
the terminating call:
int soundex_sel(int cmd, dico_key_t key, const char *dict_word) { char dcode[DICO_SOUNDEX_SIZE]; switch (cmd) { case DICO_SELECT_BEGIN: key->call_data = malloc(DICO_SOUNDEX_SIZE); if (!key->call_data) return 1; dico_soundex(key->word, key->call_data); break; case DICO_SELECT_RUN: dico_soundex(dict_word, dcode); return strcmp(dcode, key->call_data) == 0; case DICO_SELECT_END: free(key->call_data); break; } return 0; }
This document was generated on September 4, 2020 using makeinfo.
Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved.