индексировать много документов, чтобы включить запросы, которые поддерживают операции И / ИЛИ

Question

У нас много документов, состоящих из слов.Что является наиболее подходящим способом индексирования документов.Поисковый запрос должен поддерживать операции AND / OR.

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

Документы содержат только слова (исключая И / ИЛИ), а запрос содержит слова и ключевые слова И / ИЛИ.

РЕДАКТИРОВАТЬ: каков был бы алгоритм, если бы я разрешил только 2 ключевых слова и операцию (например, w1 и w2)

Answer 1

Необходима базовая структура данных: инвертированный индекс .Это сопоставляет каждое слово с набором документов, которые его содержат.Допустим, lookup - это функция от слов к наборам документов: lookup: W -> Pos(D) (где W - набор слов, D набор документов, Pos(D) набор мощности D).

Допустим, у вас есть выражение запроса в форме:

Expr ::= Word | AndExpression | OrExpression
AndExpression ::= Expr 'AND' Expr
OrExpression ::= Expr 'OR' Expr

Итак, вы получите абстрактное синтаксическое дерево, представляющее ваш запрос.Это дерево со следующими видами узлов:

abstract class Expression { }

class Word extends Expression {
  String word
}

class AndExpression extends Expression {
  Expression left
  Expression right
}

class OrExpression extends Expression {
  Expression left
  Expression right
}

Например, foo AND (bar OR baz) будет переведено в это дерево:

       AndExpression
      /             \
     /               \
  Word('foo')         OrExpression
                    /             \
                   /               \
             Word('bar')       Word('baz')

Чтобы оценить это дерево, следуйте этим простым правилам, выраженный в псевдокоде:

Set<Document> evaluate(Expr e) {
   if (e is Word) 
      return lookup(e.word)
   else if (e is AndExpression) 
      return intersection(evaluate(e.left), evaluate(e.right))
   else if (e is OrExpression) 
      return union(evaluate(e.left), evaluate(e.right))

   //otherwise, throw assertion error: no other case remaining
}

//implemented by the inverted index, not shown
Set<Document> lookup(String word)

Таким образом, выражения AND в основном транслируются для установки пересечений, в то время как выражения OR переводятся в выражения объединения, все оцениваются рекурсивно.Я уверен, что если вы посмотрите достаточно долго на вышесказанное, вы увидите его красоту:)

Вы можете представить каждый набор (который возвращает lookup) как HashSet.Если вы используете Java, вы также можете использовать реализации ленивых union и intersection в guava, что должно быть весело (особенно если вы изучаете код или используете свое воображение, чтобы увидеть, что на самом деле 'lazy')значит в этом контексте).

Насколько я знаю, пересечения редко вычисляются путем пересечения хеш-таблиц - вместо этого обычно происходит следующее: предположим, что 3 набора должны быть пересечены, мы выбираем один (наименьший предпочтительно) и назначаемсчетчик (равный 1) каждому из документов.Затем мы повторяем другие наборы, увеличивая счетчик каждого найденного документа.Наконец, мы сообщаем каждому документу, что его счетчик становится 3 (это означает, что документ появился во всех наборах, таким образом, существует в их пересечении).

Answer 2

В случае, если разрешено только 2 ключевых слова (например, "ключ1 И ключ2")

Это решение, которое я нашел до сих пор: 1) keyMap, HashMap, где ключом являются ключевые слова, а значением является LinkedList документов. 2) docMap, HashMap, где ключом является идентификатор документа, а значением является HashSet ключевых слов

Теперь по такому запросу ("key1 AND key2") я бы:

LinkedList docs = keyMap.get(key1);
for each (HashSet doc:docs)
     if(doc.contains(keys))
            result.add(doc);
return result

Что ты думаешь? Есть ли лучший способ? Как насчет 3 ключевых слов?

Answer 3

Со многими документами специальный пакет, такой как Lucene , становится очень привлекательным.

Answer 4

Как сказал @Wrikken, используйте lucene.

Поскольку вас интересует множество используемых алгоритмов, вы можете найти отправную точку здесь и дополнительную информацию здесь .

Answer 5

Google Desktop приходит на ум, но все основные O / S имеют схожие функции, встроенные или легко добавляемые.Я бы назвал пространство, используемое Spotlight на моем Mac, «разумным».