В чем разница между инвертированным индексом и простым старым индексом?

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

Один из распространенных способов использования - «... для быстрого полнотекстового поиска».

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

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

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


Для будущих читателей я приведу несколько примеров «прямого» и «перевернутого» индекса:

Пример 1: Интернет-поиск

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

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

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

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

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

Пример 2: DNS

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

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

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

Пример 4: ваш мобильный телефон

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

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

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

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

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

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

• Словарь
• Случаи

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

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

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

Надеюсь, поможет :-)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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