* Copyright (c) 2000, 2006 Michael J. Roberts
* This file is part of TADS 3.
* This header defines the Dictionary intrinsic class.
/* include our base class definition */
* The Dictionary intrinsic class is a specialized lookup table class
* designed for storing the vocabulary table for a parser. Dictionary
* works closely with GrammarProd to supply the vocabulary tokens for the
* The main difference between Dictionary and a more general hash table is
* that Dictionary tags each vocabulary word with a type; for our purposes,
* the type is the vocabulary property (&noun, &adjective, etc) that
* associates the word with an object.
intrinsic class Dictionary 'dictionary2/030001': Object
* new Dictionary() - creates a dictionary with a default comparator,
* which matches strings exactly (note that upper-case and lower-case
* letters are considered distinct)
* new Dictionary(compObj) - create a dictionary with the given
* comparator object. A comparator is an object that implements the
* comparator interface - see below for details. When searching the
* dictionary (with findWord, for example), we use the comparator
* object to determine if the string beings sought matches a dictionary
* Set the comparator object. This defines how words are compared.
* The object must provide the following methods, which comprise the
* "comparator" interface. Note that there's no class that defines
* this interface; this is simply a set of methods that we define here,
* and which the supplied object must define.
* calcHash(str) - returns an integer giving the hash value of the
* given string. The purpose of the hash value is to arbitrarily
* partition the search space, so that we can search only a small
* subset of the dictionary when looking for a particular string. It
* is desirable for hash values to distribute uniformly for a given set
* of strings. It's also highly desirable for the hash computation to
* be inexpensive (i.e., to run fast), since the whole point of the
* hash is to reduce the amount of time it takes to find a string; if
* it takes longer to compute the hash value than it would to search
* every string in the table, then we don't come out ahead using the
* matchValues(inputStr, dictStr) - compare the given input string with
* the given dictionary string, and return a result indicating whether
* or not they match for the purposes of the comparator. A return
* value of zero or nil indicates that the values do not match; any
* other return value indicates a match.
* Typically, matchValues() will return a non-zero integer to indicate
* a match and to encode additional information about the match using a
* bitwise-OR'd combination of flag values. For example, a comparator
* that allows case folding could use bit flag 0x0001 to indicate any
* match, and bit flag 0x0002 to indicate a match where the case of one
* or more input letters did not match the case of the corresponding
* letters in the dictionary string. So, a return value of 0x0001
* would indicate an exact match, and 0x0003 would indicate a match
* with case differences.
* Note the asymmetry in the matchValues() arguments: we specifically
* designate one string as the input string and one as the dictionary
* string. This allows for asymmetrical comparisons, which are
* desirable in some cases: we sometimes want a given input string to
* match a given dictionary string even when the two are not identical
* character-by-character. For example, we might want to allow the
* user to type only the first six or eight characters of a string in
* the dictionary, to save typing; or, we might want to allow a user to
* enter unaccented letters and still match dictionary words containing
* the corresponding letters with accents. The asymmetry in the
* arguments is there because we often only want these "fuzzy" match
* rules to work in one direction; for the truncation example, we'd
* want an input word that's a truncated version of a dictionary word
* to match, but not the other way around.
* Important: Note that, although the hash value computation is up to
* the implementing object to define, we impose one requirement. It is
* REQUIRED that for any two strings s1 and s2, if matchValues(s1, s2)
* indicates a match (i.e., returns a value other than 0 or nil), then
* calcHash(s1) MUST EQUAL calcHash(s2). (This does NOT mean that two
* strings with equal hash values must be equal, or, equivalently, that
* two unequal strings must have different hash values. Hash
* collisions are explicitly allowed, so two strings that don't match
* can still have the same hash value.)
* Find a word; returns a list giving the objects associated with the
* string in the dictionary. If voc_prop is specified, only objects
* associated with the word by the given vocabulary property are
* returned. We match the string using the comparator defined for the
* The return value is a list consisting of pairs of entries. The
* first element of each pair is the matching object, and the second is
* gives the comparator result for matching the word. If we use a
* StringComparator, this will be a non-zero integer value giving
* information on truncation, case folding, and any equivalence
* mappings defined in the comparator. If the comparator is a custom
* object, then the second element of the pair will be whatever the
* custom comparator's matchValues() method returned for matching the
* value for that dictionary entry.
* The reason for giving a matchValues() return value for every
* individual match is that the same input string 'str' might match
* multiple entries in the dictionary. For example, the same string
* might match one word exactly and one with truncation. The match
* result code lets the caller determine if some matches are "better"
* than others, based on how the string matched for each individual
* object entry.
* Add a word to the dictionary, associating the given object with the
* given string and property combination.
addWord(obj, str, voc_prop);
* Remove the given word association from the dictionary. This
* removes only the association for the given object; other objects
* associated with the same word are not affected.
removeWord(obj, str, voc_prop);
* Check to see if the given string 'str' is defined in the dictionary.
* Returns true if the word is defined, nil if not.
* If the 'filter' argument is provided, it gives a callback function
* that is invoked to determine whether or not to count a particular
* word in the dictionary as a match. The callback is invoked with one
* argument: (filter)(match), where 'match' is the result of the
* comparator's matchValues(str,dstr) method, where 'dstr' is a
* dictionary string matching 'str'. The filter function returns true
* if the string should be counted as a match, nil if not. The return
* value of isWordDefined thus will be true if the filter function
* returns true for at least one match, nil if not. The purpose of the
* filter function is to allow the caller to impose a more restrictive
* condition than the dictionary's current comparator does; for
* example, the caller might use the filter to determine if the
* dictionary contains any matches for 'str' that match without any
* Invoke the callback func(obj, str, prop) for each word in the
* dictionary. Note that the callback can be invoked with a single
* string multiple times, since the callback is invoked once per
* word/object/property association; in other words, the callback is
* invoked once for each association created with addWord() or during
* Get a list of possible spelling corrections for the given word.
* This searches the dictionary for words that match the given word
* within the given maximum "edit distance".
* The return value is a list giving all of the words in the dictionary
* that match the input string within the given maximum edit distance.
* Any given dictionary word will appear only once in the returned
* list. The list is in arbitrary order. Each entry consists of a
* sublist, [word, dist, repl], where 'word' is a matching dictionary
* word, 'dist' is the edit distance between that dictionary word and
* the input string, and 'repl' is the number of character replacements
* performed. (The replacement count is included in the edit distance,
* but it's called out separately because some correctors treat
* replacements as heavier changes than other edits. A caller could
* use this to break ties for corrections of the same distance.
* Consider "book" and "box" as corrections for "bok": both have edit
* distance 1, but "book" has no replacements, while "box" has one.)
* The edit distance between two words is defined as the number of
* single-character insertions, deletions, replacements, and
* transpositions necessary to transform one word into another. For
* example, OPNE can be transformed into OPEN by transposing the N-E
* pair, for an edit distance of 1. XAEMINE can be transformed into
* EXAMINE by inserting an E at the beginning, and then deleting the E
* at the third letter, for an edit distance of 2.
* Choosing the maximum edit distance is essentially heuristic. Higher
* values make the search take longer, and yield more matches - which
* increases the chances that the right match will be found, but also
* increases the number of false matches to sift through. The
* literature on spelling correction suggests that 2 is a good value in
* practice, across a wide range of applications, based on the most
* frequent patterns of human typographical errors. However, you'll
* probably do better to vary the distance based on the word length:
* perhaps 1 for words up to 4 letters, 2 for 5-7 letters, and 3 for
* words of 8 letters or more.
* If the dictionary has a StringComparator object as its current
* comparator, the results will take into account its case folding
* setting, truncation length, and character mappings. These
* "approximations" are NOT considered to be edits, so they don't count
* against the maximum edit distance. Custom comparators (not of the
* StringComparator class) are ignored: if you use a custom comparator,
* this method will only find matches based on the exact text of the
* dictionary words.
* We rely on certain methods defined by the comparator interface, so
* export those method names.
property calcHash, matchValues;
export calcHash 'IfcComparator.calcHash';
export matchValues 'IfcComparator.matchValues';
TADS 3 Library Manual
Generated on 5/16/2013 from TADS version 3.1.3