Coverage for nltk.featstruct : 81%
Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
|
# Natural Language Toolkit: Feature Structures # # Copyright (C) 2001-2012 NLTK Project # Author: Edward Loper <edloper@gradient.cis.upenn.edu>, # Rob Speer, # Steven Bird <sb@csse.unimelb.edu.au> # URL: <http://nltk.sourceforge.net> # For license information, see LICENSE.TXT
Basic data classes for representing feature structures, and for performing basic operations on those feature structures. A feature structure is a mapping from feature identifiers to feature values, where each feature value is either a basic value (such as a string or an integer), or a nested feature structure. There are two types of feature structure, implemented by two subclasses of ``FeatStruct``:
- feature dictionaries, implemented by ``FeatDict``, act like Python dictionaries. Feature identifiers may be strings or instances of the ``Feature`` class. - feature lists, implemented by ``FeatList``, act like Python lists. Feature identifiers are integers.
Feature structures are typically used to represent partial information about objects. A feature identifier that is not mapped to a value stands for a feature whose value is unknown (*not* a feature without a value). Two feature structures that represent (potentially overlapping) information about the same object can be combined by unification. When two inconsistent feature structures are unified, the unification fails and returns None.
Features can be specified using "feature paths", or tuples of feature identifiers that specify path through the nested feature structures to a value. Feature structures may contain reentrant feature values. A "reentrant feature value" is a single feature value that can be accessed via multiple feature paths. Unification preserves the reentrance relations imposed by both of the unified feature structures. In the feature structure resulting from unification, any modifications to a reentrant feature value will be visible using any of its feature paths.
Feature structure variables are encoded using the ``nltk.sem.Variable`` class. The variables' values are tracked using a bindings dictionary, which maps variables to their values. When two feature structures are unified, a fresh bindings dictionary is created to track their values; and before unification completes, all bound variables are replaced by their values. Thus, the bindings dictionaries are usually strictly internal to the unification process. However, it is possible to track the bindings of variables if you choose to, by supplying your own initial bindings dictionary to the ``unify()`` function.
When unbound variables are unified with one another, they become aliased. This is encoded by binding one variable to the other.
Lightweight Feature Structures ============================== Many of the functions defined by ``nltk.featstruct`` can be applied directly to simple Python dictionaries and lists, rather than to full-fledged ``FeatDict`` and ``FeatList`` objects. In other words, Python ``dicts`` and ``lists`` can be used as "light-weight" feature structures.
>>> from nltk.featstruct import unify >>> unify(dict(x=1, y=dict()), dict(a='a', y=dict(b='b'))) {'y': {'b': 'b'}, 'x': 1, 'a': 'a'}
However, you should keep in mind the following caveats:
- Python dictionaries & lists ignore reentrance when checking for equality between values. But two FeatStructs with different reentrances are considered nonequal, even if all their base values are equal.
- FeatStructs can be easily frozen, allowing them to be used as keys in hash tables. Python dictionaries and lists can not.
- FeatStructs display reentrance in their string representations; Python dictionaries and lists do not.
- FeatStructs may *not* be mixed with Python dictionaries and lists (e.g., when performing unification).
- FeatStructs provide a number of useful methods, such as ``walk()`` and ``cyclic()``, which are not available for Python dicts and lists.
In general, if your feature structures will contain any reentrances, or if you plan to use them as dictionary keys, it is strongly recommended that you use full-fledged ``FeatStruct`` objects. """
LogicParser, ParseException)
###################################################################### # Feature Structure ######################################################################
""" A mapping from feature identifiers to feature values, where each feature value is either a basic value (such as a string or an integer), or a nested feature structure. There are two types of feature structure:
- feature dictionaries, implemented by ``FeatDict``, act like Python dictionaries. Feature identifiers may be strings or instances of the ``Feature`` class. - feature lists, implemented by ``FeatList``, act like Python lists. Feature identifiers are integers.
Feature structures may be indexed using either simple feature identifiers or 'feature paths.' A feature path is a sequence of feature identifiers that stand for a corresponding sequence of indexing operations. In particular, ``fstruct[(f1,f2,...,fn)]`` is equivalent to ``fstruct[f1][f2]...[fn]``.
Feature structures may contain reentrant feature structures. A "reentrant feature structure" is a single feature structure object that can be accessed via multiple feature paths. Feature structures may also be cyclic. A feature structure is "cyclic" if there is any feature path from the feature structure to itself.
Two feature structures are considered equal if they assign the same values to all features, and have the same reentrancies.
By default, feature structures are mutable. They may be made immutable with the ``freeze()`` method. Once they have been frozen, they may be hashed, and thus used as dictionary keys. """
""":ivar: A flag indicating whether this feature structure is frozen or not. Once this flag is set, it should never be un-set; and no further modification should be made to this feature structue."""
##//////////////////////////////////////////////////////////// #{ Constructor ##////////////////////////////////////////////////////////////
""" Construct and return a new feature structure. If this constructor is called directly, then the returned feature structure will be an instance of either the ``FeatDict`` class or the ``FeatList`` class.
:param features: The initial feature values for this feature structure: - FeatStruct(string) -> FeatStructParser().parse(string) - FeatStruct(mapping) -> FeatDict(mapping) - FeatStruct(sequence) -> FeatList(sequence) - FeatStruct() -> FeatDict() :param morefeatures: If ``features`` is a mapping or None, then ``morefeatures`` provides additional features for the ``FeatDict`` constructor. """ # If the FeatStruct constructor is called directly, then decide # whether to create a FeatDict or a FeatList, based on the # contents of the `features` argument. return FeatDict.__new__(FeatDict, features, **morefeatures) raise TypeError('Keyword arguments may only be specified ' 'if features is None or is a mapping.') else: else: raise TypeError('Expected string or mapping or sequence')
# Otherwise, construct the object as normal. else: **morefeatures)
##//////////////////////////////////////////////////////////// #{ Uniform Accessor Methods ##//////////////////////////////////////////////////////////// # These helper functions allow the methods defined by FeatStruct # to treat all feature structures as mappings, even if they're # really lists. (Lists are treated as mappings from ints to vals)
"""Return an iterable of the feature identifiers used by this FeatStruct.""" raise NotImplementedError() # Implemented by subclasses.
"""Return an iterable of the feature values directly defined by this FeatStruct.""" raise NotImplementedError() # Implemented by subclasses.
"""Return an iterable of (fid,fval) pairs, where fid is a feature identifier and fval is the corresponding feature value, for all features defined by this FeatStruct.""" raise NotImplementedError() # Implemented by subclasses.
##//////////////////////////////////////////////////////////// #{ Equality & Hashing ##////////////////////////////////////////////////////////////
""" Return True if ``self`` and ``other`` assign the same value to to every feature. In particular, return true if ``self[p]==other[p]`` for every feature path *p* such that ``self[p]`` or ``other[p]`` is a base value (i.e., not a nested feature structure).
:param check_reentrance: If True, then also return False if there is any difference between the reentrances of ``self`` and ``other``. :note: the ``==`` is equivalent to ``equal_values()`` with ``check_reentrance=True``. """
""" Return true if ``self`` and ``other`` are both feature structures, assign the same values to all features, and contain the same reentrances. I.e., return ``self.equal_values(other, check_reentrance=True)``.
:see: ``equal_values()`` """
""" Return true unless ``self`` and ``other`` are both feature structures, assign the same values to all features, and contain the same reentrances. I.e., return ``not self.equal_values(other, check_reentrance=True)``. """
return len(self) < len(other)
""" If this feature structure is frozen, return its hash value; otherwise, raise ``TypeError``. """ 'can be hashed.')
visited_other, visited_pairs): """ Return True iff self and other have equal values.
:param visited_self: A set containing the ids of all ``self`` feature structures we've already visited. :param visited_other: A set containing the ids of all ``other`` feature structures we've already visited. :param visited_pairs: A set containing ``(selfid, otherid)`` pairs for all pairs of feature structures we've already visited. """ # If we're the same object, then we're equal.
# If we have different classes, we're definitely not equal.
# If we define different features, we're definitely not equal. # (Perform len test first because it's faster -- we should # do profiling to see if this actually helps)
# If we're checking reentrance, then any time we revisit a # structure, make sure that it was paired with the same # feature structure that it is now. Note: if check_reentrance, # then visited_pairs will never contain two pairs whose first # values are equal, or two pairs whose second values are equal.
# If we're not checking reentrance, then we still need to deal # with cycles. If we encounter the same (self, other) pair a # second time, then we won't learn anything more by examining # their children a second time, so just return true. else:
# Keep track of which nodes we've visited.
# Now we have to check all values. If any of them don't match, # then return false. visited_self, visited_other, visited_pairs): else:
# Everything matched up; return true.
""" Return a hash value for this feature structure.
:require: ``self`` must be frozen. :param visited: A set containing the ids of all feature structures we've already visited while hashing. """
else: # Convert to a 32 bit int.
##//////////////////////////////////////////////////////////// #{ Freezing ##////////////////////////////////////////////////////////////
#: Error message used by mutating methods when called on a frozen #: feature structure.
""" Make this feature structure, and any feature structures it contains, immutable. Note: this method does not attempt to 'freeze' any feature value that is not a ``FeatStruct``; it is recommended that you use only immutable feature values. """
""" Return True if this feature structure is immutable. Feature structures can be made immutable with the ``freeze()`` method. Immutable feature structures may not be made mutable again, but new mutable copies can be produced with the ``copy()`` method. """
""" Make this feature structure, and any feature structure it contains, immutable.
:param visited: A set containing the ids of all feature structures we've already visited while freezing. """
##//////////////////////////////////////////////////////////// #{ Copying ##////////////////////////////////////////////////////////////
""" Return a new copy of ``self``. The new copy will not be frozen.
:param deep: If true, create a deep copy; if false, create a shallow copy. """ else: return self.__class__(self)
# Subclasses should define __deepcopy__ to ensure that the new # copy will not be frozen. raise NotImplementedError() # Implemented by subclasses.
##//////////////////////////////////////////////////////////// #{ Structural Information ##////////////////////////////////////////////////////////////
""" Return True if this feature structure contains itself. """ return self._find_reentrances({})[id(self)]
""" Return an iterator that generates this feature structure, and each feature structure it contains. Each feature structure will be generated exactly once. """ return self._walk(set())
""" Return an iterator that generates this feature structure, and each feature structure it contains.
:param visited: A set containing the ids of all feature structures we've already visited while freezing. """ raise NotImplementedError() # Implemented by subclasses.
if id(self) in visited: return visited.add(id(self)) yield self for fval in self._values(): if isinstance(fval, FeatStruct): for elt in fval._walk(visited): yield elt
# Walk through the feature tree. The first time we see a feature # value, map it to False (not reentrant). If we see a feature # value more than once, then map it to True (reentrant). """ Return a dictionary that maps from the ``id`` of each feature structure contained in ``self`` (including ``self``) to a boolean value, indicating whether it is reentrant or not. """ # We've seen it more than once. else: # This is the first time we've seen it.
# Recurse to contained feature structures.
##//////////////////////////////////////////////////////////// #{ Variables & Bindings ##////////////////////////////////////////////////////////////
""":see: ``nltk.featstruct.substitute_bindings()``"""
""":see: ``nltk.featstruct.retract_bindings()``""" return retract_bindings(self, bindings)
""":see: ``nltk.featstruct.find_variables()``"""
""":see: ``nltk.featstruct.rename_variables()``"""
""" Return the feature structure that is obtained by deleting any feature whose value is a ``Variable``.
:rtype: FeatStruct """
##//////////////////////////////////////////////////////////// #{ Unification ##////////////////////////////////////////////////////////////
fail=None, rename_vars=True):
""" Return True if ``self`` subsumes ``other``. I.e., return true If unifying ``self`` with ``other`` would result in a feature structure equal to ``other``. """ return subsumes(self, other)
##//////////////////////////////////////////////////////////// #{ String Representations ##////////////////////////////////////////////////////////////
""" Display a single-line representation of this feature structure, suitable for embedding in other representations. """
""" Return a string representation of this feature structure.
:param reentrances: A dictionary that maps from the ``id`` of each feature value in self, indicating whether that value is reentrant or not. :param reentrance_ids: A dictionary mapping from each ``id`` of a feature value to a unique identifier. This is modified by ``repr``: the first time a reentrant feature value is displayed, an identifier is added to ``reentrance_ids`` for it. """ raise NotImplementedError()
# Mutation: disable if frozen. """ Given a method function, return a new method function that first checks if ``self._frozen`` is true; and if so, raises ``ValueError`` with an appropriate message. Otherwise, call the method and return its result. """
###################################################################### # Feature Dictionary ######################################################################
""" A feature structure that acts like a Python dictionary. I.e., a mapping from feature identifiers to feature values, where a feature identifier can be a string or a ``Feature``; and where a feature value can be either a basic value (such as a string or an integer), or a nested feature structure. A feature identifiers for a ``FeatDict`` is sometimes called a "feature name".
Two feature dicts are considered equal if they assign the same values to all features, and have the same reentrances.
:see: ``FeatStruct`` for information about feature paths, reentrance, cyclic feature structures, mutability, freezing, and hashing. """ """ Create a new feature dictionary, with the specified features.
:param features: The initial value for this feature dictionary. If ``features`` is a ``FeatStruct``, then its features are copied (shallow copy). If ``features`` is a dict, then a feature is created for each item, mapping its key to its value. If ``features`` is a string, then it is parsed using ``FeatStructParser``. If ``features`` is a list of tuples ``(name, val)``, then a feature is created for each tuple. :param morefeatures: Additional features for the new feature dictionary. If a feature is listed under both ``features`` and ``morefeatures``, then the value from ``morefeatures`` will be used. """ else: # update() checks the types of features.
#//////////////////////////////////////////////////////////// #{ Dict methods #////////////////////////////////////////////////////////////
"""If the feature with the given name or path exists, return its value; otherwise, raise ``KeyError``.""" else:
"""If the feature with the given name or path exists, return its value; otherwise, return ``default``."""
"""Return true if a feature with the given name or path exists."""
"""Return true if a feature with the given name or path exists."""
"""If the feature with the given name or path exists, delete its value; otherwise, raise ``KeyError``.""" raise ValueError("The path () can not be set") else: raise KeyError(name_or_path) # path contains base value else: raise TypeError(self._INDEX_ERROR % name_or_path)
"""Set the value for the feature with the given name or path to ``value``. If ``name_or_path`` is an invalid path, raise ``KeyError``.""" raise ValueError("The path () can not be set") else: raise KeyError(name_or_path) # path contains base value else: raise TypeError(self._INDEX_ERROR % name_or_path)
else: raise ValueError('Expected mapping or list of tuples')
raise TypeError('Feature names must be strings') raise TypeError('Feature names must be strings')
##//////////////////////////////////////////////////////////// #{ Copying ##////////////////////////////////////////////////////////////
##//////////////////////////////////////////////////////////// #{ Uniform Accessor Methods ##////////////////////////////////////////////////////////////
##//////////////////////////////////////////////////////////// #{ String Representations ##////////////////////////////////////////////////////////////
""" Display a multi-line representation of this feature dictionary as an FVM (feature value matrix). """
# If this is the first time we've seen a reentrant structure, # then assign it a unique identifier.
# sorting note: keys are unique strings, so we'll never fall # through to comparing values. (fname, reentrance_ids[id(fval)])) isinstance(fval, (Variable, string_types))): suffix = '/%s' % fval.name else: else: # If it's reentrant, then add on an identifier tag.
""" :return: A list of lines composing a string representation of this feature dictionary. :param reentrances: A dictionary that maps from the ``id`` of each feature value in self, indicating whether that value is reentrant or not. :param reentrance_ids: A dictionary mapping from each ``id`` of a feature value to a unique identifier. This is modified by ``repr``: the first time a reentrant feature value is displayed, an identifier is added to ``reentrance_ids`` for it. """ # If this is the first time we've seen a reentrant structure, # then tack on an id string.
# Special case: empty feature dict. else: return ['[]']
# What's the longest feature name? Use this to align names.
# sorting note: keys are unique strings, so we'll never fall # through to comparing values.
fval_repr = fval._repr(reentrances, reentrance_ids) lines.append('%s = %r' % (fname, fval_repr))
# It's not a nested feature structure -- just print it.
# It's a feature structure we've seen before -- print # the reentrance id.
else: # It's a new feature structure. Separate it from # other values by a blank line.
# Recursively print the feature's value (fval).
# Indent each line to make room for fname.
# Pick which line we'll display fname on, & splice it in. fname+' ='+fval_lines[nameline][maxfnamelen+2:])
# Add the feature structure to the output.
# Separate FeatStructs by a blank line.
# Get rid of any excess blank lines.
# Add brackets around everything.
# If it's reentrant, then add on an identifier tag.
###################################################################### # Feature List ######################################################################
""" A list of feature values, where each feature value is either a basic value (such as a string or an integer), or a nested feature structure.
Feature lists may contain reentrant feature values. A "reentrant feature value" is a single feature value that can be accessed via multiple feature paths. Feature lists may also be cyclic.
Two feature lists are considered equal if they assign the same values to all features, and have the same reentrances.
:see: ``FeatStruct`` for information about feature paths, reentrance, cyclic feature structures, mutability, freezing, and hashing. """ """ Create a new feature list, with the specified features.
:param features: The initial list of features for this feature list. If ``features`` is a string, then it is paresd using ``FeatStructParser``. Otherwise, it should be a sequence of basic values and nested feature structures. """ else:
#//////////////////////////////////////////////////////////// #{ List methods #////////////////////////////////////////////////////////////
elif isinstance(name_or_path, tuple): try: val = self for fid in name_or_path: if not isinstance(val, FeatStruct): raise KeyError # path contains base value val = val[fid] return val except (KeyError, IndexError): raise KeyError(name_or_path) else: raise TypeError(self._INDEX_ERROR % name_or_path)
"""If the feature with the given name or path exists, delete its value; otherwise, raise ``KeyError``.""" elif isinstance(name_or_path, tuple): if len(name_or_path) == 0: raise ValueError("The path () can not be set") else: parent = self[name_or_path[:-1]] if not isinstance(parent, FeatStruct): raise KeyError(name_or_path) # path contains base value del parent[name_or_path[-1]] else: raise TypeError(self._INDEX_ERROR % name_or_path)
"""Set the value for the feature with the given name or path to ``value``. If ``name_or_path`` is an invalid path, raise ``KeyError``.""" elif isinstance(name_or_path, tuple): if len(name_or_path) == 0: raise ValueError("The path () can not be set") else: parent = self[name_or_path[:-1]] if not isinstance(parent, FeatStruct): raise KeyError(name_or_path) # path contains base value parent[name_or_path[-1]] = value else: raise TypeError(self._INDEX_ERROR % name_or_path)
# __delslice__ = _check_frozen(list.__delslice__, ' ') # __setslice__ = _check_frozen(list.__setslice__, ' ')
##//////////////////////////////////////////////////////////// #{ Copying ##////////////////////////////////////////////////////////////
##//////////////////////////////////////////////////////////// #{ Uniform Accessor Methods ##////////////////////////////////////////////////////////////
##//////////////////////////////////////////////////////////// #{ String Representations ##////////////////////////////////////////////////////////////
# Special handling for: reentrances, variables, expressions. # If this is the first time we've seen a reentrant structure, # then assign it a unique identifier. assert id(self) not in reentrance_ids reentrance_ids[id(self)] = repr(len(reentrance_ids)+1) prefix = '(%s)' % reentrance_ids[id(self)] else:
segments.append('->(%s)' % reentrance_ids[id(fval)]) segments.append(fval.name) segments.append('%s' % fval) else:
###################################################################### # Variables & Bindings ######################################################################
""" Return the feature structure that is obtained by replacing each variable bound by ``bindings`` with its binding. If a variable is aliased to a bound variable, then it will be replaced by that variable's value. If a variable is aliased to an unbound variable, then it will be replaced by that variable.
:type bindings: dict(Variable -> any) :param bindings: A dictionary mapping from variables to values. """
# Visit each node only once:
else: raise ValueError('Expected mapping or sequence')
""" Return the feature structure that is obtained by replacing each feature structure value that is bound by ``bindings`` with the variable that binds it. A feature structure value must be identical to a bound value (i.e., have equal id) to be replaced.
``bindings`` is modified to point to this new feature structure, rather than the original feature structure. Feature structure values in ``bindings`` may be modified if they are contained in ``fstruct``. """
# Visit each node only once:
elif _is_sequence(fstruct): items = enumerate(fstruct) else: raise ValueError('Expected mapping or sequence')
""" :return: The set of variables used by this feature structure. :rtype: set(Variable) """
# Visit each node only once: else: raise ValueError('Expected mapping or sequence')
fs_class='default'): """ Return the feature structure that is obtained by replacing any of this feature structure's variables that are in ``vars`` with new variables. The names for these new variables will be names that are not used by any variable in ``vars``, or in ``used_vars``, or in this feature structure.
:type vars: set :param vars: The set of variables that should be renamed. If not specified, ``find_variables(fstruct)`` is used; i.e., all variables will be given new names. :type used_vars: set :param used_vars: A set of variables whose names should not be used by the new variables. :type new_vars: dict(Variable -> Variable) :param new_vars: A dictionary that is used to hold the mapping from old variables to new variables. For each variable *v* in this feature structure:
- If ``new_vars`` maps *v* to *v'*, then *v* will be replaced by *v'*. - If ``new_vars`` does not contain *v*, but ``vars`` does contain *v*, then a new entry will be added to ``new_vars``, mapping *v* to the new variable that is used to replace it.
To consistently rename the variables in a set of feature structures, simply apply rename_variables to each one, using the same dictionary:
>>> from nltk.featstruct import FeatStruct >>> fstruct1 = FeatStruct('[subj=[agr=[gender=?y]], obj=[agr=[gender=?y]]]') >>> fstruct2 = FeatStruct('[subj=[agr=[number=?z,gender=?y]], obj=[agr=[number=?z,gender=?y]]]') >>> new_vars = {} # Maps old vars to alpha-renamed vars >>> fstruct1.rename_variables(new_vars=new_vars) [obj=[agr=[gender=?y2]], subj=[agr=[gender=?y2]]] >>> fstruct2.rename_variables(new_vars=new_vars) [obj=[agr=[gender=?y2, number=?z2]], subj=[agr=[gender=?y2, number=?z2]]]
If new_vars is not specified, then an empty dictionary is used. """
# Default values:
# Add our own variables to used_vars.
# Copy ourselves, and rename variables in the copy. new_vars, fs_class, set())
else: raise ValueError('Expected mapping or sequence') # If it's in new_vars, then rebind it. # If it's in vars, pick a new name for it. fs_class, visited) # Pick new names for any variables in `vars` # Replace all variables in `new_vars`.
""" :rtype: FeatStruct :return: The feature structure that is obtained by deleting all features whose values are ``Variables``. """
elif _is_sequence(fstruct): items = list(enumerate(fstruct)) else: raise ValueError('Expected mapping or sequence')
###################################################################### # Unification ######################################################################
"""A unique value used to indicate unification failure. It can be returned by ``Feature.unify_base_values()`` or by custom ``fail()`` functions to indicate that unificaiton should fail."""
# The basic unification algorithm: # 1. Make copies of self and other (preserving reentrance) # 2. Destructively unify self and other # 3. Apply forward pointers, to preserve reentrance. # 4. Replace bound variables with their values. fail=None, rename_vars=True, fs_class='default'): """ Unify ``fstruct1`` with ``fstruct2``, and return the resulting feature structure. This unified feature structure is the minimal feature structure that contains all feature value assignments from both ``fstruct1`` and ``fstruct2``, and that preserves all reentrancies.
If no such feature structure exists (because ``fstruct1`` and ``fstruct2`` specify incompatible values for some feature), then unification fails, and ``unify`` returns None.
Bound variables are replaced by their values. Aliased variables are replaced by their representative variable (if unbound) or the value of their representative variable (if bound). I.e., if variable *v* is in ``bindings``, then *v* is replaced by ``bindings[v]``. This will be repeated until the variable is replaced by an unbound variable or a non-variable value.
Unbound variables are bound when they are unified with values; and aliased when they are unified with variables. I.e., if variable *v* is not in ``bindings``, and is unified with a variable or value *x*, then ``bindings[v]`` is set to *x*.
If ``bindings`` is unspecified, then all variables are assumed to be unbound. I.e., ``bindings`` defaults to an empty dict.
>>> from nltk.featstruct import FeatStruct >>> FeatStruct('[a=?x]').unify(FeatStruct('[b=?x]')) [a=?x, b=?x2]
:type bindings: dict(Variable -> any) :param bindings: A set of variable bindings to be used and updated during unification. :type trace: bool :param trace: If true, generate trace output. :type rename_vars: bool :param rename_vars: If True, then rename any variables in ``fstruct2`` that are also used in ``fstruct1``, in order to avoid collisions on variable names. """ # Decide which class(es) will be treated as feature structures, # for the purposes of unification. "dicts and lists is not supported.")
# If bindings are unspecified, use an empty set of bindings.
# Make copies of fstruct1 and fstruct2 (since the unification # algorithm is destructive). Do it all at once, to preserve # reentrance links between fstruct1 and fstruct2. Copy bindings # as well, in case there are any bound vars that contain parts # of fstruct1 or fstruct2. copy.deepcopy((fstruct1, fstruct2, bindings)))
# Copy the bindings back to the original bindings dict.
# Do the actual unification. If it fails, return None. forward, trace, fail, fs_class, ())
# _destructively_unify might return UnificationFailure, e.g. if we # tried to unify a mapping with a sequence. if fail is None: return None else: return fail(fstruct1copy, fstruct2copy, ())
# Replace any feature structure that has a forward pointer # with the target of its forward pointer.
# Replace bound vars with values.
# Return the result.
"""An exception that is used by ``_destructively_unify`` to abort unification when a failure is encountered."""
trace, fail, fs_class, path): """ Attempt to unify ``fstruct1`` and ``fstruct2`` by modifying them in-place. If the unification succeeds, then ``fstruct1`` will contain the unified value, the value of ``fstruct2`` is undefined, and forward[id(fstruct2)] is set to fstruct1. If the unification fails, then a _UnificationFailureError is raised, and the values of ``fstruct1`` and ``fstruct2`` are undefined.
:param bindings: A dictionary mapping variables to values. :param forward: A dictionary mapping feature structures ids to replacement structures. When two feature structures are merged, a mapping from one to the other will be added to the forward dictionary; and changes will be made only to the target of the forward dictionary. ``_destructively_unify`` will always 'follow' any links in the forward dictionary for fstruct1 and fstruct2 before actually unifying them. :param trace: If true, generate trace output :param path: The feature path that led us to this unification step. Used for trace output. """ # If fstruct1 is already identical to fstruct2, we're done. # Note: this, together with the forward pointers, ensures # that unification will terminate even for cyclic structures.
# Set fstruct2's forward pointer to point to fstruct1; this makes # fstruct1 the canonical copy for fstruct2. Note that we need to # do this before we recurse into any child structures, in case # they're cyclic.
# Unifying two mappings:
# Unify any values that are defined in both fstruct1 and # fstruct2. Copy any values that are defined in fstruct2 but # not in fstruct1 to fstruct1. Note: sorting fstruct2's # features isn't actually necessary; but we do it to give # deterministic behavior, e.g. for tracing. fname, fstruct1[fname], fval2, bindings, forward, trace, fail, fs_class, path+(fname,)) else:
# Unifying two sequences: # If the lengths don't match, fail. return UnificationFailure
# Unify corresponding values in fstruct1 and fstruct2. findex, fstruct1[findex], fstruct2[findex], bindings, forward, trace, fail, fs_class, path+(findex,))
# Unifying sequence & mapping: fail. The failure function # doesn't get a chance to recover in this case. elif ((_is_sequence(fstruct1) or _is_mapping(fstruct1)) and (_is_sequence(fstruct2) or _is_mapping(fstruct2))): return UnificationFailure
# Unifying anything else: not allowed! raise TypeError('Expected mappings or sequences')
trace, fail, fs_class, fpath): """ Attempt to unify ``fval1`` and and ``fval2``, and return the resulting unified value. The method of unification will depend on the types of ``fval1`` and ``fval2``:
1. If they're both feature structures, then destructively unify them (see ``_destructively_unify()``. 2. If they're both unbound variables, then alias one variable to the other (by setting bindings[v2]=v1). 3. If one is an unbound variable, and the other is a value, then bind the unbound variable to the value. 4. If one is a feature structure, and the other is a base value, then fail. 5. If they're both base values, then unify them. By default, this will succeed if they are equal, and fail otherwise. """
# Look up the "canonical" copy of fval1 and fval2
# If fval1 or fval2 is a bound variable, then # replace it by the variable's bound value. This # includes aliased variables, which are encoded as # variables bound to other variables.
# Case 1: Two feature structures (recursive case) trace, fail, fs_class, fpath)
# Case 2: Two unbound variables (create alias) isinstance(fval2, Variable)):
# Case 3: An unbound variable and a value (bind)
# Case 4: A feature structure & a base value (fail)
# Case 5: Two base values else: # Case 5a: Feature defines a custom unification method for base values # Case 5b: Feature value defines custom unification method # Sanity check: unify value should be symmetric result != fval2.unify(fval1)): raise AssertionError( 'CustomFeatureValue objects %r and %r disagree ' 'about unification value: %r vs. %r' % (fval1, fval2, result, fval2.unify(fval1))) result = fval2.unify(fval1) # Case 5c: Simple values -- check if they're equal. else: else:
# If either value was a bound variable, then update the # bindings. (This is really only necessary if fname is a # Feature or if either value is a CustomFeatureValue.)
# If we unification failed, call the failure function; it # might decide to continue anyway.
# Normalize the result.
""" Replace any feature structure that has a forward pointer with the target of its forward pointer (to preserve reentrancy). """
""" Replace any feature structure that has a forward pointer with the target of its forward pointer (to preserve reentrancy). """ # Follow our own forwards pointers (if any)
# Visit each node only once:
else: raise ValueError('Expected mapping or sequence') # Replace w/ forwarded value. # Recurse to child.
""" Replace any bound aliased vars with their binding; and replace any unbound aliased vars with their representative var. """
else: print(' '+'| '*len(path)+'|') print(' '+'| '*len(path)+'| (identical objects)') print(' '+'| '*len(path)+'|') print(' '+'| '*len(path)+'+-->'+repr(fval1)) else: resume = ' (nonfatal)' # Print the result. # Print the bindings (if any). '%s: %s' % (var, _trace_valrepr(val)) for (var, val) in binditems) else:
""" Return True if ``fstruct1`` subsumes ``fstruct2``. I.e., return true if unifying ``fstruct1`` with ``fstruct2`` would result in a feature structure equal to ``fstruct2.``
:rtype: bool """ return fstruct2 == unify(fstruct1, fstruct2)
""" Return a list of the feature paths of all features which are assigned incompatible values by ``fstruct1`` and ``fstruct2``.
:rtype: list(tuple) """
###################################################################### # Helper Functions ######################################################################
not isinstance(v, string_types))
else: raise ValueError('To unify objects of type %s, you must specify ' 'fs_class explicitly.' % obj.__class__.__name__) ###################################################################### # FeatureValueSet & FeatureValueTuple ######################################################################
""" A mixin class for sequence clases that distributes variables() and substitute_bindings() over the object's elements. """ sum([list(elt.variables()) for elt in self if isinstance(elt, SubstituteBindingsI)], []))
else:
""" A base feature value that is a tuple of other base feature values. FeatureValueTuple implements ``SubstituteBindingsI``, so it any variable substitutions will be propagated to the elements contained by the set. A ``FeatureValueTuple`` is immutable. """
""" A base feature value that is a set of other base feature values. FeatureValueSet implements ``SubstituteBindingsI``, so it any variable substitutions will be propagated to the elements contained by the set. A ``FeatureValueSet`` is immutable. """ # n.b., we sort the string reprs of our elements, to ensure # that our own repr is deterministic.
""" A base feature value that represents the union of two or more ``FeatureValueSet`` or ``Variable``. """ # If values contains FeatureValueUnions, then collapse them.
# If the resulting list contains no variables, then # use a simple FeatureValueSet instead.
# If we contain a single variable, return that variable. return list(values)[0]
# Otherwise, build the FeatureValueUnion.
# n.b., we sort the string reprs of our elements, to ensure # that our own repr is deterministic. also, note that len(self) # is guaranteed to be 2 or more.
""" A base feature value that represents the concatenation of two or more ``FeatureValueTuple`` or ``Variable``. """ # If values contains FeatureValueConcats, then collapse them.
# If the resulting list contains no variables, then # use a simple FeatureValueTuple instead.
# If we contain a single variable, return that variable. return list(values)[0]
# Otherwise, build the FeatureValueConcat.
# n.b.: len(self) is guaranteed to be 2 or more.
""" Helper function -- return a copy of list, with all elements of type ``cls`` spliced in rather than appended in. """
###################################################################### # Specialized Features ######################################################################
""" A feature identifier that's specialized to put additional constraints, default values, etc. """
else:
def name(self): """The name of this feature."""
def default(self): """Default value for this feature."""
def display(self): """Custom display location: can be prefix, or slash."""
return not (self == other)
#//////////////////////////////////////////////////////////// # These can be overridden by subclasses: #////////////////////////////////////////////////////////////
""" If possible, return a single value.. If not, return the value ``UnificationFailure``. """ else: return UnificationFailure
###################################################################### # Specialized Feature Values ######################################################################
""" An abstract base class for base values that define a custom unification method. The custom unification method of ``CustomFeatureValue`` will be used during unification if:
- The ``CustomFeatureValue`` is unified with another base value. - The ``CustomFeatureValue`` is not the value of a customized ``Feature`` (which defines its own unification method).
If two ``CustomFeatureValue`` objects are unified with one another during feature structure unification, then the unified base values they return *must* be equal; otherwise, an ``AssertionError`` will be raised.
Subclasses must define ``unify()``, ``__eq__()`` and ``__lt__()``. Subclasses may also wish to define ``__hash__()``. """ """ If this base value unifies with ``other``, then return the unified value. Otherwise, return ``UnificationFailure``. """ raise NotImplementedError('abstract base class')
raise NotImplementedError('__cmp__ is deprecated')
raise NotImplementedError('abstract base class')
raise NotImplementedError('abstract base class')
raise TypeError('%s objects or unhashable' % self.__class__.__name__)
###################################################################### # Feature Structure Parser ######################################################################
flist_class=FeatList, logic_parser=None): raise ValueError('Multiple features w/ display=slash') raise ValueError('Multiple features w/ display=prefix') if feature.default is not None]
""" Convert a string representation of a feature structure (as displayed by repr) into a ``FeatStruct``. This parse imposes the following restrictions on the string representation:
- Feature names cannot contain any of the following: whitespace, parentheses, quote marks, equals signs, dashes, commas, and square brackets. Feature names may not begin with plus signs or minus signs. - Only the following basic feature value are supported: strings, integers, variables, None, and unquoted alphanumeric strings. - For reentrant values, the first mention must specify a reentrance identifier and a value; and any subsequent mentions must use arrows (``'->'``) to reference the reentrance identifier. """
# This one is used to distinguish fdicts from flists: _BARE_PREFIX_RE.pattern, _START_FSTRUCT_RE.pattern, _FEATURE_NAME_RE.pattern, _FEATURE_NAME_RE.pattern))
""" Helper function that parses a feature structure.
:param s: The string to parse. :param position: The position in the string to start parsing. :param reentrances: A dictionary from reentrance ids to values. Defaults to an empty dictionary. :return: A tuple (val, pos) of the feature structure created by parsing and the position where the parsed feature structure ends. :rtype: bool """
# Create the new feature structure else:
# Read up to the open bracket.
# If there as an identifier, record it. raise ValueError('new identifier', match.start(1))
reentrances, fstruct) else: reentrances, fstruct)
reentrances, fstruct): # Prefix features are not allowed: # Bare prefixes are not allowed:
# Build a list of the features defined by the structure. # Check for the close bracket.
# Reentances have the form "-> (target)" position = match.end() match = _TARGET_RE.match(s, position) if not match: raise ValueError('identifier', position) target = match.group(1) if target not in reentrances: raise ValueError('bound identifier', position) position = match.end() fstruct.append(reentrances[target])
# Anything else is a value. else: self._parse_value(0, s, position, reentrances))
# If there's a close bracket, handle it at the top of the loop.
# Otherwise, there should be a comma
# We never saw a close bracket. raise ValueError('close bracket', position)
reentrances, fstruct): # If there was a prefix feature, record it. raise ValueError('open bracket or identifier', match.start(2))
# If group 3 is empty, then we just have a bare prefix, so # we're done.
# Build a list of the features defined by the structure. # Each feature has one of the three following forms: # name = value # name -> (target) # +name # -name # Use these variables to hold info about each feature:
# Check for the close bracket.
# Get the feature name's name
# Check if it's a special feature. raise ValueError('known special feature', match.start(2))
# Check if this feature has a value already. raise ValueError('new name', match.start(2))
# Boolean value ("+name" or "-name")
# Reentrance link ("-> (target)")
# Assignment ("= value"). self._parse_value(name, s, position, reentrances)) # None of the above: error. else: raise ValueError('equals sign', position)
# Store the value.
# If there's a close bracket, handle it at the top of the loop.
# Otherwise, there should be a comma
# We never saw a close bracket. raise ValueError('close bracket', position)
""" Called when we see the close brace -- checks for a slash feature, and adds in default values. """ # Add the slash feature (if any) ## Add any default features. -- handle in unficiation instead? #for feature in self._features_with_defaults: # fstruct.setdefault(feature, feature.default) # Return the value.
else:
position -= len(lines.pop(0))+1 # +1 for the newline. lines[0] + '\n ' + ' '*position + '^ ' + 'Expected %s' % expected)
#//////////////////////////////////////////////////////////// #{ Value Parsers #////////////////////////////////////////////////////////////
#: A table indicating how feature values should be parsed. Each #: entry in the table is a pair (handler, regexp). The first entry #: with a matching regexp will have its handler called. Handlers #: should have the following signature:: #: #: def handler(s, position, reentrances, match): ... #: #: and should return a tuple (value, position), where position is #: the string position where the value ended. (n.b.: order is #: important here!) ('parse_fstruct_value', _START_FSTRUCT_RE), ('parse_var_value', re.compile(r'\?[a-zA-Z_][a-zA-Z0-9_]*')), ('parse_str_value', re.compile("[uU]?[rR]?(['\"])")), ('parse_int_value', re.compile(r'-?\d+')), ('parse_sym_value', re.compile(r'[a-zA-Z_][a-zA-Z0-9_]*')), ('parse_app_value', re.compile(r'<(app)\((\?[a-z][a-z]*)\s*,' r'\s*(\?[a-z][a-z]*)\)>')), # ('parse_logic_value', re.compile(r'<([^>]*)>')), #lazily match any character after '<' until we hit a '>' not preceded by '-' ('parse_logic_value', re.compile(r'<(.*?)(?<!-)>')), ('parse_set_value', re.compile(r'{')), ('parse_tuple_value', re.compile(r'\(')), ]
# Note: the '?' is included in the variable name.
"""Mainly included for backwards compat."""
except ParseException: raise ValueError() except ValueError: raise ValueError('logic expression', match.start(1))
FeatureValueTuple, FeatureValueConcat)
FeatureValueSet, FeatureValueUnion)
close_paren, seq_class, plus_class): """ Helper function used by parse_tuple_value and parse_set_value. """ # Special syntax fo empty tuples: # Read values: # Close paren: return value.
# Read the next value.
# Comma or looking at close paren
###################################################################### #{ Demo ######################################################################
# Print the two input feature structures, side by side. fs1_lines = str(fs1).split('\n') fs2_lines = str(fs2).split('\n') if len(fs1_lines) > len(fs2_lines): blankline = '['+' '*(len(fs2_lines[0])-2)+']' fs2_lines += [blankline]*len(fs1_lines) else: blankline = '['+' '*(len(fs1_lines[0])-2)+']' fs1_lines += [blankline]*len(fs2_lines) for (fs1_line, fs2_line) in zip(fs1_lines, fs2_lines): print(indent + fs1_line + ' ' + fs2_line) print(indent+'-'*len(fs1_lines[0])+' '+'-'*len(fs2_lines[0]))
linelen = len(fs1_lines[0])*2+3 print(indent+'| |'.center(linelen)) print(indent+'+-----UNIFY-----+'.center(linelen)) print(indent+'|'.center(linelen)) print(indent+'V'.center(linelen))
bindings = {}
result = fs1.unify(fs2, bindings) if result is None: print(indent+'(FAILED)'.center(linelen)) else: print('\n'.join(indent+l.center(linelen) for l in str(result).split('\n'))) if bindings and len(bindings.bound_variables()) > 0: print(repr(bindings).center(linelen)) return result
import random, sys
HELP = ''' 1-%d: Select the corresponding feature structure q: Quit t: Turn tracing on or off l: List all feature structures ?: Help '''
print(''' This demo will repeatedly present you with a list of feature structures, and ask you to choose two for unification. Whenever a new feature structure is generated, it is added to the list of choices that you can pick from. However, since this can be a large number of feature structures, the demo will only print out a random subset for you to choose between at a given time. If you want to see the complete lists, type "l". For a list of valid commands, type "?". ''') print('Press "Enter" to continue...') sys.stdin.readline()
fstruct_strings = [ '[agr=[number=sing, gender=masc]]', '[agr=[gender=masc, person=3]]', '[agr=[gender=fem, person=3]]', '[subj=[agr=(1)[]], agr->(1)]', '[obj=?x]', '[subj=?x]', '[/=None]', '[/=NP]', '[cat=NP]', '[cat=VP]', '[cat=PP]', '[subj=[agr=[gender=?y]], obj=[agr=[gender=?y]]]', '[gender=masc, agr=?C]', '[gender=?S, agr=[gender=?S,person=3]]' ]
all_fstructs = [(i, FeatStruct(fstruct_strings[i])) for i in range(len(fstruct_strings))]
def list_fstructs(fstructs): for i, fstruct in fstructs: print() lines = str(fstruct).split('\n') print('%3d: %s' % (i+1, lines[0])) for line in lines[1:]: print(' '+line) print()
while True: # Pick 5 feature structures at random from the master list. MAX_CHOICES = 5 if len(all_fstructs) > MAX_CHOICES: fstructs = sorted(random.sample(all_fstructs, MAX_CHOICES)) else: fstructs = all_fstructs
print('_'*75)
print('Choose two feature structures to unify:') list_fstructs(fstructs)
selected = [None,None] for (nth,i) in (('First',0), ('Second',1)): while selected[i] is None: print(('%s feature structure (1-%d,q,t,l,?): ' % (nth, len(all_fstructs))), end=' ') try: input = sys.stdin.readline().strip() if input in ('q', 'Q', 'x', 'X'): return if input in ('t', 'T'): trace = not trace print(' Trace = %s' % trace) continue if input in ('h', 'H', '?'): print(HELP % len(fstructs)); continue if input in ('l', 'L'): list_fstructs(all_fstructs); continue num = int(input)-1 selected[i] = all_fstructs[num][1] print() except: print('Bad sentence number') continue
if trace: result = selected[0].unify(selected[1], trace=1) else: result = display_unification(selected[0], selected[1]) if result is not None: for i, fstruct in all_fstructs: if repr(result) == repr(fstruct): break else: all_fstructs.append((len(all_fstructs), result))
print('\nType "Enter" to continue unifying; or "q" to quit.') input = sys.stdin.readline().strip() if input in ('q', 'Q', 'x', 'X'): return
""" Just for testing """ #import random
# parser breaks with values like '3rd' fstruct_strings = [ '[agr=[number=sing, gender=masc]]', '[agr=[gender=masc, person=3]]', '[agr=[gender=fem, person=3]]', '[subj=[agr=(1)[]], agr->(1)]', '[obj=?x]', '[subj=?x]', '[/=None]', '[/=NP]', '[cat=NP]', '[cat=VP]', '[cat=PP]', '[subj=[agr=[gender=?y]], obj=[agr=[gender=?y]]]', '[gender=masc, agr=?C]', '[gender=?S, agr=[gender=?S,person=3]]' ] all_fstructs = [FeatStruct(fss) for fss in fstruct_strings] #MAX_CHOICES = 5 #if len(all_fstructs) > MAX_CHOICES: #fstructs = random.sample(all_fstructs, MAX_CHOICES) #fstructs.sort() #else: #fstructs = all_fstructs
for fs1 in all_fstructs: for fs2 in all_fstructs: print("\n*******************\nfs1 is:\n%s\n\nfs2 is:\n%s\n\nresult is:\n%s" % (fs1, fs2, unify(fs1, fs2)))
demo()
'Feature', 'SlashFeature', 'RangeFeature', 'SLASH', 'TYPE', 'FeatStructParser'] |