[Adonthell-devel] indexing of quest logs

[Kai Sterker]

Since an index will probably have 100 entries and more in the final 
game, simple full-text indexing will definitely not work. To speed this 
up, I have thought about the following:

* the index itself is split up into multiple parts, with the first 
letter of
  each word as key. Individual entries are kept in a hash table.
* whenever a text is indexed, all the words it contains are also sorted 
by
  first letter. Words shorter than any entry in the index are omitted. 
That
  means, the number of words to compare are already greatly reduced. 
Further,
  they need not be compared against all index entries, only with those 
that
  have already matching first letters.
* finally, for all remaining words of the text, the matching index 
entry is
  retrieved from its hash table. If there is an entry, the uid of the 
text
  can be added, otherwise we continue with the next word of the text.

With these measures, indexing in realtime shouldn't be any problem, 
even with large index and long texts.


I briefly thought about specifying the index keys for a log entry in 
advance. The advantage is that an entry can be indexed even though it 
does not contain the required keyword. OTOH, it means more work for 
writers, and its easy to forget adding index entries. Should it really 
be required for certain log entries, we can make it an optional feature.


I have committed a first implementation. There is a test script 
(test/logtest.py) and if you update -d, you also get the required test 
data. I just used the texts from our library, which are much longer 
than an average log entry will be. Still, all of them are indexed in 
about 0.2 - 0.3 seconds on my 800Mhz iBook. That should be sufficiently 
fast. Still, I plan to change the code a little, as there are one or 
two problems left.

Kai

P.S: there's also another new test script (itemtest.py) which does some 
inventory/item tests. Not completely done yet, though ...