Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

Statistical parsing of English sentences

, 13 Dec 2006
Shows how to generate parse trees for English language sentences, using a C# port of OpenNLP, a statistical natural language parsing library.
englishparsing_bin.zip
englishparsing_net2_0_bin.zip
englishparsing_net2_0_src.zip
Lithium
Collections
Delegates
Enums
Interfaces
IO
Lithium.csproj.vspscc
LithiumControl.bmp
Shapes
UI
Visitors
ModelConverter
App.ico
ModelConverter.csproj.vspscc
ParseTree
App.ico
ParseTree.csproj.vspscc
ToolsExample
App.ico
ToolsExample.csproj.vspscc
OpenNLP
OpenNLP.csproj.vspscc
SharpEntropy.dll
Tools
Chunker
NameFind
Parser
PosTagger
SentenceDetect
Tokenize
Util
englishparsing_src.zip
Lithium.csproj.user
LithiumControl.bmp
App.ico
ModelConverter.csproj.user
OpenNLP.csproj.user
SharpEntropy.dll
vssver.scc
vssver.scc
vssver.scc
vssver.scc
vssver.scc
vssver.scc
vssver.scc
App.ico
ParseTree.csproj.user
App.ico
ToolsExample.csproj.user
//Copyright (C) 2005 Richard J. Northedge
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

//This file is based on the Cache.java source file found in the
//original java implementation of OpenNLP.  That source file contains the following header:

//Copyright (C) 2003 Jeremy LaCivita and Thomas Morton
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

using System;
using System.Collections;
using System.Text;

namespace OpenNLP.Tools.Util
{
	/// <summary>
	///  Provides fixed size, pre-allocated, least recently used replacement cache.
	///  </summary>
	public class Cache : IDictionary
	{
		/// <summary>
		/// The element in the linked list which was most recently used.
		/// </summary>
		private DoubleLinkedListElement mFirstElement;

		/// <summary>
		/// The element in the linked list which was least recently used.
		/// </summary>
		private DoubleLinkedListElement mLastElement;

		/// <summary>
		/// Temporary holder of the key of the least-recently-used element.
		/// </summary>
		private object mLastKey;

		/// <summary>
		/// Temporary value used in swap.
		/// </summary>
		private ObjectWrapper mTempSwapWrapper;

		/// <summary>
		/// Holds the object wrappers which the keys are mapped to.
		/// </summary>
		private ObjectWrapper[] mWrappers;

		/// <summary>
		/// Hashtable which stores the keys and values of the cache.
		/// </summary>
		private Hashtable mMap;

		/// <summary>
		/// The size of the cache.
		/// </summary>
		private int mCacheSize;

		public virtual ICollection Keys
		{
			get
			{
				return new Set(mMap.Keys);
			}
			
		}
		public virtual int Count
		{
			get
			{
				return mMap.Count;
			}
			
		}
		public virtual ICollection Values
		{
			get
			{
				return mMap.Values;
			}
			
		}
		
		/// <summary>
		/// Creates a new cache of the specified size.
		/// </summary>
		/// <param name="size">
		/// The size of the cache.
		/// </param>
		public Cache(int size)
		{
			mMap = new Hashtable(size);
			mWrappers = new ObjectWrapper[size];
			mCacheSize = size;
			object item = new object();
			mFirstElement = new DoubleLinkedListElement(null, null, item);
			object tempObject;
			tempObject = new ObjectWrapper(null, mFirstElement);
			mMap[item] = tempObject;
			mWrappers[0] = new ObjectWrapper(null, mFirstElement);
			
			DoubleLinkedListElement element = mFirstElement;
			for (int iCurrentItem = 1; iCurrentItem < mCacheSize; iCurrentItem++)
			{
				item = new object();
				element = new DoubleLinkedListElement(element, null, item);
				mWrappers[iCurrentItem] = new ObjectWrapper(null, element);
				object tempObject2;
				tempObject2 = mWrappers[iCurrentItem];
				mMap[item] = tempObject2;
				element.Previous.Next = element;
			}
			mLastElement = element;
		}
		
		public virtual void Clear()
		{
			mMap.Clear();
			DoubleLinkedListElement element = mFirstElement;

			for (int currentItem = 0; currentItem < mCacheSize; currentItem++)
			{
				mWrappers[currentItem].Item = null;
				object o = new object();
				mMap.Add(o, mWrappers[currentItem]);
				element.Item = o;
				element = element.Next;
			}
		}
		
