Как создать простой инвертированный индекс?

Я хочу создать простую функцию индексирования поисковой системы без какого-либо API, например Lucene. В инвертированном индексе мне просто нужно записать основную информацию каждого слова, например. docID, положение и частота.

Теперь у меня есть несколько вопросов:

Какая структура данных часто используется для построения инвертированного индекса? Многомерный список?
После создания индекса, как записать его в файлы? Какой формат в файле? Как таблица? Как рисовать индексную таблицу на бумаге?

Ответ 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.