В чем разница между инвертированным индексом и простым старым индексом? - PullRequest
79 голосов
/ 11 октября 2011

В разработке программного обеспечения мы постоянно создаем индексы (например, в базах данных), но я также слышал, что многие люди говорят об инвертированных индексах.Есть ли что-то принципиально другое между ними?Они звучат как одно и то же.

Ответы [ 8 ]

191 голосов
/ 02 декабря 2011

Одним из распространенных вариантов использования является "... для обеспечения быстрого полнотекстового поиска."

Два типа обозначают направленность .Один ведет вас вперед по индексу, а другой - назад (обратный) по индексу.Вот и все.Там нет никакой тайны, чтобы раскрыть здесь.В противном случае эти два типа идентичны, это просто вопрос о том, какую информацию вы имеете , и в результате какую информацию вы пытаетесь найти.

По адресуВаш запрос, я не думаю, что на самом деле есть способ узнать, почему использование сегодня такое.Единственная причина, по которой важно определить, что является forward, а какая - inverted, заключается в том, что мы все можем поговорить о них, и каждый знает, в каком направлении мы говорим.Подумайте о терминах «левый» и «правый»: они относительны.То, что не имеет значения, за исключением того, что каждый должен договориться, какой из них «левый», а какой «правый», чтобы слова имели значение.Если бы, как культура, мы решили перевернуть влево и вправо, у вас возникла бы та же проблема, выясняя, что такое «поворот вправо» и «поворот налево», поскольку согласованное значение изменилось.Тем не менее, наименование является произвольным, так что какой из них (сам по себе) не имеет значения - важно то, что мы все согласны в отношении значения.

В вашем комментарии, гдеВы спрашиваете: «Пожалуйста, не просто определяйте термины», вы упускаете суть, и я думаю, что вы просто зацикливаетесь на формулировках, когда между ними нет абсолютно никакой разницы.Для будущих читателей я приведу несколько примеров «прямого» и «инвертированного» индекса:

Пример 1. Веб-поиск

Если вы думаете, что обратное значение индексаэто что-то вроде инверсии функции в математике , где инверсия - это особая вещь, которая имеет другую форму, тогда вы ошибаетесь: это не тот случай.

ВПоисковая система у вас есть список документов (страниц на веб-сайтах), где вы вводите некоторые ключевые слова и получаете результаты обратно.

A форвардный индекс (или просто индекс) это список документов и слова в них.В примере веб-поиска Google сканирует сеть, формируя список документов, выясняя, какие слова встречаются на каждой странице.

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

Они оба являются индексами - это просто вопрос, в каком направлении вы находитесьсобирается.Вперед от документов-> к-> словам, к перевернутым от слов-> к-> документам.

Пример 2. DNS

Другим примером является поиск DNS (который принимает имя хоста и возвращает IP-адрес) и обратный поиск (который принимает IP-адрес и дает вамимя хоста).

Пример 3: книга

Индекс в конце книги на самом деле представляет собой инвертированный индекс , как определено в приведенных выше примерах - список слов игде их найти в книге.В книге оглавление похоже на форвардный индекс : это список документов (глав), которые содержит книга, за исключением того, что вместо перечисления слов в этих разделах оглавление просто даетназвание / общее описание того, что содержится в этих документах (главы).

Пример 4. Ваш сотовый телефон

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

20 голосов
/ 06 декабря 2011

Они назвали это инвертированным только потому, что уже есть форвардный индекс. Возьмите пример поискового движка, он состоит из двух частей: первая часть - это «веб-сканер и анализатор», которые создают индекс от документа к слову, вторая часть - поисковая база данных, которая создает индекс от слова к документу. Поскольку первый индекс существует, мы, естественно, называем второй индекс инвертированным.

Если вы называете оглавление (оглавление) книги в качестве индекса, то индекс в конце книги следует называть «инвертированным индексом». Или, с другой стороны, вы можете назвать TOC как инвертированный индекс.

6 голосов
/ 03 мая 2012

normalocity уже прекрасно дифференцировал между прямым и инвертированным индексом, но на вопрос, почему один называется прямым индексом, а другой инвертированным, может быть, поэтому они называются так ---

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

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

Это всего лишь мои предположения.

6 голосов
/ 05 декабря 2011

обычно, когда речь идет об индексе, вы имеете в виду некоторые дополнительные вычисления или сохраненные результаты процедур, которые были сделаны для ускорения приложения (например, MySQL или другая СУБД Обратитесь к MySQL, документация ).Индексирование также может быть связано с кэшированием и т. Д.

Инвертированный индекс создает файл со структурой, которая в основном предназначена для (полнотекстового) поиска.

Инвертированный указатель состоит из двух основных файлов:

  • Словарь
  • Вхождения

В словаре используются общие слова, извлеченные из текста (изконечно после фильтрации черного списка слов типа местоимений).Файл вхождений содержит связь между словами и документами (слово1 появляется в doc1 и doc2, а не в doc3).Он представлен в виде матрицы.

Indexing process - inverted index

На изображении выше показан процесс создания двух упомянутых файлов.

Если вы находитесь дальшеИнтересуюсь этим проблемным вопросом, я могу порекомендовать вам отличную книгу, написанную Рикардо Ятедом - Современный поиск информации ( Посмотрите на Амазонке ) - я думаю о странице 200.

4 голосов
/ 02 декабря 2011

Существует много типов индексов. Например, B-дерево, R-дерево, хэш ... Для разных целей мы должны выбрать правильный индекс.

Инвертированный индекс является особым. Инвертированный индекс обычно используется в полнотекстовой поисковой системе. Используя инвертированный индекс, мы можем узнать местоположение слова в документе (или наборе документов) как можно быстрее. Подумайте об ограничении памяти и процессора, другие индексы не могут завершить эту работу.

Вы можете прочитать документ Lucene для более подробной информации. Это поисковая система с открытым исходным кодом. http://lucene.apache.org/java/docs/index.html

2 голосов
/ 28 апреля 2018

Термин «индекс перевернутого слова» относится к изменению отношения одного документа, содержащего много слов, к каждому уникальному слову, содержащему (или идентифицирующему) список из множества документов.Это фактически берет отношение «один ко многим» (Документы к словам) и инвертирует (или обращает) его так, что теперь существует новое «перевернутое» отношение «один ко многим», то есть каждое уникальное слово, относящееся ко многим.Документы (т. Е. Все, что содержит это слово).Его происхождение действительно так просто, и термин «инвертированный индекс» использовался для описания ручных индексов того же типа задолго до того, как компьютеры и электронная высокоскоростная индексация даже существовали (да, по общему признанию, я старый программист, почтидостаточно взрослый, чтобы считать Грэйс Хоппер «милой молодой леди», подходящей для ухаживания, когда «Кобол» был новым блестящим языком).Пожалуйста, пока не отказывайтесь от нас, чудаков, потому что мы иногда можем предоставить полезную и, возможно, даже ценную историческую новость - два, когда наша личная память все еще работает, то есть.[Оскал]

2 голосов
/ 11 октября 2011

в инвертированных индексах мы имеем следующую форму:

word1-> список документов, в которых он находится (в порядке сортировки)

word2-> список документов, в которых он находится (в порядке сортировки)

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

Вы можете использовать контролируемое машинное обучение для построения этого инвертированного индекса.

0 голосов
/ 28 августа 2017

Еще одно отличие:

Обработка обновлений с инвертированным индексом обходится дороже по сравнению с прямым индексом.

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

...