What kind of data structures could be used in a natural language processing project?

I have worked in the area of NLP for a while, and like most people who work in NLP, never focussed on what Data Structures to choose, as opposed to what techniques to apply. Let's understand how data structures will be useful in NLP based projects. Besides storing and retrieving text (strings), data structures would not play other part, in determining the performance of the outcome. What we need is efficient storage and faster retrieval of text, in projects of these sorts. So keeping the above in mind, my choice would be "trees", "heaps", and "hashtable". Blatant Self Promotion: We recently released a sentiment analysis tool called http://texsie.tationem.com , in which we leveraged some of the above mentioned data structures.

There are some more specific data structures for NLP when dealing with ambiguity, which is encountered in all aspects of NLP. Word lattices are used in early stages in both speech and text segmentation. They are a specific kind of Directed acyclic graph (DAG). Confusion networks seem to be a more advanced/powerful relative of the lattice just mentioned. Parse forests are ambiguity-supporting relatives of parse trees. One key subtype is the Shared packed parse forest (SPPF). I am not an expert, just an interested amature ploughing through papers in the field.