Алгоритм поиска по инвертированному индексу
Представьте, что в Google ищут 10 миллиардов слов. В соответствии с каждым словом у вас есть отсортированный список всех идентификаторов документов. Список выглядит так:
[Word 1]->[doc_i1,doc_j1,.....]
[Word 2]->[doc_i2,doc_j2,.....]
...
...
...
[Word N]->[doc_in,doc_jn,.....]
Я ищу алгоритм, чтобы найти 100 редких пар слов. Редкая пара слов - это пара слов, которые встречаются вместе (не обязательно смежные) ровно в 1 документе.
Я ищу что-то лучше, чем O(n^2), если это возможно.
2 ответа
- Вы упорядочиваете слова в соответствии с количеством документов, в которых они встречаются. Идея состоит в том, что слова, которые встречаются редко вообще, также будут встречаться редко в парах. Если вы найдете слова, которые встречаются только в одном документе, просто выберите любое другое слово из этого документа, и все готово.
- Затем вы начинаете инвертировать индекс, начиная с самого редкого слова. Это означает, что вы создаете карту, где каждый документ указывает на набор слов в нем. Сначала вы создаете этот перевернутый индекс только с самым редким словом. После того, как вы вставили все документы, связанные с этим редчайшим словом, в инвертированный индекс, у вас есть карта, где каждый документ указывает ровно на одно слово.
- Затем вы добавляете следующее слово со всеми его документами, все еще следуя порядку, созданному в (1.). В какой-то момент вы обнаружите, что документ, связанный со словом, уже присутствует в вашей перевернутой карте. Здесь вы проверяете все слова, связанные с этим документом, если они образуют такую редкую пару слов.
Производительность этой вещи сильно зависит от того, как далеко вы должны пойти, чтобы найти 100 таких пар, идея состоит в том, что вы сделали после обработки лишь небольшой части общего набора данных. Чтобы воспользоваться тем фактом, что вы обрабатываете только небольшую часть данных, вы должны использовать в (1.) алгоритм сортировки, который позволяет находить наименьшие элементы задолго до сортировки всего набора, например быструю сортировку. Затем сортировка может быть выполнена следующим образом: O(N*log(N1)), где N1 - это количество слов, которое вам нужно добавить к инвертированному индексу перед нахождением 100 пар. Сложность других операций, а именно добавления слова в инвертированный индекс и проверки наличия пары слов в более чем одном документе, также линейна с количеством документов на слово, поэтому эти операции должны быть быстрыми в начале и замедляться позже, потому что позже у вас будет больше документов на слово.
Это противоположно «частому добыче набора предметов».
т.е. проверьте эту недавнюю публикацию: Добыча редких образцов: проблемы и перспективы на будущее