implementing feature structures: what data type to use?
- by Dervin Thunk
Hello.
In simplistic terms, a feature structure is an unordered list of attribute-value pairs.
[number:sg, person:3 | _ ],
which can be embedded:
[cat:np, agr:[number:sg, person:3 | _ ] | _ ],
can subindex stuff and share the value
[number:[1], person:3 | _ ],
where [1] is another feature structure (that is, it allows reentrancy).
My question is: what data structure would people think this should be implemented with for later access to values, to perform unification between 2 fts, to "type" them, etc.
There is a full book on this, but it's in lisp, which simplifies list handling. So, my choices are: a hash of lists, a list of lists, or a trie. What do people think about this?
