Что алгоритм должен искать индекс несколько значений?
Это - на самом деле настоящая проблема, я продолжаю работать, но для простоты, давайте притворимся, что я - Google.
Скажите пользовательские поиски "наноразмера tupperware". Нет очень многих страниц с обоими словами... только о 3k. Но существует ~2 миллиона страниц с "наноразмером" и ~4 миллиона с "tupperware". Однако, Google находит 3k для меня за 0,3 секунды.
Как это делает это?
Единственный алгоритм, о котором я знаю, должен получить документы для "наноразмера", получить документы для "tupperware" и затем сделать слияние списка. Но это - O (N + M) или O (5,000,000), который кажется немногим медленным. Особенно, если я выполняю его на рабочем столе вместо uber-быстрого кластера.
Так то, что на самом деле, что Google делает, и их скорость должна главным образом к тому, что они выполняют это дорогое вычисление на своем значительном распределенном кластере?
Или есть ли лучший алгоритм, о котором я не знаю? Википедия и Google ничего не поднимают для меня.
Править:
Так как люди, кажется, фокусируются на аспекте Google моего вопроса, я предполагаю, что вновь заявлю о нем в фактических терминах.
У меня есть несколько очень большие (миллионы объектов) индексы, реализованные как пары ключ/значение. Ключи являются простыми словами, значениями являются Наборы документов. Случай общего использования должен получить пересечение результатов на нескольких поисках на различных индексах: болевая точка получает пересечение множеств документа.
Я могу повторно реализовать свои индексы однако, я хочу - это - главным образом академический проект в этой точке.
2 ответа
Как вы это описываете, у вас уже есть инвертированный индекс со списком сообщений для каждого термина (список документов). Я не знаю лучшего решения, чем объединение в списки сообщений для каждого термина, и, насколько мне известно, это то, что делают решения для полнотекстового индексирования, такие как Lucene. Тем не менее, вы можете сделать несколько очевидных оптимизаций:
- Если вы можете хранить свой набор данных в памяти, даже распределяя его по многим машинам, вы можете объединить объединение , и результаты будут получены очень быстро, по сравнению с что потребуется для поиска диска.
- «Наивный» алгоритм объединения слиянием продвигает один указатель на одну позицию при каждом несовпадении, но если ваши списки сообщений сами индексируются, вы можете добиться большего, взяв максимум отдельных текущих значений и выполнив поиск во всех других списках сообщений до первого значения, большего или равного этому ключу - возможно, пропуская миллионы нерелевантных результатов в процессе. Это было названо зигзагообразным объединением слияния .
То, что вы описываете, называется n-граммами.
Google использует алгоритм под названием PageRank для поиска и сортировки результатов, который реализован с помощью MapReduce.
Все эти темы подробно обсуждались на Stackoverflow в прошлом. Найти их будет довольно просто.
Вероятно, это не очень поможет вам, поскольку у вас, скорее всего, нет огромной распределенной системы для запуска MapReduce, но поскольку вы не дали нам никаких подробностей о том, что вы пытаетесь индексировать, трудно предложить что-то подходящее для вашей проблемы.