[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Adonthell-devel] indexing of quest logs
From: |
Kai Sterker |
Subject: |
[Adonthell-devel] indexing of quest logs |
Date: |
Sat, 3 Jul 2004 09:36:50 +0200 |
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 ...
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Adonthell-devel] indexing of quest logs,
Kai Sterker <=