Структура данных для поисковой системы в JAVA?

Я студент второго курса MCS. Я делаю проект на Java, в котором у меня есть разные изображения. Для хранения описания скажем IMAGE-1 у меня есть ArrayList с именем IMAGE-1, аналогично для IMAGE-2 ArrayList IMAGE-2 n и так далее .....

Теперь мне нужно разработать поисковик, в котором мне нужно найти все изображения, описание которых совпадает со словом, введенным в поисковик ..........

FOR EX Если я введу «компьютер», я смогу найти все изображения, описание которых содержит «компьютер».

Итак, мой вопрос ...

Как мне сделать это эффективно?
Как мне сохранить все эти ArrayList, так как я могу иметь 100 таких ...? или я должен использовать другую структуру данных вместо ArrayList?

13.10.2009 08:50:50
4 ОТВЕТА

Я бы предложил вам использовать класс Hashtable или организовать ваш контент в виде дерева для оптимизации поиска.

0
13.10.2009 08:57:57
-1 Hashtable устарел с Java 1.2 и не имеет абсолютно никакого отношения к деревьям.
Michael Borgwardt 13.10.2009 09:18:11
Я не работал с Java в прошлом году. Я только что проверил документ: java.sun.com/j2se/1.4.2/docs/api/java/util/Hashtable.html Никаких упоминаний об устаревании или устаревании нет. Док был с 1.4.2. Я видел совет использовать HashMap в Java 1.6. Деревья не были напрямую связаны с хеш-таблицами, но представляли альтернативу. Например, посмотрите на: stackoverflow.com/questions/823744/ternary-tree-vs-hash-table
Roberto Aloi 13.10.2009 09:45:59

Если у вас есть небольшое количество изображений и кратких описаний (<1000 символов), загрузите их в массив и выполните поиск слов с помощью String.indexOf()(т.е. одна запись в массиве == одно полное описание изображения). Это достаточно эффективно, скажем, для менее чем 10 000 изображений.

Используйте, toLowerCase()чтобы сложить регистр символов (чтобы пользователи находили «Компьютер» при вводе «компьютера»). String.indexOf()также будет работать для коротких слов (используя «comp», чтобы найти «Computer» или «сравнить»).

Если у вас много изображений и длинных описаний и / или вы хотите предоставить своим пользователям некоторые удобства для поиска (как в Google), используйте Lucene .

1
13.10.2009 09:16:07
Люсена это слон, поверь мне. Но действительно стоит попробовать.
Adeel Ansari 13.10.2009 09:07:00
Спасибо ... но описание может быть довольно большим, то есть более 1000 строк, так что можете хранить его в простом массиве?
user188944 13.10.2009 09:26:51
В чем проблема с использованием строки?
Thomas Jung 13.10.2009 09:35:28
Массиву потребуется больше памяти, и поиск будет медленнее, так зачем вам его использовать?
Aaron Digulla 13.10.2009 12:11:24

Не существует простой, удобной в использовании структуры данных, которая поддерживает эффективный полнотекстовый поиск.

Но вам действительно нужна эффективность? Это настольное приложение или веб-приложение? В первом случае не беспокойтесь об эффективности: современный ЦП может осуществлять поиск в мегабайтах текста за доли секунды - просто просматривайте все ваши описания, используя String.contains()(или регулярное выражение, чтобы обеспечить более гибкий поиск).

Если вам действительно нужна эффективность (например, для веб-приложения, в котором многие люди могут выполнять поиск одновременно), изучите Apache Lucene .

Что касается ваших ArrayLists, кажется странным использовать один для описания одного изображения. Почему список, что представляет собой индекс? Линии? Если это так, и если вам действительно не нужен прямой доступ к строкам, замените списки простой строкой - она ​​может содержать символы новой строки просто отлично.

1
13.10.2009 09:16:59
Это странный подход. Попробуйте грубую силу. Если это не поможет, используйте эту гигантскую библиотеку (Lucene). Есть одно или два решения в середине.
Thomas Jung 13.10.2009 09:09:47
Приведите примеры, которые не требуют много работы или имеют ограниченную полезность (сопоставление слов со смещением текста не подходит для составных слов).
Michael Borgwardt 13.10.2009 09:16:40
Одним из упрощенных решений может быть: токенизация описания для (token: tokenize (descr)) map.put (token, item). Это сожжет немного памяти, но может быть правильным решением. В зависимости от ограничений.
Thomas Jung 13.10.2009 09:20:43
Как я уже писал: не получается составные слова. Большинство пользователей не будут довольны этим ограничением.
Michael Borgwardt 13.10.2009 09:27:00
Можно токенизировать по мере необходимости. Если вы начинаете строить свой собственный стеминг, самое время использовать Lucene. Но проблема была в том, чтобы найти прямые попадания (простой токенизатор, а не остановка).
Thomas Jung 13.10.2009 09:33:32

Простая реализация состоит в том, чтобы маркировать описание и использовать Map<String, Collection<Item>>для хранения всех элементов для токена.

Здание:

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

(Коллекция необходима, поскольку для токена можно найти несколько записей. Инициализация коллекции отсутствует в коде. Но идея должна быть ясной.)

Использование:

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

Реализация HashMap общего назначения в этом случае не самая эффективная. Когда у вас начнутся проблемы с памятью, вы можете взглянуть на более эффективную реализацию дерева (например, основополагающие деревья - реализация ).

Следующим шагом может быть использование некоторой (в памяти) базы данных. Они могут быть реляционными ( HSQL ) или нет ( Berkeley DB ).

2
14.10.2009 18:52:38
Вы ничего нового не говорите. Смотрите мой пост.
Adeel Ansari 13.10.2009 09:39:40
Я не понял, что вы пытаетесь сказать: тег! = Токен. Если он называется тегом, он должен быть тегом ( en.wikipedia.org/wiki/Tag_%28metadata%29 ). Пометка звучит так, как будто пользователь принимает решение, какие элементы и теги связаны между собой.
Thomas Jung 13.10.2009 09:47:31
В вашем случае список предметов / изображений будет сопоставлен с токеном / ключом. В моем случае это то же самое, но я говорю это тег вместо токена. Поскольку мы здесь, в SO, помечаем наши сообщения, и один тег может содержать список сообщений. Таким образом, термин, который я использовал, явно верен, я считаю.
Adeel Ansari 13.10.2009 09:54:23
Может быть, я не очень хорошо выразил свою идею. Или сказать, что я выбрал не то слово. Как бы то ни было, но на самом деле я сказал то же самое. Итак, +1 за мысли, как я :).
Adeel Ansari 13.10.2009 09:58:00
Как вы можете видеть с SO, набор тегов - это не описание токена, а метаданные, назначенные пользователем. Это две совершенно разные концепции.
Thomas Jung 13.10.2009 09:58:17