Data structure for search engine in JAVA?

Question

Hi,

I m MCS 2nd year student.I m doing a project in Java in which I have different images. For storing description of say IMAGE-1, I have ArrayList named IMAGE-1, similarly for IMAGE-2 ArrayList IMAGE-2 n so on.....

Now I need to develop a search engine, in which i need to find a all image's whose description matches with a word entered in search engine..........

FOR EX If i enter "computer" then I should be able to find all images whose description contain "computer".

So my question is...

How should i do this efficiently?
How should i maintain all those ArrayList since i can have 100 of such...? or should i use another data structure instead of ArrayList?

Answer 1

I would suggest you to use the Hashtable class or to organize your content into a tree to optimize searching.

Answer 2

If you have a small number of images and short descriptions (< 1000 characters), load them into an array and search for words using String.indexOf() (i.e. one entry in the array == one complete image description). This is efficient enough for, say, less than 10'000 images.

Use toLowerCase() to fold the case of the characters (so users will find "Computer" when they type "computer"). String.indexOf() will also work for short words (using "comp" to find "Computer" or "compare").

If you have lots of images and long descriptions and/or you want to give your users some comforts for the search (like Google does), then use Lucene.

Answer 3

There is no simple, easy-to-use data structure that supports efficient fulltext search.

But do you actually need efficiency? Is this a desktop app or a web app? In the former case, don't worry about efficiency, a modern CPU can search through megabytes of text in fractions of a second - simply look through all your descriptions using String.contains() (or a regexp to allow more flexible searches).

If you really need efficiency (such as for a webapp where many people could do searches at the same time), look into Apache Lucene.

As for your ArrayLists, it seems strange to use one for the description of a single image. Why a list, what does the index represent? Lines? If so, and unless you actually need to access lines directly, replace the lists with a simple String - it can contain newline characters just fine.

Answer 4

A simple implementation is to tokenize the description and use a Map<String, Collection<Item>> to store all items for a token.

Building:

for(String token: tokenize(description)) map.get(token).add(item)

(A collection is needed as multiple entries could be found for a token. The initialization of the collection is missing in the code. But the idea should be clear.)

Use:

List<Item> result = map.get("Computer")

The the general purpose HashMap implementation is not the most efficient in this case. When you start getting memory problems you can look into a tree implementation that is more efficient (like radix trees - implementation).

The next step could be to use some (in-memory) database. These could be relational (HSQL) or not (Berkeley DB).