The index to use for full-text search is a GiST index, and there is nothing heuristic about it (except the "picksplit" algorithm). "fulltextindex" was removed in 8.2, and full text search got added to core in 8.3, so that's what you should use.
Read the WARNING file from release 8.1:
WARNING
-------
This implementation of full text indexing is very slow and inefficient. It is
STRONGLY recommended that you switch to using contrib/tsearch which offers these
features:
Advantages
----------
* Actively developed and improved
* Tight integration with OpenFTS (openfts.sourceforge.net)
* Orders of magnitude faster (eg. 300 times faster for two keyword search)
* No extra tables or multi-way joins required
* Select syntax allows easy 'and'ing, 'or'ing and 'not'ing of keywords
* Built-in stemmer with customisable dictionaries (ie. searching for 'jellies' will find 'jelly')
* Stop words automatically ignored
* Supports non-C locales
Disadvantages
-------------
* Only indexes full words - substring searches on words won't work.
eg. Searching for 'burg' won't find 'burger'
Due to the deficiencies in this module, it is quite likely that it will be removed from the standard PostgreSQL distribution in the future.
PostgreSQL is open source. To see the discussion that led to the removal of the module, search the archives. You will find this and this.