Re: trie

25 jul 2005 kl. 19.18 skrev Per Nyfelt:
>
> Very interesting. Have you looked at JXPath from apache commons?

Not yet. But I'm planning to add a layer of OCL (the object  
constraint language) to enable the kind of queries you listed.

> How would you compare your efforts with Lucene which is quite a  
> full featured
> indexing and search engine?

I don't aim to replace Lucene. This is more of a HashMap/HashSet- 
replacement. A small implementation for small use. I've refactored  
and optimized quite a bit since the last post.

                            {1}
   [Query]-------->[Trie]-------><#>[TrieWriter]
                      |
                      |
                      | + rootNode
                  {1} |
                      V
               +--->[Node](reference:Object)--- {0..1} ->[/ 
ReferenceMetaData/]
        {0..*} |      |
     +children |      |
               +------+


Here is some output from my 1.5GHz Powerbook G4 768MB using a case  
insensitive index:

import all java files recursive of /Users/kalle/projects
Time spent: 0ms since start.

files imported. total size: 7988k.
Time spent: 2344ms since start.

trie populated. memory in use by trie 27M, or 3.585573 bytes per 1  
byte of index data.
Time spent: 11416ms since start, 9072ms since touched.

query trie with ('to?o' OR ('log*' NOT 'warning*')))
Time spent: 11448ms since start, 32ms since touched.

gathered 396 results.
Time spent: 11514ms since start, 66ms since touched.

/Users/kalle/projects/ozone/ozone/modules/xml/dom/src/org/ozoneDB/xml/ 
dom/DocumentImpl.java
occurances in hit: 1, path in index: 'logging' file: /Users/kalle/ 
projects/ozone/ozone/modules/xml/dom/src/org/ozoneDB/xml/dom/ 
DocumentImpl.java
occurances in hit: 2, path in index: 'todo' file: /Users/kalle/ 
projects/ozone/ozone/modules/xml/dom4j/src/org/ozoneDB/xml/dom4j/io/ 
O3SAXReader.java
occurances in hit: 18, path in index: 'log' file: /Users/kalle/ 
projects/ozone/ozone/server/samples/OO1/CattellImpl.java
occurances in hit: 7, path in index: 'logmessage' file: /Users/kalle/ 
projects/ozone/ozone/server/samples/OO1/CattellImpl.java
occurances in hit: 9, path in index: 'logtime' file: /Users/kalle/ 
projects/ozone/ozone/server/samples/OO1/CattellImpl.java
occurances in hit: 1, path in index: 'todo' file: /Users/kalle/ 
projects/ozone/ozone/modules/xml/dom/src/org/xmldb/api/sdk/modules/ 
SetContentHandler.java
occurances in hit: 1, path in index: 'todo' file: /Users/kalle/ 
projects/ozone/ozone/modules/xml/dom4j/src/test/dom4j/datatype/ 
TestDataTypes.java
occurances in hit: 3, path in index: 'todo' file: /Users/kalle/ 
projects/ozone/ozone/server/src/org/ozoneDB/ExternalDatabase.java


-- 

   kalle