		public object this[object key]
		{
			get
			{
				ObjectWrapper wrapper = (ObjectWrapper) mMap[key];

				if (wrapper != null)
				{
					// Move it to the front
					DoubleLinkedListElement element = (DoubleLinkedListElement) wrapper.ListItem;
				
					//move to front
					if (element != mFirstElement)
					{
						//remove list item
						element.Previous.Next = element.Next;
						if (element.Next != null)
						{
							element.Next.Previous = element.Previous;
						}
						else
						{
							//were moving last
							mLastElement = element.Previous;
						}
						//put list item in front
						element.Next = mFirstElement;
						mFirstElement.Previous = element;
						element.Previous = null;
					
						//update first
						mFirstElement = element;
					}
					return wrapper.Item;
				}
				else
				{
					return null;
				}
			}

			set
			{
				
				ObjectWrapper wrapper = (ObjectWrapper) mMap[key];
				if (wrapper != null)
				{
					/* this should never be the case, we only do a put on a cache miss which 
					means the current value wasn't in the cache.  However if the user 
					screws up or wants to use this as a fixed size hash and puts the same 
					thing in the list twice things break
					*/

					//System.err.println("Cache.put: inserting same object into cache!!!!");
					// Move wrapper's partner in the list to front
					DoubleLinkedListElement element = wrapper.ListItem;
				
					//move to front
					if (element != mFirstElement)
					{
						//remove list item
						element.Previous.Next = element.Next;
						if (element.Next != null)
						{
							element.Next.Previous = element.Previous;
						}
						else
						{
							//were moving last
							mLastElement = element.Previous;
						}
					
						//put list item in front
						element.Next = mFirstElement;
						mFirstElement.Previous = element;
						element.Previous = null;
					
						//update first
						mFirstElement = element;
					}
					return; 
				}
				// Put wrapper in the front and remove the last one
				mLastKey = mLastElement.Item; // store key to remove from hash later
				mLastElement.Item = key; //update list element with new key
			
				// connect list item to front of list
				mLastElement.Next = mFirstElement;
				mFirstElement.Previous = mLastElement;
			
				// update first and last value
				mFirstElement = mLastElement;
				mLastElement = mLastElement.Previous;
				mFirstElement.Previous = null;
				mLastElement.Next = null;
			
				// remove old value from cache
				mTempSwapWrapper = (ObjectWrapper) mMap[mLastKey];
				mMap.Remove(mLastKey);
				
				//update wrapper
				mTempSwapWrapper.Item = value;
				mTempSwapWrapper.ListItem = mFirstElement;
			
				object tempObject;
				tempObject = mTempSwapWrapper;
				mMap[key] = tempObject;
			}
		}
		
		public bool ContainsKey(object key)
		{
			return mMap.ContainsKey(key);
		}
		
		public bool Contains(object dataValue)
		{
			return mMap.Contains(dataValue);
		}
		
		public Set EntrySet()
		{
			IDictionaryEnumerator hashEnumerator = mMap.GetEnumerator();
			Set hashSet = new Set();
			while(hashEnumerator.MoveNext())
			{
				Hashtable tempHash = new Hashtable();
				tempHash.Add(hashEnumerator.Key, hashEnumerator.Value);
				hashSet.Add(tempHash.GetEnumerator());
			}
			return hashSet;
		}
		
		public bool IsEmpty()
		{
			return (mMap.Count == 0);
		}
		
		public void PutAll(IDictionary source)
		{
			object[] keys = new object[source.Keys.Count];
			object[] values = new object[source.Values.Count];

			source.Keys.CopyTo(keys, 0);
			source.Values.CopyTo(values, 0);

			for (int index = 0; index < source.Keys.Count; index++)
			{
				mMap[keys.GetValue(index)] = values.GetValue(index);
			}
		}
		
		public virtual void Remove(object key)
		{
			mMap.Remove(key);
		}

		public bool IsSynchronized
		{
			get
			{
				return mMap.IsSynchronized;
			}
		}

		public object SyncRoot
		{
			get
			{
				return mMap.SyncRoot;
			}
		}
        
		public void CopyTo(System.Array copyArray, int arrayIndex)
		{
			mMap.CopyTo(copyArray, arrayIndex);
		}

		public void Add(object key, object dataValue)
		{
			throw new NotSupportedException("cannot add to a fixed size cache");
		}

		public bool IsFixedSize
		{
			get
			{
				return true;
			}
		}

		public bool IsReadOnly
		{
			get
			{
				return false;
			}
		}

		public IDictionaryEnumerator GetEnumerator()
		{
			return mMap.GetEnumerator();
		}    

