В чем разница между инвертированным индексом и обычным старым индексом?
в программной инженерии мы создаем индексы все время (например, в базах данных), но я также слышу много людей говорят об инвертированных индексах. Есть ли что-то принципиально другое между ними? Они звучат как одно и то же.
8 ответов:
одно общее использование " ... для быстрого полнотекстового поиска."
эти два типа обозначают направленности. Один берет тебя вперед через индекс, а другой принимает вас назад (обратное) через индекс. Вот и все. Здесь нет никакой тайны, чтобы раскрыть ее. В противном случае два типа идентичны, это просто вопрос того, какую информацию вы есть, и в результате какая информация вы пытаетесь найти.
чтобы обратиться к вашему запросу, я не думаю, что на самом деле есть способ узнать, почему использование-это то, что есть сегодня. Единственная причина, по которой важно определить, что это
forwardиinvertedэто так, что мы все можем поговорить о них, и все знают, в каком направлении мы говорим. Подумайте о терминах "левый" и "правый": они относительны. Это не имеет значения, за исключением того, что каждый должен согласиться, какой из них "левый" , а какой "правильно" для того, чтобы слова имели смысл. Если бы, как культура, мы решили перевернуть влево и вправо, тогда у вас была бы та же проблема, выясняя, что такое "правый поворот" против "левого поворота", поскольку согласованное значение изменилось. Однако имя произвольно, так что какой из них (сам по себе) не имеет значения - важно то, что мы все согласен на смысл.в вашем комментарии, где вы спрашиваете: "пожалуйста, не просто определите термины", вам не хватает точка, и я думаю, что вы просто зацикливаетесь на формулировке, когда между ними нет абсолютно никакой разницы.
Для будущих читателей я приведу несколько примеров индекса" вперед "и" назад":Пример 1: Web search
Если вы думаете, что инверсия индекса-это что-то вроде обратная функция в математике, где обратное-это особая вещь, которая имеет другую форму, то вы ошибаетесь: здесь дело не в этом.
в поисковике у вас есть список документов (страниц на веб-сайтах), где вы вводите несколько ключевых слов и получите результаты.
A вперед индекса (или просто индекс) - это список документов, и какие слова появляются в них. В примере веб-поиска Google обходит веб-страницы, создавая список документов, выясняя, какие слова появляются на каждой странице.
The перевернутый индекс - это список слов, и документы, в которых они появляются. В примере веб-поиска вы предоставляете список слов (ваш поисковый запрос), а Google создает документы (ссылки на результаты поиска).
Они оба индекса - это просто вопрос, в каком направлении вы идете. Вперед от документов - >К - > слова, перевернутый от слов->к - >документы.
Пример 2: DNS
другой пример-DNS поиск (который принимает имя хоста и возвращает IP-адрес) и обратный поиск (который принимает IP-адрес и дает вам имя хоста).
Пример 3: книга
индекс в конце книги на самом деле инвертированный индекс, как определено выше примеры - список слов, и где их найти в книге. В книге оглавление похоже на вперед индекса: это список документов (глав) , которые книга содержит, за исключением того, что вместо перечисления слов в этих разделах, оглавление просто дает имя / общее описание того, что содержится в этих документах (главах).
Пример 4: Ваш мобильный телефон
The вперед индекса в вашем мобильном телефоне есть список контактов, и какие номера телефонов (сотовый, домашний, рабочий) связаны с этими контактами. Элемент инвертированный индекс это то, что позволяет вручную ввести номер телефона, и когда вы нажмете "набрать" вы видите имя человека, а не номер, потому что ваш телефон взял номер телефона и нашел вам контакт, связанный с ним.
Они назвали его инвертированным только потому, что уже есть прямой индекс. Возьмем пример поисковой системы, она состоит из двух частей: первая часть - "веб-искатель и парсер", которые строят индекс от документа к слову, вторая часть-поисковая база данных, которая строит индекс от слова к документу. Поскольку первый индекс существует, мы, естественно, называем второй индекс инвертированным индексом.
Если вы называете TOC (таблицу содержания) книги в качестве индекса, то вы должны вызвать индекс в конце книги как "перевернутый индекс". Или, с другой стороны, вы можете вызвать TOC как инвертированный индекс.
обычно говоря об индексе, вы имеете в виду некоторые добавленные вычисления или сохраненные результаты процедур, которые были сделаны для ускорения приложения (например, MySQL или другие СУБД обратитесь к MySQL docs). Индексация также может быть связано с кэшированием и т. д.
инвертированный индекс создает файл со структурой, которая в первую очередь предназначена для (полнотекстового) поиска.
инвертированный индекс состоит из двух основных файлы:
- словарь
- символы
в словаре есть общие слова, извлеченные из текста (конечно, после фильтрации черного списка слов, таких как местоимения). Файл occurences содержит связь между словами и документами (word1 отображается в doc1 и doc2, а не в doc3). Он представлен в виде матрицы.
на приведенном выше изображении показан процесс создания двух файлов упомянутый.
Если вы еще больше интересуетесь этой проблематикой, я могу порекомендовать вам отличную книгу, написанную Рикардо Ятедом-Modern Information Retrieval (смотрите его на Amazon) - о странице 200 я думаю.
надеюсь, что это помогает :-)
normalocity уже чудесно дифференцированных между прямым и инвертированным индексом, но для вопроса о том, почему один называется прямым индексом, а другой-инвертированным индексом, возможно, именно поэтому они называются так - - -
принимая во внимание пример обхода и индексирования поисковой системы (или построения индекса для книги), прямой индекс может быть построен одновременно во время обхода веб-страниц(или чтения книги) или будет вперед. Итак, если у вас есть 10 веб-страниц для обхода (или 10 глав в книге), вы можете просмотреть первую веб-страницу (прочитать первую главу), а затем составить список слов, которые появляются на веб-странице (слова, которые появляются в главе), и продолжить этот процесс для других веб-страниц(других глав), поэтому к тому времени, когда вы просмотрели все 10 веб-страниц(прочитайте все 10 глав) ваш forward index завершается каждой веб-страницей (главой), указывающей на список слов, которые она содержит.
но чтобы сделать инвертированный индекс, вы должны просмотреть все 10 веб-страниц (прочитать 10 глав), а затем взять каждое слово из каждого списка документов и выяснить, какие документы содержат это слово. Так что это как идти назад, как только вы обход веб-страниц(читать главы книги). Так называемый инвертированный индекс.
Это только мои предположения.
есть много типов индексов. Например, B-дерево, R-дерево, хэш... Для разных целей, мы должны выбрать правильный индекс.
инвертированный индекс является специальным. Инвертированный индекс обычно используется в полнотекстовый поиск. Использование инвертированного индекса мы можем узнать расположение слова в документе(или наборе документов) как можно быстрее. Подумайте о пределе памяти и процессора, другой индекс не может закончить эту работу.
вы можете прочитать документ lucene для получения более подробной информации. Это открытое место источник поисковой системы. http://lucene.apache.org/java/docs/index.html
термин "перевернутый индекс слова" относится к изменению отношения один документ, содержащий много слов, к каждому уникальному слову, содержащему (или идентификация) список многих документов. Это фактически берет отношение " один ко многим "(Docs to Words) и инвертирует (или реверсирует) его таким образом, что теперь существует новое" инвертированное "отношение" один ко многим", которое является каждым уникальным словом, относящимся ко многим документам (т. е. всем, которые содержат это слово). Это происхождение действительно так просто, и термин " инвертированный индекс "использовался для описания ручных индексов того же типа задолго до того, как компьютеры и электронная высокоскоростная индексация даже существовали (да, по общему признанию, Я старый программист, почти достаточно старый, чтобы считать Грейс Хоппер" милой молодой леди " возраст, подходящий для ухаживания, когда COBOL был блестящим новым языком). Пожалуйста, не отбрасывайте нас, стариков, пока мы можем иногда предоставлять полезный и, возможно, даже ценный исторический tid-бит или два-когда наша личная оперативная память все еще работает, то есть. [ухмылка]
в инвертированных индексах мы имеем следующий вид:
word1 - > список документов это происходит в (отсортированном порядке)
word2 - > список документов это происходит в (отсортированном порядке)
Это очень полезно для обработки запросов поисковой системы, поскольку это позволяет нам найти документы, в которых встречается слово .
вы можете использовать контролируемое машинное обучение для построения этого инвертированного индекса.
еще одно отличие:
обработка обновлений с инвертированным индексом является дорогостоящей по сравнению с прямым индексом.
прямой индекс легко обрабатывает обновления, отражая изменения только в соответствующем индексе документа, тогда как в инвертированном индексе одно и то же изменение должно отражаться в нескольких позициях по инвертированному индексу.