RE: [Please Help] Pattern Matching Comparison

[Scott Dossey <sdossey@xxxxxxxx>]

	>     PAT Tree: easy to do exact & sub pattern matching. The problem
is space. It
	>takes about 4 ^ 100 = 10^60 tree nodes. You know how terribly big
10^60 is. Some
	>of you on this list (Mark the Ph.D.?) was using PAT, I don't know
how he could
	>handle so big a PAT tree.


	Why don't you consider a suffix tree?  It has all the power of a
Patricia tree but takes up linear space.  It's searching time for an
arbitrary substring will be proportional to X where X is the number of
tokens in the substring.  It's insertion time is constant.  

	It's a very powerful data structure.  With a suffix tree a linear
time and linear space sorting algorithm WORST case was created.  It doesn't
conform to the NlogN bound that was formerly proven for a comparison based
sort, because it is a classification sort.

	It is an extremely powerful data structure, and I highly recommend
it for any situation where substring matching is necessary.  Unfortunately,
it is not the easiest data structrue to implement.
http://dogma.net/markn/articles/suffixt/suffixt.htm for more information.

	-Scott Dossey.