Алгоритм поиска по инвертированному индексу

Учтите, что есть 10 миллиардов слов, которые люди искали в Google. Каждому слову соответствует отсортированный список всех идентификаторов документов. Список выглядит так:

[Word 1]->[doc_i1,doc_j1,.....]
[Word 2]->[doc_i2,doc_j2,.....]
...
...
...
[Word N]->[doc_in,doc_jn,.....]

Я ищу алгоритм для поиска 100 редких пар слов. Редкая пара слов — это пара слов, которые встречаются вместе (не обязательно рядом) ровно в 1 документе.

Я ищу что-то лучше, чем O (n ^ 2), если это возможно.


set sorting algorithm information-retrieval inverted-index
person funkyme    schedule 05.02.2014    source источник
comment
Сложность также должна зависеть от количества документов. Каковы ваши требования к сложности с точки зрения слов и документов?   -  person zvisofer    schedule 05.02.2014
comment
Предположим, что максимальное количество документов, в которых может появиться слово, равно m, тогда пересечение двух слов (документов, в которых присутствуют оба слова) можно найти в наихудшем случае O(2*m). В этом случае одна редкая пара слов может быть найдена за O(n^2*m) (грубая сила). Я ищу что-то лучше, чем это.   -  person funkyme    schedule 05.02.2014
comment
Вы можете легко получить O(d * w^2 * m), где w — максимальное количество слов в документе, а d — количество документов. Это лучше?   -  person Niklas B.    schedule 05.02.2014
comment
@zvisofer: Вы можете получить O(m) с высокой вероятностью, используя хеширование. И сортировка всех списков занимает O(n log m) или даже линейное время с использованием целочисленных сортировок, поэтому при необходимости это легко сделать в качестве шага предварительной обработки.   -  person Niklas B.    schedule 05.02.2014
comment
@НикласБ. Но для этого мне нужно инвертировать всю структуру данных из word-doc в doc-word, что само по себе может занять много времени. Также количество слов в документе может быть очень большим. Также это будет O (d ^ 2 * w ^ 2). Не могли бы вы объяснить, если я ошибаюсь?   -  person funkyme    schedule 05.02.2014
comment
@zvisofer: с высокой вероятностью! = ожидаемое время выполнения   -  person Niklas B.    schedule 05.02.2014
comment
@zvisofer Списки документов отсортированы в соответствии с вопросом. Я ищу худший случай. Никлас Б. Можете ли вы объяснить, как вы можете сделать это за O (m) в ожидаемое время (высокая вероятность)   -  person funkyme    schedule 05.02.2014
comment
@Microbotz: Да, вам придется инвертировать индекс, но это линейное время и, следовательно, намного быстрее, чем алгоритм, который вы хотите запустить впоследствии. Я имел в виду, что вы смотрите только на пары слов, которые действительно встречаются вместе в по крайней мере одном документе, путем перечисления всех пар слов во всех документах. Затем вы проверяете, встречаются ли они ровно в одном документе, проверяя пересечение   -  person Niklas B.    schedule 05.02.2014
comment
@Microbotz: вы можете вычислить пересечение двух списков в O(m) whp. Мы не говорили о решении вашей проблемы.   -  person Niklas B.    schedule 05.02.2014
comment
Такую редкую пару традиционно называют googlewhack. Просто говорю.   -  person n. 1.8e9-where's-my-share m.    schedule 05.02.2014
comment
@НикласБ. Будет много пар слов, которые будут встречаться по крайней мере в одном документе, даже если вы удалите стоп-слова (is, a, the и т. д.). и еще вам нужно сделать это для всей пары документов. не могли бы вы объяснить, как вы будете делать это на O (d)?   -  person funkyme    schedule 05.02.2014
comment
@Microbotz: вы перечисляете все документы в O(d) итерациях. В каждом документе у вас есть O(w) слова, поэтому вы перечисляете все пары в O(w^2). Теперь для каждой пары вы вычисляете пересечение их списков документов в O(m), чтобы проверить, встречаются ли они ровно один раз. Весь алгоритм O(d * w^2 * m), но на практике вы можете найти много пар слов несколько раз. Вы можете пропустить часть пересечения, если это произойдет, и сохранить коэффициент m во многих случаях. Будет ли это лучше исходного алгоритма или не очень, зависит от ваших данных. Я не понимаю, откуда вы взяли O(d^2).   -  person Niklas B.    schedule 05.02.2014
comment
@НикласБ. да. Мы можем перечислить слова в O(w^2), а затем мы можем построить хеш с парой слов в качестве ключа и продолжать увеличивать количество слов для пары, если она найдена в любом другом документе. В конце нам нужно пройтись по хеш-таблице и найти пары слов всего одним попаданием (документом). это можно сделать за O(d*w^2) и время на обход хеш-таблицы. Но я сомневаюсь, сколько улучшений это даст.   -  person funkyme    schedule 05.02.2014
comment
@Microbotz: это легко узнать. Просто вычислите sum_{i=1}^d w_i^2 и сравните его с n^2. Я не думаю, что существует детерминированный алгоритм, который не будет иметь в качестве фактора ни n^2, ни w^2. Не уверен насчет случайного выбора, но это маловероятно (хррр)   -  person Niklas B.    schedule 05.02.2014
comment
Да, и, кстати, я не думаю, что разумно предполагать, что реальные данные Google, вероятно, будут худшим случаем вашего алгоритма. Например, я думаю, что вы вполне сможете найти такую ​​пару среди самых редких 10000 слов или около того, поэтому вы можете разработать свой алгоритм так, чтобы он сортировал слова по возрастанию количества вхождений и пробовал пары с уменьшением редкости.   -  person Niklas B.    schedule 05.02.2014
comment
@НикласБ. Я с тобой согласен. Но я думал об этой проблеме и задавался вопросом, существует ли лучший способ, чем грубая сила для этой проблемы?   -  person funkyme    schedule 05.02.2014