		IEnumerator IEnumerable.GetEnumerator()
		{
			return mMap.GetEnumerator();
		}
	}
	
	class ObjectWrapper
	{
		public virtual object Item
		{
			get
			{
				return mItem;
			}
			
			set
			{
				mItem = value;
			}
			
		}
		virtual public DoubleLinkedListElement ListItem
		{
			get
			{
				return mListItem;
			}
			
			set
			{
				mListItem = value;
			}
			
		}
		
		private object mItem;
		private DoubleLinkedListElement mListItem;
		
		public ObjectWrapper(object item, DoubleLinkedListElement listItem)
		{
			mItem = item;
			mListItem = listItem;
		}
		
		public override bool Equals(object compare)
		{
			return mItem.Equals(compare);
		}

		public override int GetHashCode()
		{
			return mItem.GetHashCode();
		}
	}
	
	/// <summary>
	/// An entry in a double-linked list.
	/// </summary>
	public class DoubleLinkedListElement
	{
		private DoubleLinkedListElement mPrevious;
		private DoubleLinkedListElement mNext;
		private object mItem;
		
		public DoubleLinkedListElement Previous
		{
			get
			{
				return mPrevious;
			}
			set
			{
				mPrevious = value;
			}
		}

		public DoubleLinkedListElement Next
		{
			get
			{
				return mNext;
			}
			set
			{
				mNext = value;
			}
		}

		public object Item
		{
			get
			{
				return mItem;
			}
			set
			{
				mItem = value;
			}
		}

		public DoubleLinkedListElement(DoubleLinkedListElement previousElement, DoubleLinkedListElement nextElement, object item)
		{
			mPrevious = previousElement;
			mNext = nextElement;
			mItem = item;
			
			if (previousElement != null)
			{
				previousElement.Next = this;
			}
			
			if (nextElement != null)
			{
				nextElement.Previous = this;
			}
		}
	}
	
	/// <summary>
	/// A double-linked list implementation.
	/// </summary>
	public class DoubleLinkedList
	{
		virtual public DoubleLinkedListElement GetFirst()
		{
			Current = First;
			return First;
		}

		virtual public DoubleLinkedListElement GetLast()
		{
			Current = Last;
			return Last;
		}
		virtual public DoubleLinkedListElement GetCurrent()
		{
			return Current;
		}
		
		internal DoubleLinkedListElement First;
		internal DoubleLinkedListElement Last;
		internal DoubleLinkedListElement Current;
		
		public DoubleLinkedList()
		{
			First = null;
			Last = null;
			Current = null;
		}
		
		public virtual void AddFirst(object item)
		{
			First = new DoubleLinkedListElement(null, First, item);
			
			if (Current.Next == null)
			{
				Last = Current;
			}
		}
		
		public virtual void AddLast(object item)
		{
			Last = new DoubleLinkedListElement(Last, null, item);
			
			if (Current.Previous == null)
			{
				First = Current;
			}
		}
		
		public virtual void Insert(object item)
		{
			if (Current == null)
			{
				Current = new DoubleLinkedListElement(null, null, item);
			}
			else
			{
				Current = new DoubleLinkedListElement(Current.Previous, Current, item);
			}
			
			if (Current.Previous == null)
			{
				First = Current;
			}
			
			if (Current.Next == null)
			{
				Last = Current;
			}
		}
		
		public virtual DoubleLinkedListElement Next()
		{
			if (Current.Next != null)
			{
				Current = Current.Next;
			}
			return Current;
		}
		
		public virtual DoubleLinkedListElement Previous()
		{
			if (Current.Previous != null)
			{
				Current = Current.Previous;
			}
			return Current;
		}
		
		public override string ToString()
		{
			DoubleLinkedListElement element = First;
			StringBuilder buffer = new StringBuilder();
			buffer.Append("[").Append(element.Item.ToString());
			
			element = element.Next;
			
			while (element != null)
			{
				buffer.Append(", ").Append(element.Item.ToString());
				element = element.Next;
			}
			
			buffer.Append("]");
			
			return buffer.ToString();
		}
	}
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

Richard Northedge
Web Developer
United Kingdom United Kingdom
Richard Northedge is a senior developer with a UK Microsoft Gold Partner company. He has a postgraduate degree in English Literature, has been programming professionally since 1998 and has been an MCSD since 2000.

| Advertise | Privacy | Mobile
Web04 | 2.8.140827.1 | Last Updated 13 Dec 2006
Article Copyright 2005 by Richard Northedge
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid