On 8/2/06, Julien Lemoine <speedblue(a)happycoders.org> wrote: How long does the compiling take? How close to a real-time update could it be? This seems to be a recurring problem with search etc at Wikipedia - the fact that it's always at best a few days out of date, and sometimes months. Then with the problems with toolserver... Steve

On 8/2/06, Julien Lemoine <speedblue(a)happycoders.org> wrote: I would be interested to hear from the server admins on the feasibility of integrating this tool in Wikipedia - particularly that compilation time. Steve

Hello, Simetrical wrote: Here is the time output of compiler for the analysis of wikipedia english articles : 622,65s user 53,69s system 70% cpu 15:58,91 total 95% of this time (16mins) was to read the files from disk (with a fresh reboot so nothing was in the cache). The algorithm uses very few cpu power. Imagine for example that all the data needed are in memory, the compiled automaton could be obtained in 1 minutes. Best Regards. Julien Lemoine

Hello, Simetrical wrote: The search uses very few resources (only RAM to store the index). The complexity in the worst case is O(log(A) * P) where A is the number of letter in Alphabet and P the size of the word to search. I wrote two implementations : - monothreaded with index stored on disk (I implemented it for my server because I have few RAM available) - multithreaded version with all index in RAM With the second one, you will be able to handle a lot of queries per second with very few cpu power. Best Regards. Julien Lemoine

Hello, Timwi wrote: Yes this is a directed graph, each transition from one node to another is labeled by one UTF-8 character. This graph is deterministic, you can not have two identic transitions at the output of a node. For each article I added the name of the article in this automaton, with the final node containing a pointer to articles details (url, name, nb of links). After article names were added in automaton, I computed the table of best content for each node containing pointer to articles with the higher number of links. I talked about pointers, these pointers are index to a vector storing all details about articles. You can have a small example (figure) in my FAQ : http://suggest.speedblue.org/FAQ.php I can give you more details about number of nodes/transitions in the automaton if you want. I hope this give you a more precise idea of how it works. Please, don't hesitate to ask me more details. Best Regards. Julien Lemoine

On 8/3/06, Timwi <timwi(a)gmx.net> wrote: The right data structure for this sort of thing is called a "trie", and Googling it will turn up lots of information. Though I'm not sure if the original poster knows this term.

Evan Martin wrote: I know, and his is indeed a trie. But that word is rarely used. Look at his work: He has perfectly implemented a trie with a lot of thought, but without knowing the word "trie" :-p Timwi

On Fri, Aug 04, 2006 at 08:03:22AM +0200, Julien Lemoine wrote: It would require you to apply some heuristics to determine what *not* to display, certainly... but let me note that the incremental search feature in the phone book of my Blackberry -- which displays a list of first, the entries whose titles *start* with the substring, and then, the entries which contain it elsewhere -- is pretty useful. It interacts with the height of the pulldown, of course, but it is pretty useful. Cheers, -- jra -- Jay R. Ashworth jra(a)baylink.com Designer Baylink RFC 2100 Ashworth & Associates The Things I Think '87 e24 St Petersburg FL USA http://baylink.pitas.com +1 727 647 1274 The Internet: We paved paradise, and put up a snarking lot.