Ответы (2)


arrow_upward
3
arrow_downward

  1. Вы упорядочиваете слова в соответствии с количеством документов, в которых они встречаются. Идея здесь в том, что слова, которые вообще редко встречаются, также редко встречаются парами. Если вы найдете слова, которые встречаются только в одном документе, просто выберите любое другое слово из этого документа, и все готово.
  2. Затем вы начинаете инвертировать индекс, начиная с самого редкого слова. Это означает, что вы создаете карту, в которой каждый документ указывает на набор слов в нем. Сначала вы создаете этот инвертированный индекс только с самым редким словом. После того, как вы вставили все документы, связанные с этим самым редким словом, в инвертированный индекс, у вас есть карта, на которой каждый документ указывает ровно на одно слово.
  3. Затем вы добавляете следующее слово со всеми его документами, все еще следуя порядку, созданному в (1.). В какой-то момент вы обнаружите, что документ, связанный со словом, уже присутствует в вашей перевернутой карте. Здесь вы проверяете все слова, связанные с этим документом, если они образуют такую ​​редкую пару слов.

Производительность сильно зависит от того, как далеко вы должны зайти, чтобы найти 100 таких пар, идея состоит в том, что вы закончите обработку лишь небольшой части общего набора данных. Чтобы воспользоваться тем фактом, что вы обрабатываете только небольшую часть данных, вы должны использовать в (1.) алгоритм сортировки, который позволяет вам находить наименьшие элементы задолго до того, как будет отсортирован весь набор, например быстрая сортировка. Затем сортировка может быть выполнена как O(N*log(N1) ), где N1 — это количество слов, которое вам действительно нужно добавить к инвертированному индексу, прежде чем найти 100 пар. Сложность других операций, а именно добавление слова в инвертированный индекс и проверка того, встречается ли пара слов более чем в одном документе, также линейна с количеством документов в одном документе. слово, поэтому эти операции должны быть быстрыми в начале и замедляться позже, потому что позже у вас будет больше документов на слово.

person pentadecagon    schedule 05.02.2014

arrow_upward
0
arrow_downward

Это противоположность частому добыче набора предметов.

т.е. проверьте эту недавнюю публикацию: Извлечение редких паттернов: проблемы и перспективы на будущее

person Radio Controlled    schedule 13.12.2020