Ответ 1
Вы можете увидеть очень простую реализацию инвертированного индекса и поиска в TinySearchEngine.
Для вашего первого вопроса, если вы хотите создать простой (в памяти) инвертированный индекс, простая структура данных - это карта хэша, подобная этой:
val invertedIndex = new collection.mutable.HashMap[String, List[Posting]]
или Java-esque:
HashMap<String, List<Posting>> invertedIndex = new HashMap<String, List<Postring>>();
Хеш отображает каждый член/слово/токен в список проводок. A Posting - это просто объект, который представляет собой вхождение слова внутри документа:
case class Posting(docId:Int, var termFrequency:Int)
Индексирование нового документа - это просто его токенизация (разделение в токенах/словах) и для каждого токена вставить новую проводку в правильный список хэш-карты. Конечно, если Posting уже существует для этого термина в этом конкретном docId, вы увеличиваете значение termFrequency. Есть и другие способы сделать это. Для инвертированных индексов памяти это нормально, но для индексов на диске вы, вероятно, захотите вставить Postings один раз с правильным termFrequency, а не обновлять его каждый раз.
Что касается вашего второго вопроса, обычно два случая:
(1) у вас есть (почти) неизменяемый индекс. Вы индексируете все свои данные один раз, и если у вас есть новые данные, вы можете просто переиндексировать. Например, нет необходимости в режиме реального времени или индексировании много раз за час.
(2) все новые документы поступают все время, и вам необходимо как можно скорее выполнить поиск вновь прибывших документов.
В случае (1) вы можете иметь как минимум 2 файла:
1 - Инвертированный индексный файл. Он перечисляет для каждого термина все Postings (пары docId/termFrequency). Здесь представлены в виде обычного текста, но обычно хранятся в виде двоичных данных.
Term1<docId1,termFreq><docId2,termFreq><docId3,termFreq><docId4,termFreq><docId5,termFreq><docId6,termFreq><docId7,termFreq>
Term2<docId3,termFreq><docId5,termFreq><docId9,termFreq><docId10,termFreq><docId11,termFreq>
Term3<docId1,termFreq><docId3,termFreq><docId10,termFreq>
Term4<docId5,termFreq><docId7,termFreq><docId10,termFreq><docId12,termFreq>
...
TermN<docId5,termFreq><docId7,termFreq>
2- Файл смещения. Хранит для каждого термина смещение, чтобы найти его перевернутый список в инвертированном файле индекса. Здесь я представляю смещение в символах, но вы обычно храните двоичные данные, поэтому смещение будет в байтах. Этот файл может быть загружен в память во время запуска. Когда вам нужно найти термин перевернутый список, вы просматриваете его смещение и читаете перевернутый список из файла.
Term1 -> 0
Term2 -> 126
Term3 -> 222
....
Наряду с этими двумя файлами вы можете (и обычно) иметь файл для хранения каждого термина IDF и каждой нормы документа.
В случае (2) я попытаюсь кратко объяснить, как Lucene (и, следовательно, Solr и ElasticSearch).
Формат файла может быть таким же, как описано выше. Основное различие заключается в том, что вы индексируете новые документы в таких системах, как Lucene, вместо того, чтобы восстанавливать индекс с нуля, они просто создают новый с только новыми документами. Поэтому каждый раз, когда вам нужно что-то индексировать, вы делаете это в новом разделенном индексе.
Чтобы выполнить запрос в этом "разделенном" индексе, вы можете запускать запрос по каждому другому индексу (параллельно) и объединить результаты вместе, прежде чем вернуться к пользователю.
Lucene называет эти "маленькие" индексы segments.
Очевидная проблема заключается в том, что вы получите очень много маленьких сегментов очень быстро. Чтобы этого избежать, вам понадобится политика для слияния сегментов и создания больших сегментов. Например, если у вас больше, чем N segments, вы можете объединить все сегменты, меньшие, чем 10 KBs.